Двунаправленный поиск

Двунаправленный поиск – это алгоритм поиска, который находит расстояние от исходной точки до конечной точки в ориентированном графе. Алгоритм запускает 2 одновременных поиск: от начальной точки к конечной и от конечной точки к начальной. Алгоритм заканчивает свою работу, когда оба поиска приходят в одну точку. Т.к. прямой и обратный поиск могут быть выполнены параллельно друг с другом в разных потоках приложения, чисто теоретически, это позволяет получить двукратное уменьшение времени затрачиваемого на поиск. Однако на практике существует ряд дополнительных проблем, которые связаны с таким ускорением алгоритма. Алгоритм двунаправленный поиска должен содержать дополнительную логику, которая будет принимать решение по какой из дуг перейти на следующем шаге. От этого выбора сильно зависит успешность алгоритма. Конечная точка должна быть жёстко задана, но на практике часто возникает необходимость задать конечную точку какими либо параметрами, в этом случае алгоритм двунаправленного поиска в исходном виде не применим. Алгоритм двунаправленного поиска так же должен включать логику, которая будет эффективно определять пересечение двух деревьев поиска для нахождения общей точки, что сильно осложняет реализацию, особенно учитывая тот факт, что коэффициент ветвления обратного поиска может отличаться от коэффициента ветвления прямого поиска.

Такая сложность реализации наталкивает на мысль, что алгоритм поиска A* является лучшим решением в случае если мы может определить эффективную эвристическую функцию.

Однако, не смотря на все сложности реализации алгоритм двунаправленного поиска, зачастую работает эффективней, чем алгоритм A*. Тесты Иры Поль, проведённые на 15 элементной мозаике, показали, что алгоритм двунаправленного поиска позволяет найти кратчайшие пути по сравнению с алгоритмом A*, когда эвристическая функция подобрана не достаточно хорошо. К тому же, существует множество ситуаций когда алгоритм А* требует намного больше ресурсов компьютера для успешного завершения.