Русская Википедия:Двунаправленный поиск
Шаблон:Rq Двунаправленный поиск пути[1][2] в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в формировании процесса поиска от начальной (прямой поиск) и от конечной вершины (обратный поиск) графа.
Идея
Нахождение искомого пути сводится к определению путей от начальной к какой-то промежуточной, а от неё к конечной вершине. Реализуется проверкой в одном или обоих процессах, когда лист одного дерева поиска совпадёт с листом другого, после чего выделяются пути до этого элемента. Соединив пути получаем искомый путь. Если два поиска осуществляются параллельно — это ещё больше экономит время на получение искомого пути по сравнению с однонаправленным поиском.
Преимущества и недостатки
- Повышенное быстродействие;
- Нужна память для хранения дерева поиска для того, чтобы можно было выполнить проверку принадлежности листа другому дереву.
Оценка сложности исполнения
Шаблон:Заготовка раздела Сложность всего алгоритма оценивается как сумма сложности прямого и обратных поисков, проверки принадлежности, равной одной операции, постоянному времени (O(n)), обращению к хеш-таблице.
Подсчёт количества операций
Слишком зависит от конкретной ситуации, если поиск осуществляется не по n-арному дереву.
Асимптотическая сложность возрастания количества операций
- Если известны единственные конкретные начальный и целевой элементы, то временная асимптотическая сложность прямого и обратного поисков равна <math>O(b^{d/2})</math>, следовательно общая — <math>O(b^{d/2})</math> + <math>O(b^{d/2})</math>, что гораздо меньше чем <math>O(b^{d})</math>. Пространственная асимптотическая сложность <math>O(b^{d/2})</math>, вместо — <math>O(1)</math> у прямого, так как нужно хранить в памяти.
- Если известны конкретный начальный элемент и набор элементов, из которого один — целевой.
Статистическая оценка
Двунаправленный поиск, при заданных единственных начальном и конечном элементах, может улучшить однонаправленный поиск в ширину, обычно, в 2 раза. Наиболее сложным случаем для двунаправленного поиска является такая задача, в которой для проверки цели дано только неявное описание некоторого (возможно очень большого) множества целевых состояний, например всех состояний, соответствующих проверки цели «Мат» в шахматах. При обратном поиске потребовалось бы создать компактные описания всех состояний, которые позволяют поставить мат с помощью ходов <math>q1, q2, q3 ...</math> и т. д. ; и эти описания нужно было бы сверять с состояниями, формируемыми при прямом поиске. Общего способа эффективного решения такой проблемы не существует.
Алгоритм двунаправленного поиска
Алгоритм состоит:
- прямого поиска, аналогичного одиночному поиску;
- обратного поиска;
- операции определения принадлежности листа другому дереву поиска.
Сложность реализации
Шаблон:Заготовка раздела Сложность реализации заключается в алгоритме обратного поиска.
Примеры реализации
Практическое применение
См. также
Примечания
Ссылки
- Алгоритмы поиска пути на pmg.org.ru
- Модели и методы решения задач на Марий Эл.ру
- Реализация на C++ (aisearch.tgz) на www.cs.cmu.edu
Литература
Шаблон:Алгоритмы поиска на графах
- ↑ Другое: двунаправленный поиск элемента — осуществляется в двунаправленных или кольцевых списках от искомого элемента в обе стороны.
- ↑ [1]Шаблон:Недоступная ссылка Этот алгоритм является полным и оптимальным (при единообразных стоимостях этапов), если оба процесса поиска осуществляются в ширину; другие сочетания методов могут характеризоваться отсутствием полноты, оптимальности или того и другого.
