Двунаправленный поиск пути в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину ), идея которого заключается в формировании процесса поиска от начальной ( прямой поиск ) и от конечной вершины ( обратный поиск ) графа .

Идея

Нахождение искомого пути сводится к определению путей от начальной к какой-то промежуточной, а от неё к конечной вершине. Реализуется проверкой в одном или обоих процессах, когда лист одного дерева поиска совпадёт с листом другого, после чего выделяются пути до этого элемента. Соединив пути получаем искомый путь. Если два поиска осуществляются параллельно — это ещё больше экономит время на получение искомого пути по сравнению с однонаправленным поиском.

Преимущества и недостатки

• Повышенное быстродействие;
• Нужна память для хранения дерева поиска для того, чтобы можно было выполнить проверку принадлежности листа другому дереву.

Оценка сложности исполнения

Этот раздел не завершён . Вы поможете проекту, исправив и дополнив его.

Сложность всего алгоритма оценивается как сумма сложности прямого и обратных поисков, проверки принадлежности, равной одной операции, постоянному времени (O(n)), обращению к хеш-таблице .

Подсчёт количества операций

Слишком зависит от конкретной ситуации, если поиск осуществляется не по n-арному дереву .

Асимптотическая сложность возрастания количества операций

• Если известны единственные конкретные начальный и целевой элементы, то временная асимптотическая сложность прямого и обратного поисков равна ${\displaystyle O(b^{d/2})}$ , следовательно общая — ${\displaystyle O(b^{d/2})}$ + ${\displaystyle O(b^{d/2})}$ , что гораздо меньше чем ${\displaystyle O(b^{d})}$ . Пространственная асимптотическая сложность ${\displaystyle O(b^{d/2})}$ , вместо — ${\displaystyle O(1)}$ у прямого, так как нужно хранить в памяти.
• Если известны конкретный начальный элемент и набор элементов, из которого один — целевой.

Статистическая оценка

Двунаправленный поиск, при заданных единственных начальном и конечном элементах, может улучшить однонаправленный поиск в ширину, обычно, в 2 раза. Наиболее сложным случаем для двунаправленного поиска является такая задача, в которой для проверки цели дано только неявное описание некоторого (возможно очень большого) множества целевых состояний, например всех состояний, соответствующих проверки цели «Мат» в шахматах . При обратном поиске потребовалось бы создать компактные описания всех состояний, которые позволяют поставить мат с помощью ходов ${\displaystyle q1,q2,q3...}$ и т. д. ; и эти описания нужно было бы сверять с состояниями, формируемыми при прямом поиске. Общего способа эффективного решения такой проблемы не существует.

Алгоритм двунаправленного поиска

Алгоритм состоит:

• прямого поиска, аналогичного одиночному поиску;
• обратного поиска;
• операции определения принадлежности листа другому дереву поиска.

Сложность реализации

Этот раздел не завершён . Вы поможете проекту, исправив и дополнив его.

Сложность реализации заключается в алгоритме обратного поиска.

Примеры реализации

Этот раздел не завершён . Вы поможете проекту, исправив и дополнив его.

Практическое применение

Этот раздел не завершён . Вы поможете проекту, исправив и дополнив его.

См. также

• Поиск в ширину
• Поиск в глубину

Примечания

Ссылки

• на pmg.org.ru
• на Марий Эл.ру
• на www.cs.cmu.edu

Литература

• Стюарт Рассел & Питер Норвиг. Часть 2. Решение проблем // Искусственный интеллект (Современный подход) = Artificial Intelligence (A Modern Approach). — 2-е изд. — ФГУП. "Печатный двор" им. А.М.Горького: Вильямс, 2006. — С. 135-136. — ISBN 5-8459-0887-6 .