Глава 21. Кратчайшие пути. distance(s, d),где distance()есть функция, возвращающая расстояние между двумя верши­нами

distance(s, d), где distance() есть функция, возвращающая расстояние между двумя верши­нами. Во-вторых, мы определяем приоритет Р как функцию:

(wt[v] + e-> wt() + distance(w, d) - distance(v, d))

вместо функции (wt[v] + e-> wt0), которая использовалась в программе 21.1 (вспомните, что v и w — это локальные переменные, которые заполняются, соответственно, величи­нами e-> v() и e-> w()). Приведенные изменения, которые мы называем также эвклидо­вой эвристикой, поддерживают такой инвариант, как величина wt[v] - distance(v, d), яв­ляющийся длиной кратчайшего пути в сети из s в v для каждой вершины v дерева (и, следовательно, wt[v] представляет собой нижнюю границу длины возможного кратчайшего пути из s в d через v). Мы вычисляем wt[w] за счет добавления к этой величине веса (рас­стояние до w) ребра плюс расстояние от w до стока d.

Свойство 21.11. Приоритетный поиск с эвклидовой эвристикой решает задачу кратчай­ших путей источник-сток в эвклидовых графах.

Доказательство: Здесь применяется доказательство свойства 21.2. Когда мы добавляем вершину х к дереву, добавление к приоритету расстояния из х в d не влияет на дока­зательство того, что путь в дереве из s в х является кратчайшим путем в графе из s в х, поскольку к длине всех путей, ведущих в х, добавляется одна и та же величина. При добавлении d к дереву мы знаем, что никакой другой путь из s в d не короче, чем дан­ный путь в дереве, поскольку любой такой путь должен состоять из некоторого пути в дереве, за которым следует ребро, ведущее в некоторую вершину w, которая не ле­жит на дереве, и завершаться путем из w в d (длина которого не может быть короче расстояния из w в d). Однако, по построению мы знаем, что длина пути из s в w плюс расстояние из w в d не меньше, чем длина пути в дереве из s в d. ■

В разделе 21.6 мы обсудим другой простой способ реализации эвклидовой эвристики. Прежде всего, мы делаем проход по графу, изменяя вес каждого ребра: для каждого реб­ра v-w мы добавляем величину distance(w, d) - distance(v, d). Затем мы выполняем стан­дартный алгоритм поиска кратчайшего пути, начиная с s (с wt[s], инициализированного значениями distance(s, d)), и останавливаемся по достижении d. Этот метод в вычислитель­ном отношении эквивалентен уже описанному методу (который в принципе по ходу вы­числений считает те же веса) и является типовым примером базовой операции, известной как повторное взвешивание (reweighting) сети. Повторное взвешивание играет существенную роль при решении задач поиска кратчайших путей с отрицательными весами; мы обсу­дим его подробно в разделе 21.6.

Эвклидова эвристика оказывает влияние на эффективность, но не на правильность алгоритма Дейкстры для вычисления кратчайших путей в модели источник-сток. Как го­ворилось в доказательстве свойства 21.2, применение стандартного алгоритма для реше­ния задачи источник-сток означает построение SPT, в котором все вершины ближе к на­чалу, чем сток d. При использовании эвклидовой эвристики SPT содержит только те вершины, для которых длина пути из s плюс расстояние до d меньше, чем длина кратчай­шего пути из s в d. Мы полагаем, что это дерево будет существенно меньшим для мно­гих приложений, поскольку при данной эвристике отбрасывается значительное число длинных путей. Точная экономия зависит от структуры графа и геометрии расположения вершин. На рис. 21.19 показано действие эвклидовой эвристики на нашем типовом гра­фе, когда достигается существенная экономия. Мы называем этот метод эвристическим,

Часть 5. Алгоритмы на графах

поскольку нет гарантии, что какая-либо экономия вообще будет иметь место: всегда возможен случай, когда имеется единственный достаточно длинный путь из источника в сток, который перед возвратом в сток отклонится произ­вольно далеко в сторону от источника (см. упражнение 21.80).

