262
правки
Изменения
м
=Двухэтапные алгоритмы=
К сожалению, двунаправленный алгоритм Дейкстры всего в два раза быстрее обычного, а это слишком медленно. Рассмотрим алгоритм поиска кратчайшего пути, состоящий из двух этапов:
# Препроцессинг
#* запускается единожды для графа
#* может занимать много времени
#* рассчитывает некую вспомогательную информацию
# Запрос
#* может использовать данные, полученные во время препроцессинга
#* запускается по требованию для пары <tex>(s,t)</tex>
#* должен выполняться очень быстро (в реальном времени)
Можно рассмотреть в этом ключе два примера:
* Алгоритм Дейкстры: препроцессинг - ничего не делать, запрос - выполнение алгоритма Дейкстры;
* Полный перебор: препроцессинг - посчитать таблицу расстояний размером <tex>n \times n</tex> (займёт порядка 5 лет времени и 1 петабайта памяти для карты Европы), запрос - обратиться к элементу таблицы.
Оба эти примера - крайние случаи. Нам нужно нечто более гибкое: препроцессинг за часы/минуты, рост количества предпосчитанных данных линейно от размера графа и запросы в реальном времени.
Нет описания правки
На практике, такой двунаправленный поиск быстрее обычного алгоритма Дейкстры примерно в два раза.
=Алгоритм A*=
При таком выборе потенциальных функций, выполняется <tex>\forall u : h_{f}(u)+h_{r}(u)=0</tex> и тогда двунаправленный A* становится аналогичен двунаправленному алгоритму Дейкстры
=Двухэтапные алгоритмы=
К сожалению, двунаправленный алгоритм Дейкстры всего в два раза быстрее обычного, а это слишком медленно. Рассмотрим алгоритм поиска кратчайшего пути, состоящий из двух этапов:
# Препроцессинг
#* запускается единожды для графа
#* может занимать много времени
#* рассчитывает некую вспомогательную информацию
# Запрос
#* может использовать данные, полученные во время препроцессинга
#* запускается по требованию для пары <tex>(s,t)</tex>
#* должен выполняться очень быстро (в реальном времени)
Можно рассмотреть в этом ключе два примера:
* Алгоритм Дейкстры: препроцессинг - ничего не делать, запрос - выполнение алгоритма Дейкстры;
* Полный перебор: препроцессинг - посчитать таблицу расстояний размером <tex>n \times n</tex> (займёт порядка 5 лет времени и 1 петабайта памяти для карты Европы), запрос - обратиться к элементу таблицы.
Оба эти примера - крайние случаи. Нам нужно нечто более гибкое: препроцессинг за часы/минуты, рост количества предпосчитанных данных линейно от размера графа и запросы в реальном времени.
