Какие алгоритмы поиска пути наиболее известны?

Некоторые известные алгоритмы поиска пути:

• Поиск в ширину (BFS, Breadth-First Search). tproger.ru Алгоритм разработан Муром и Ли для разных приложений (поиск пути в лабиринте и разводка проводников соответственно) в 1959 и 1961 годах. tproger.ru
• Алгоритм Дейкстры (Dijkstra). tproger.ru proglib.io В процессе выполнения алгоритм проверит каждую из вершин графа и найдёт кратчайший путь до исходной вершины. tproger.ru
• А* (А «со звёздочкой»). tproger.ru Впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. tproger.ru Данный алгоритм является расширением алгоритма Дейкстры, ускорение работы достигается за счёт эвристики — при рассмотрении каждой отдельной вершины переход делается в ту соседнюю вершину, предположительный путь из которой до искомой вершины самый короткий. tproger.ru
• Поиск по первому наилучшему совпадению (Best-First Search). tproger.ru Усовершенствованная версия алгоритма поиска в ширину, отличающаяся от оригинала тем, что в первую очередь развёртываются узлы, путь из которых до конечной вершины предположительно короче. tproger.ru
• IDA* (A* с итеративным углублением). tproger.ru Является изменённой версией A, использующей меньше памяти за счёт меньшего количества развёртываемых узлов. tproger.ru Работает быстрее A в случае удачного выбора эвристики. tproger.ru
• Jump Point Search. tproger.ru Самый молодой из перечисленных алгоритмов, был представлен в 2011 году. tproger.ru Представляет собой усовершенствованный A*, ускоряет поиск пути, «перепрыгивая» многие места, которые должны быть просмотрены. tproger.ru В отличие от подобных алгоритмов JPS не требует предварительной обработки и дополнительных затрат памяти. tproger.ru