Рисунок 21.20 иллюстрирует интуитивное описание ба­зовой геометрии, лежащей в основе эвклидовой эвристики: если длина кратчайшего пути из s в d есть z, то вершины, просматриваемые этим алгоритмом, лежат в основном внутри эллипса, определяемого как местоположение тех точек х, для которых расстояние от s до х плюс расстояние от х до d равняется zДля типовых эвклидовых графов мы ожидаем, что количество вершин в этом эллипсе намного меньше, чем количество вершин в круге радиуса z с цент­ром в источнике (тех, которые должны просматриваться алгоритмом Дейкстры).

Строгий анализ получаемой экономии является трудной аналитической задачей и зависит как от конфигурации на­боров случайных точек, так и от вида случайных графов {см. раздел ссыпок). Для типовых ситуаций мы ожидаем, что если в стандартном алгоритме при вычислении кратчайше­го пути источник-сток рассматривается X вершин, то эвк­лидова эвристика сократит расход ресурсов, доведя его до величины, пропорциональной √ X, что приведет ожидае­мое время выполнения к величине, пропорциональной V для насыщенных и √ Y — для разреженных графов. Этот пример показывает, что трудность разработки подходящей модели или анализ связанных с нею алгоритмов ни в коем случае не должны разубеждать нас от использования пре­имуществ существенной экономии, которая будет дости­гаться во многих приложениях, особенно, когда реализа­ция тривиальна.

Доказательство свойства 21.11 применимо в отношении любой функции, которая дает нижнюю границу расстояния от каждой вершины до d. Существуют ли другие функции, для которых алгоритм будет рассматривать даже меньше вершин, чем с использованием эвклидовой эвристики? Этот вопрос изучался в общей постановке применительно к широкому классу алгоритмов комбинаторного поиска.

Действительно, эвклидова эвристика является характерным примером алгоритма, назы­ваемого А* (произносится " эй-стар"). Из теории известно, что оптимальным будет исполь­зование функции, дающей наилучшую возможную нижнюю границу; другими словами, чем лучше эта граничная функция, тем более эффективным окажется поиск. В данном случае оптимальность А* говорит о том, что при использовании эвклидовой эвристики,

Глава 21. Кратчайшие пути

несомненно, будет просматриваться не больше вершин, чем в случае алгоритма Дейкстры (который представля­ет собой А* с нулевой нижней границей). Результаты ана­литических исследований дают более точную информа­цию для конкретных сетевых моделей.

Свойства эвклидовых сетей можно также использовать и для построения абстрактных АТД поиска кратчайших путей, более эффективно реализующих компромисс меж­ду используемым временем и пространством, нежели для сетей общего вида (см. упражнения 21.48-21.50). Такие алгоритмы важны в приложениях, подобных обработке карт, где сети огромны и разрежены. Например, предпо­ложим, что требуется разработать навигационную систе­му, определяющую кратчайшие пути на карте с милли­онами дорог. Возможно, хотелось бы хранить карту непосредственно в малом бортовом компьютере, однако расстояния и матрицы путей зачастую слишком велики, чтобы их можно было втиснуть в память (см. упражнения 21.39 и 21.40); следовательно, алгоритмы для поиска всех путей из раздела 21.3 не применимы. Алгоритм Дейкстры также не может дать ответа за достаточно короткое вре­мя для случая огромных карт. Упражнения 21.77 и 21.78 исследуют стратегии рационального соотношения между

РИСУНОК 21.20. ЭВКЛИДОВА ЭВРИСТИКА И ГРАНИЦЫ СТОИМОСТИ

Когда нам нужно отыскать кратчайший путь в вершину-адресат, при поиске мы можем ограничиться вершинами внутри эллипса, описанного вокруг пути, вместо круга с центром в s, что требовалось бы в алгорит­ме Дейкстры. Радиус круга и форма эллипса определяются длиной кратчайшего пути.

Часть 5. Алгоритмы на графах