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

Двунаправленный поиск — это алгоритм поиска в графе , который находит кратчайший путь от начальной вершины до целевой вершины в ориентированном графе . Он выполняет два одновременных поиска: один вперед от исходного состояния и один назад от цели, останавливаясь, когда они встречаются. Причина такого подхода в том, что во многих случаях он быстрее: например, в упрощенной модели сложности задачи поиска, в которой оба поиска расширяют дерево с коэффициентом ветвления b , а расстояние от начала до цели равно d , каждый из два поиска имеют сложность O ( b ^{д /2} ) (в нотации Big O ), а сумма этих двух времен поиска намного меньше, чем O ( b ^д ) сложность, которая может возникнуть в результате одного поиска от начала до цели.

Эндрю Голдберг и другие объяснили правильные условия завершения двунаправленной версии алгоритма Дейкстры .

Как и в поиске A* , двунаправленный поиск может руководствоваться эвристической оценкой оставшегося расстояния до цели (в прямом дереве) или от начала (в обратном дереве).

Айра Пол ( 1971 ) был первым, кто разработал и реализовал двунаправленный эвристический алгоритм поиска. Деревья поиска, исходящие из начального и целевого узлов, не смогли встретиться в середине пространства решений. Алгоритм BHFFA исправил этот дефект Шампо (1977).

Решение, найденное однонаправленным алгоритмом A* с использованием допустимой эвристики, имеет кратчайшую длину пути; то же самое свойство справедливо и для двунаправленной эвристической версии BHFFA2, описанной де Шампо (1983). BHFFA2 имеет, среди прочего, более строгие условия завершения, чем BHFFA.

Описание

Двунаправленный эвристический поиск — это поиск в пространстве состояний из некоторого состояния. $s$ в другое государство $t$, поиск из $s$ к $t$ и из $t$ к $s$ одновременно. Он возвращает действительный список операторов, к которым при применении $s$ даст нам $t$.

Хотя может показаться, что для обратного поиска операторы должны быть обратимыми, необходимо лишь иметь возможность найти по любому узлу $n$, набор родительских узлов $n$ такой, что существует некоторый допустимый оператор от каждого из родительских узлов к $n$. В области поиска маршрута это часто сравнивают с улицей с односторонним движением: не обязательно иметь возможность ехать в обоих направлениях, но необходимо, стоя в конце улицы, определить начало улицы. как возможный маршрут.

Аналогично, для тех ребер, которые имеют обратные дуги (т.е. дуги, идущие в обоих направлениях), не обязательно, чтобы каждое направление имело одинаковую стоимость. При обратном поиске всегда будет использоваться обратная стоимость (т.е. стоимость дуги в прямом направлении). Более формально, если $n$ это узел с родителем $p$, затем $k_{1}(p,n)=k_{2}(n,p)$, определяемый как стоимость от $p$ к $n$.(Ауэр Кайндл 2004)

Терминология и обозначения

$b$

коэффициент ветвления дерева поиска

$k(n,m)$

стоимость, связанная с переездом из узла $n$ узел $m$

$g(n)$

стоимость от корня до узла $n$

$h(n)$

эвристическая оценка расстояния между узлами $n$ и цель

$s$

начальное состояние

$t$

состояние цели (иногда $g$, не путать с функцией)

$d$

текущее направление поиска. По соглашению, $d$ равно 1 для прямого направления и 2 для обратного направления (Kwa 1989)

$d'$

противоположное направление поиска (т.е. $d'=3-d$)

$\mathrm {TREE} _{d}$

дерево поиска в направлении d. Если $d=1$, корень $s$, если $d=2$, корень $t$

$\mathrm {OPEN} _{d}$

листья $\mathrm {TREE} _{d}$ (иногда называемый $\mathrm {FRINGE} _{d}$). Именно из этого набора выбирается узел для расширения. В двунаправленном поиске их иногда называют «границами поиска» или «волновыми фронтами», имея в виду, как они выглядят, когда поиск представлен графически. В этой метафоре «столкновение» происходит, когда во время фазы расширения обнаруживается, что узел одного волнового фронта имеет преемников на противоположном волновом фронте.

$\mathrm {CLOSED} _{d}$

нелистовые узлы $\mathrm {TREE} _{d}$. Этот набор содержит узлы, уже посещенные поиском.

Подходы к двунаправленному эвристическому поиску

Двунаправленные алгоритмы можно условно разделить на три категории: «Вперед-вперед», «Вперед-назад» (или «Вперед-к-концу») и поиск по периметру (Каиндл Кайнц, 1997). Они различаются функцией, используемой для расчета эвристики.

Спереди назад

Алгоритмы Front-to-Back рассчитывают $h$ значение узла $n$ используя эвристическую оценку между $n$ и корень противоположного дерева поиска, $s$ или $t$.

«Спереди назад» — наиболее активно исследуемая из трех категорий. На данный момент лучшим алгоритмом (по крайней мере, в области головоломок «Пятнадцать ») является алгоритм BiMAX-BS*F, созданный Ауером и Кайндлом (Auer, Kaindl 2004).

Спереди вперед

Алгоритмы Front-to-Front вычисляют значение h узла n, используя эвристическую оценку между n и некоторым подмножеством узлов. $\mathrm {OPEN} _{d'}$. Каноническим примером является BHFFA ( двунаправленный эвристический фронт-фронтальный алгоритм ), где функция h определяется как минимум всех эвристических оценок между текущим узлом и узлами на противоположном фронте. Или формально:

$h_{d}(n)=\min _{i}\left\{H(n,o_{i})|o_{i}\in \mathrm {OPEN} _{d'}\right\}$

где $H(n,o)$ возвращает допустимую (т.е. не завышенную) эвристическую оценку расстояния между узлами n и o .

Метод Front-to-Front страдает от чрезмерных вычислительных затрат. Каждый раз, когда узел n помещается в открытый список, его $f=g+h$ стоимость необходимо рассчитать. Это включает в себя вычисление эвристической оценки от n до каждого узла в противоположном множестве OPEN , как описано выше. Наборы OPEN увеличиваются в размерах экспоненциально для всех доменов с b > 1 .

Ссылки

• де Шампо, Деннис; Синт, Лени (1977), «Улучшенный двунаправленный эвристический алгоритм поиска», Journal of the ACM , 24 (2): 177–191, doi : 10.1145/322003.322004 .
• де Шампо, Деннис (1983), «Снова двунаправленный эвристический поиск», Журнал ACM , 30 (1): 22–32, doi : 10.1145/322358.322360 .
• Поль, Ира (1971), «Двунаправленный поиск», Мельцер, Бернард; Мичи, Дональд (ред.), Machine Intelligence , vol. 6, Издательство Эдинбургского университета, стр. 127–140 .
• Рассел, Стюарт Дж .; Норвиг, Питер (2002), «3.4 Стратегии неинформированного поиска», Искусственный интеллект: современный подход (2-е изд.), Прентис Холл .