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

Алгоритмы поиска по графам и деревьям
α – β А * B * Возврат Луч Беллман – Форд Лучший первый Двунаправленный Борувка Ветвь и граница BFS британский музей D * DFS Dijkstra Эдмондс Флойд – Уоршалл Поиск бахромы скалолазание ИДА* Итеративное углубление Джонсон Точка прыжка Крускал Лексикографическая BFS LPA * Prim SMA *
Списки
Алгоритмы графа Алгоритмы поиска Список алгоритмов графа
похожие темы
Динамическое программирование Обход графа Обход дерева Искать игры Раскраска графика
v т е

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

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

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

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

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

Описание

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

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

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

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

${\ displaystyle b}$

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

${\ Displaystyle к (п, м)}$

стоимость, связанная с перемещением от узла к узлу${\ displaystyle n}$${\ displaystyle m}$

${\ Displaystyle г (п)}$

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

${\ Displaystyle ч (п)}$

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

${\ displaystyle s}$

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

${\ displaystyle t}$

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

${\ displaystyle d}$

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

${\ displaystyle d '}$

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

${\ displaystyle \ mathrm {ДЕРЕВО} _ {d}}$

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

${\ displaystyle \ mathrm {ОТКРЫТЬ} _ {d}}$

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

${\ displaystyle \ mathrm {ЗАКРЫТО} _ {d}}$

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

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

Двунаправленные алгоритмы можно в общих чертах разделить на три категории: Front-to-Front, Front-to-Back (или Front-to-End) и поиск по периметру (Kaindl Kainz 1997). Они различаются функцией, используемой для вычисления эвристики.

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

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

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

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

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

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

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

Front-to-Front страдает от чрезмерной вычислительной нагрузки. Каждый раз, когда узел n помещается в открытый список, необходимо вычислять его значение. Это включает вычисление эвристической оценки от n до каждого узла в противоположном наборе OPEN , как описано выше. В ОТКРЫТЫХ наборах увеличиваются в размерах экспоненциально для всех областей с Ь > 1 . ${\ displaystyle f = g + h}$

Рекомендации

• де Шампо, Деннис; Синт, Лени (1977), "Усовершенствованный двунаправленный эвристический алгоритм поиска", журнал в АКМ , 24 (2): 177-191, DOI : 10,1145 / 322003.322004.
• де Champeaux, Dennis (1983), "Двунаправленная эвристический поиск снова", Журнал ACM , 30 (1): 22-32, DOI : 10,1145 / 322358,322360.
• Поль, Ира (1971), «Двунаправленный поиск», у Мельцера, Бернарда; Мичи, Дональд (ред.), Machine Intelligence , 6 , Edinburgh University Press, стр. 127–140..
• Рассел, Стюарт Дж .; Норвиг, Питер (2002), "3.4 Стратегии неосведомленного поиска", Искусственный интеллект: современный подход (2-е изд.), Прентис Холл..