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

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

Алгоритм часто улучшает простой поиск в ширину тем, что запускаются два одновременных поиска в ширину из стартового и конечного узлов и останавливается, когда узел из одного фронта поиска находит соседний узел из другого фронта. Подобный поиск может улучшить простой поиск в ширину (обычно в 2 раза). Объясением почему он может быть быстрее, служит то что сложность каждого <math>O(b^{d/2})</math>, а суммарная <math>O(b^{d/2})</math> + <math>O(b^{d/2})</math>, гораздо меньше чем <math>O(b^{d})</math>. Утверждение верно только в случае, когда мы точно знаем и целевое и начальное состояние.

Наиболее сложным случаем для двунаправленного поиска является такая задача, в котором для проверки цели дано только неявное описание некоторого (возможно очень большого) множества целевых состояний, например всех состояний, соответствующих проверки цели "Мат" в шахматах. При обратном поиске потребовалось бы создать компактные описания всех состояний, которые позволяют поставить мат с помощью ходов <math>q1, q2, q3 ...</math> и т.д. ; и эти описания нужно было бы сверять с состояниями, формируемыми при прямом поиске. Общего способа эффективного решения такой проблемы не существует.

Ссылки

• Алгоритмы поиска пути на pmg.org.ru
• Модели и методы решения задач на Марий Эл.ру
• Исходный код на языке Java на googlecode.com
• Реализация на C++ (aisearch.tgz ) на www.cs.cmu.edu

Литература

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