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

Алгоритми пошуку графами та деревами
α–β A* B* Бахромовий Беллмана — Форда Британського музею Борувки В глибину В ширину Гілок та меж D* Двоспрямований Дейкстри Джонсона Едмондса З вертанням зворотний перехід З ітеративним заглибленням З обмеженням глибини IDA* Крускала Лексикографічний у ширину На стрибкових точках Перший-найліпший Прима Променевий SMA* Сходження на вершину Флойда — Воршелла
Переліки
Алгоритми на графах Алгоритми пошуку Список алгоритмів на графах
Пов'язані теми
Динамічне програмування Пошукова гра Пошук по графу Обхід дерева

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

Файл:Bidirectional search.PNG

Рис. 1. Схема двонаправленого пошуку. Тут він має успішно завершитися після того, як одна з гілок, що йде з початкового вузла, зустрінеться з гілкою з цільового вузла

Ідея

Нехай b — максимальний коефіцієнт розгалуження дерева пошуку та d — глибина оптимального розв'язку в дереві пошуку. Як показано на рис. 1, значення b^d/2 + b^d/2 набагато менше, ніж b^d, або, як показано на малюнку, площа двох невеликих кіл менше площі одного великого кола з центром на початку пошуку, який охоплює ціль пошуку.

Двонаправлений пошук реалізується за допомогою методу, у якому передбачається перевірка в одному або обох процесах пошуку кожного вузла перед його розгортанням для визначення того, чи не знаходиться він на периферії іншого дерева пошуку; у випадку позитивного результату перевірки рішення знайдено. Наприклад, якщо задача має рішення на глибині d = 6 і в кожному напрямку здійснюється пошук ушир із послідовним розгортанням по одному вузлу, то у найгіршому випадку ці два процеси пошуку зустрінуться, якщо у кожному з них будуть розгорнуті усі вузли на глибині 3, крім одного. Це означає, що при b = 10 буде сформована загальна кількість вузлів, рівне 22 200, а не 11 111 100, як при стандартному пошуку ушир. Перевірка належності вузла до іншого дерева пошуку може бути виконана за сталий час за допомогою хеш-таблиці, тому часова складність двонаправленого пошуку визначається як O(b^d/2). У пам'яті необхідно зберігати щонайменше одне з дерев пошуку, для того, щоб можна було виконати перевірку належності до іншого дерева, тому просторова складність також визначається як O(b^d/2). Такі вимоги до простору є одним з найістотніших недоліків двонаправленого пошуку. Цей алгоритм є повним та оптимальним (при однакових вартостях етапів), якщо обидва процеси пошуку здійснюються ушир; інші сполучення методів можуть характеризуватися відсутністю повноти, оптимальності або того та іншого.

Принцип реалізації

Двонаправлений пошук стає привабливим завдяки зменшенню часової складності, але постає питання, як організувати пошук у зворотному напрямку. Це не так легко як здається на перший погляд. Припустимо, що попередниками вузла n, що визначаються за допомогою функції Pred(n), є всі ті вузли, для яких n слугує наступником. Для двонаправленого пошуку потрібно, щоб функція визначення попередника Pred(n) була ефективно обчислюваною. Напростішим є такий випадок, коли всі дії у просторі станів оборотні таким чином, що Pred(n) = Succ^-1(n), а інші випадки можуть потребувати проявити значну винахідливість.

Розглянемо питання про те, що мається на увазі під поняттям «ціль» при пошуку «у зворотному напрямку від цілі». В задачі гри у вісім та пошуку маршруту на графі є тільки один цільовий стан, тому зворотний пошук дуже схожий на прямий пошук. Якщо ж є декілька явно перерахованих цільових станів, то може бути створений новий фіктивний цільовий стан, безпосередніми попередниками якого є всі фактичні цільові стани. Інакше, формуванню деяких надлишкових вузлів можна запобігти, розглядаючи множину цільових станів як єдиний цільовий стан, кожним з попередників якого є також множина станів, а саме, множина станів, що має відповідного наступника у множині цільових станів.

Найскладнішим випадком двонаправленого пошуку є така задача, в якій для перевірки цілі дається тільки неявний опис деякої (можливо, великої) множини цільових станів, наприклад всіх станів, що відповідають перевірці цілі «мат» у грі в шахи. При зворотному пошуку треба було б створити компактні описи «всіх станів, що дозволяють поставити мат за допомогою ходу m1» і т. д.; і ці описи треба було б звіряти зі станами, що формуються під час прямого пошуку. Загального способу ефективного рішення такої проблеми не існує.

Посилання

• Реалізація на C++ (aisearch.tgz ) на www.cs.cmu.edu

Література

• Стюарт Рассел & Питер Норвиг Часть 2. Решение проблем // Искусственный интеллект (Современный подход) = Artificial Intelligence (A Modern Approach) — 2-е изд. — ФГУП. «Печатный двор» им. А. М. Горького: Вильямс, 2006. — С. 135—136. — ISBN 5-8459-0887-6.
• de Champeaux, Dennis; Sint, Lenie (1977), «An improved bidirectional heuristic search algorithm», Journal of the ACM 24 (2): 177—191, doi:10.1145/322003.322004.
• de Champeaux, Dennis (1983), «Bidirectional heuristic search again», Journal of the ACM 30 (1): 22-32, doi:10.1145/322358.322360.
• Pohl, Ira (1971), «Bi-directional Search», in Meltzer, Bernard; Michie, Donald, Machine Intelligence, 6, Edinburgh University Press, pp. 127-140.