251
правка
Изменения
м
→Двухэтапные алгоритмы
К сожалению, двунаправленный алгоритм Дейкстры всего в два раза быстрее обычного, а это слишком медленно. Рассмотрим алгоритм поиска кратчайшего пути, состоящий из двух этапов:
# Препроцессинг:#* запускается единожды для графа,#* может занимать много времени,#* рассчитывает некую вспомогательную информацию.# Запрос:#* может использовать данные, полученные во время препроцессинга,#* запускается по требованию для пары <tex>(s,t)</tex>,#* должен выполняться очень быстро (в реальном времени).
Можно рассмотреть в этом ключе два примера:
Аббревиатура ALT расшифровывается как <b>A</b>* +<b>L</b>andmarks + <b>T</b>riangle inequality : A* + ориентиры + неравенство треугольника.
#Препроцессинг:#* взять небольшое количество вершин (например, 16), обозначив их как <b>ориентиры</b> (англ. ''landmarks''),#* для каждого из ориентиров посчитать кратчайшие пути до <b>всех</b> вершин,#* сохранить эти пути. #Запрос:#* используем A*,#* если некоторое ребро находится на кратчайшем пути между исходной точкой и ориентиром — по нему идём в первую очередь.
[[Файл:ALT.jpg|right|frame|рис. 1]]
Будем использовать неравенство треугольника для нижних оценок пути (см. рис. 1). Пусть <tex>A</tex> — один из ориентиров, тогда:
*<tex>dist(v,w)\ge dist(A,w)-dist(A,v)</tex>,*<tex>dist(v,w)\ge dist(v,A)-dist(w,A)</tex>,*<tex>dist(v,w)\ge \max\{dist(A,w)-dist(A,v),dist(v,A)-dist(w,A)\}</tex>.
Эта эвристика хорошо работает, на дорожных графах, для которых верно следующее: как правило, кратчайший путь затрагивает небольшое количество локальных дорог, потом крупную автомагистраль и снова некоторое количество локальных дорог.
Сложности в выборе ориентиров:
* хороший ориентир для запроса <tex>s \rightsquigarrow t</tex> должен находиться "до" <tex>s</tex> (точно не будет общих рёбер на кратчайшем пути) или "за" <tex>t</tex> (чем острее угол, тем меньше отклонение от предварительно посчитанного кратчайшего пути до искомого),* Нам нам нужно выбрать такие ориентиры, которые будут неплохими для всех запросов.
Выглядит логичным выбирать ориентиры на краю дорожной сети, тогда будет больше острых углов и ориентиры будут лучше.
====Плоскостной (planar)====
* разделим Разделим карту на <tex>k</tex> секторов одинаковой площади,* возьмём ориентиром наиболее удалённую точку от центра в каждом секторе.
Такой способ подходит, только если граф имеет относительно правильную форму. На практике обычно используется оптимизированная версия этого алгоритма.
[[Файл:reach1.jpg|right]]
Заметим, что вершины с большим охватом находятся вблизи середины некоторого длинного кратчайшего пути, то есть
* на больших автомагистралях вершины имеют большой охват,* на локальных перекрёстках (внутри населённых пунктов) вершины имеют маленький охват.
Во время обработки ребра <tex>(v,w)</tex>:
* удалим вершину <tex>w</tex>, если <tex>r(w)<\min\{d(s,v)+\ell(v,w), LB(w,t)\}</tex>,
* оценка <tex>LB(w,t)</tex> должна быть подобрана таким образом, чтобы, если бы <tex>P=(s,..,v,w,...,t)</tex> было кратчайшим путём, <tex>r(w)</tex> было бы больше.
[[Файл:reach2.jpg|right]]
Как искать нижнюю оценку длины пути <tex>LB(w,t)</tex>?
* Явно: Евклидово расстояние, с помощью ориентиров.* Неявно: сделать поиск двунаправленным.
Например, радиус <tex>R_{t}</tex> поиска в обратную сторону может быть нижней оценкой, т.к. если вершина <tex>w</tex> не была посещена поиском в обратную сторону, то <tex>d(w,t)\geq R_{t}</tex>
[[Файл:reach3.jpg|right]]
* на начальном этапе <tex>\forall v: r(v)\leftarrow 0</tex>,* для каждой вершины <tex>s \in V</tex> рассмотрим дерево кратчайших путей до всех других вершин <tex>T_{s}</tex>. , **найдём наиболее длинный путь <tex>P_{s\rightsquigarrow t}</tex>, содержащий <tex>v</tex>. , **Назовём глубиной вершины <tex>d_{s}(v)</tex> расстояние от <tex>s</tex>, высотой вершины <tex>h_{s}(v)</tex> — расстояние до наиболее далёкого потомка вершины,** Тогда, охватом вершины в этом дереве будет величина <tex>r_{s}(v) = \min\{d_{s}(v),h_{s}(v)\}</tex>,** Тогда обновим значение охвата <tex>r(v) \leftarrow \max\{r(v),r_{s}(v)\}</tex>.
Сложность алгоритма: <tex>O(nm)</tex>, поэтому он слишком медленный для больших графов и его нужно улучшить.
Назовём кратчайший путь <tex>P_{s\rightsquigarrow t} = (s, s',...,v,...,t',t)</tex> <tex>\varepsilon</tex>-минимальным, если выполняются условия
*<tex>dist(s,v)\geq\varepsilon</tex>,*<tex>dist(s',v)\textless\varepsilon</tex>,*<tex>dist(v,t)\geq\varepsilon</tex>,*<tex>dist(v,t')\textless\varepsilon</tex>.
Таким образом, алгоритм будет выглядеть так:
*найдём оценку охвата <tex>r'(v)</tex>, используя только <tex>\varepsilon</tex> — минимальные пути,* если <tex>r'(v)<\varepsilon</tex>, то оценка корректна: <tex>r(v)=r'(v)</tex>,* если же <tex>r'(v)\geq \varepsilon</tex>, то она нас не интересует: <tex>r(v)\geq r'(v)</tex>.
Полезно будет рассматривать <b>частично обработанные деревья</b> (англ. ''partial trees'') — деревья кратчайших путей, хранящие пути длиной, меньшей определённого порога. Тогда дерево кратчайших путей будет глубиной порядка <tex>2\varepsilon</tex>:
* Установим установим <tex>G'\leftarrow G</tex> и <tex>\varepsilon\leftarrow \varepsilon_{0}</tex> (маленькое число),* Пока пока <tex>G'</tex> не пусто:** найдём частично обработанное дерево кратчайших путей из <tex>v</tex>, чтобы найти вершины с охватом <tex>r(v) \geq \varepsilon</tex>,** удалим из <tex>G'</tex> оставшиеся вершины (с охватом <tex>r(v) \textless\varepsilon</tex>, уже обработанные),** установим <tex>\varepsilon\leftarrow 3\varepsilon</tex>.
[[Файл:reach5.jpg|right]]
[[Файл:reach6.jpg|right]]
На этом шаге мы будем искать <b>пропускаемые</b> (англ. ''bypassable'') вершины. Назовём вершину <tex>v</tex> пропускаемой, если выполняется одно из двух условий:
* <tex>v</tex> имеет только одно входящее ребро <tex>(u,v)</tex> и одно исходящее ребро <tex>(v,w)</tex> ,* <tex>v</tex> имеет два входящих ребра <tex>(u,v)</tex>, <tex>(w,v)</tex> и два исходящих ребра <tex>(v,w)</tex> ,<tex>(v,u)</tex>.
В обоих случаях подразумевается, что <tex>u\neq w</tex>, то есть у <tex>v</tex> обязательно есть только два соседа. В первом случае, <tex>v</tex> — кандидат на односторонний пропуск (англ. ''one-way bypass''), во втором — на двухсторонний (англ. ''two-way bypass''). Мы будем использовать сокращающие рёбра, чтобы пропускать такие вершины.
Такую же процедуру можно проделать с двусторонней линией, т.к. помимо оценок, указанных выше, можно добавить:
* <tex>\overline{r}(w,v)=\ell(w,v)+out\textrm{-}penalty(v)</tex>,* <tex>\overline{r}(v,u)=\ell(v,u)+in\textrm{-}penalty(v)</tex>.
====Фаза отладки====
