![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 21. Кратчайшие пути. 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. Алгоритмы на графах
21.74. Выполните эмпирические исследования с целью проверки эффективности эв 21.75. Разработайте реализацию класса для задачи поиска кратчайших путей источник- о 21.76. Воспользуйтесь геометрической интерпретацией для получения оценки отношения количества вершин в SPT, создаваемых алгоритмом Дейкстры для задачи источник-сток, к количеству вершин в SPT, создаваемых двунаправленной версией, описанной в упражнении 21.75. 21.77. Разработайте реализацию класса для поиска кратчайших путей в эвклидовых 21.78. Разработайте реализацию АТД поиска кратчайших путей для всех пар для эвк 21.79. Выполните эмпирические исследования с целью сравнения эффективности эв 21.80. Расширьте эмпирические исследования, включив в них эвклидовы графы, ко 21.81. Постройте прямую реализацию алгоритма Флойда с АТД сети для неявных эв 21.82. Разработайте реализацию для сценария, описанного в упражнении 21.81, ког
|