Введение
Двунаправленный поиск — это алгоритм поиска в графе, который находит кратчайший путь от начальной вершины к целевой вершине в ориентированном графе. Он выполняет два одновременных поиска: один — от начального состояния вперёд, а другой — от цели назад, останавливаясь, когда они встречаются. Причина такого подхода заключается в том, что во многих случаях он быстрее: например, в упрощённой модели сложности задачи поиска, в которой оба поиска расширяют дерево с коэффициентом ветвления b, а расстояние от начала до цели равно d, сложность каждого из двух поисков составляет O(bd/2) (в нотации «Большое О»), а суммарное время этих двух поисков значительно меньше, чем сложность O(bd), которая возникла бы при однонаправленном поиске от начала до цели. Эндрю Голдберг и другие объяснили корректные условия завершения для двунаправленной версии алгоритма Дейкстры. Как и в поиске A*, двунаправленный поиск может управляться эвристической оценкой оставшегося расстояния до цели (в дереве, расширяющемся от начала) или от начала (в дереве, расширяющемся от цели). Де Шампо был первым, кто разработал и реализовал двунаправленный эвристический алгоритм поиска. Поисковые деревья, начинающиеся от начального и конечного узлов, не могли встретиться в середине пространства решений. Алгоритм BHFFA устранил этот недостаток (Champeaux, 1977). Решение, найденное однонаправленным алгоритмом A* с использованием допустимой эвристики, имеет длину кратчайшего пути; то же свойство справедливо и для двунаправленной эвристической версии BHFFA2, описанной в (de Champeaux, 1983). BHFFA2, среди прочего, имеет более строгие условия завершения, чем BHFFA.
Описание
Двунаправленный эвристический поиск — это поиск в пространстве состояний из одного состояния в другое, осуществляемый одновременно от начального состояния к конечному и от конечного к начальному. Он возвращает допустимый список операторов, применение которых к начальному состоянию приведет к конечному. Хотя может показаться, что для обратного поиска операторы должны быть обратимыми, необходимо лишь иметь возможность, для любого узла, определить набор его родительских узлов, из которых существует допустимый оператор в данный узел. Это часто сравнивают с улицей с односторонним движением в задачах поиска пути: не обязательно иметь возможность проехать по улице в обоих направлениях, но необходимо, находясь в конце улицы, определить ее начало как возможный маршрут. Аналогично, для ребер, имеющих обратные дуги (то есть дуги, идущие в обоих направлениях), необязательно, чтобы стоимость каждого направления была одинаковой. Обратный поиск всегда использует обратную стоимость (то есть стоимость дуги в прямом направлении). Более формально, если — узел с родителем , то , определяется как стоимость перехода от к . (Auer Kaindl, 2004)
While it may seem as though the operators have to be invertible for the reverse search, it is only necessary to be able to find, given any node , the set of parent nodes of such that there exists some valid operator from each of the parent nodes to This has often been likened to a one way street in the route finding domain: it is not necessary to be able to travel down both directions, but it is necessary when standing at the end of the street to determine the beginning of the street as a possible route. Similarly, for those edges that have inverse arcs (i. e. arcs going in both directions) it is not necessary that each direction be of equal cost. The reverse search will always use the inverse cost (i. e. the cost of the arc in the forward direction). More formally, if is a node with parent , then , defined as being the cost from to . (Auer Kaindl 2004)
Подходы к двунаправленному эвристическому поиску
Двунаправленные алгоритмы можно условно разделить на три категории: «фронт-фронт», «фронт-к-заднему» (или «фронт-к-концу») и поиск по периметру (Kaindl Kainz 1997). Они различаются используемой функцией для вычисления эвристики.
Передняя к задней
Алгоритмы "от фронта к тылу" вычисляют значение узла, используя эвристическую оценку расстояния между этим узлом и корнем противоположного дерева поиска. "От фронта к тылу" – наиболее активно исследуемая из трех категорий. На данный момент лучшим алгоритмом (по крайней мере, в области задачи "Пятнашки") является алгоритм BiMAX BS*F, разработанный Ауэром и Каиндлом (Auer, Kaindl 2004).
Front to Back is the most actively researched of the three categories. The current best algorithm (at least in the Fifteen puzzle domain) is the BiMAX BS*F algorithm, created by Auer and Kaindl (Auer, Kaindl 2004).
Передняя к передней
Алгоритмы Front to Front вычисляют значение h узла n, используя эвристическую оценку между n и некоторым подмножеством узлов. Каноническим примером является BHFFA (Bidirectional Heuristic Front to Front Algorithm), где функция h определяется как минимум всех эвристических оценок между текущим узлом и узлами на противоположном фронте. Или, формально:
где возвращает допустимую (т.е. не переоценивающую) эвристическую оценку расстояния между узлами n и o. Алгоритм Front to Front страдает от чрезмерных вычислительных затрат. Каждый раз, когда узел n добавляется в открытый список, его значение h должно быть пересчитано. Это требует вычисления эвристической оценки от n до каждого узла в противоположном открытом множестве, как описано выше. Открытые множества увеличиваются в размере экспоненциально для всех областей с b > 1.