Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Эвклидовы сети
|
|
В приложениях, где сеть является моделью карты, наш основной интерес часто направлен на нахождение лучшего маршрута из одной точки в другую. В этом разделе мы рассматриваем стратегию решения упомянутой задачи: быстрый алгоритм для задачи кратчайшего пути источник-сток в эвклидовых сетях, т.е. таких, вершины которых являются точками на плоскости и веса ребер которых определяются геометрическими расстояниями между этими точками.
Часть 5. Алгоритмы на графах
|
| Эти сети обладают двумя важными свойствами, которые не обязательно присущи весам ребер в общем случае. Во-первых, расстояния удовлетворяют неравенству треугольника: расстояние от s до d никогда не больше, чем расстояние от s до х плюс расстояние от х до d. Во-вторых, координаты вершин дают нижнюю границу длины пути: не существует пути из s в d, который был бы короче, чем расстояние между s и d. Алгоритм поиска кратчайших путей для задачи источник-сток, который мы рассматриваем в этом разделе, использует особенности этих двух свойств, что улучшает его эффективность. Часто эвклидовы сети также симметричны: их ребра являются двунаправленными. Как упоминалось в начале этой главы, такие сети возникают всякий раз, когда, например, мы интерпретируем Представление взвешенного неориентированного эвклидового графа в форме матрицы смежности или списков смежности (см. раздел 20.7) как взвешенный орграф (сеть). Когда мы рисуем неориентированную эвклидову сеть, мы делаем это ввиду того, что при такой интерпретации не происходит размножения стрелок на рисунках. Основная идея проста: поиск по приоритету (PFS) предоставляет нам общий механизм для поиска путей в графах. С помощью алгоритма Дейкстры мы рассматриваем пути в порядке увеличения их расстояния от начальной вершины. Это упорядочение гарантирует, что, когда мы достигнем стока, будут рассмотрены все более короткие пути в графе, ни один из которых не ведет в сток. Но в эвклидовом графе мы располагаем дополнитель- |
ной информацией: если мы ищем путь из источника s в сток d и при этом проходим через третью вершину v, то мы знаем, что нам не только необходимо учесть путь, найденный из s в v, но также и то, что лучшее, на что можно рассчитывать на пути из v в d, это, во-первых, взять вес ребра v-w и затем вычислить путь, длина которого равна прямолинейному расстоянию от w до d (см. рис. 21.18). В случае приоритетного поиска мы свободно можем принять во внимание эту дополнительную информацию для повышения эффективности вычислений. Мы используем стандартный алгоритм, но в качестве приоритета для каждого ребра v-w принимаем сумму следующих трех величин: длина известного пути из s в v, вес ребра v-w, и расстояние от w до t. Если мы всегда выбираем ребро, для которого это число наименьшее, то при достижении / можем быть уверены, что в данном графе не существует более короткого пути из s в t. Кроме того, в типовых сетях мы получаем этот результат после выполнения гораздо меньшего количества попыток, чем пришлось бы сделать в алгоритме Дейкстры.
Для реализации данного подхода мы используем стандартную PFS-реализацию алгоритма Дейкстры (см. программу 21.1, а также упражнение 21.73, поскольку эвклидовы графы обычно разрежены) с двумя изменениями. Во-первых, вместо инициализации wt[s] в начале поиска значениями 0, 0 он заполняется величинами
РИСУНОК 21.18. ОСЛАБЛЕНИЕ РЕБРА (ЭВКЛИДОВО)
Когда мы вычисляем кратчайшие пути в эвклидовом графе, в операции ослабления мы можем учитывать расстояния до адресата. На этом примере мы могли бы сделать вывод, что представленный путь из s в v, плюс v-w не может привести к более короткому пути из s в d, чем уже найденный, поскольку длина любого такого пути должна быть, по крайней мере, длиной пути из s в v плюс длина v-w и плюс прямолинейное расстояние от w до d, что больше длины известного пути из s в d. Подобного рода проверки могут существенно уменьшить количество путей, которые необходимо рассмотреть.