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

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

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

Ідея

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

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