Пошук в глибину з ітеративним заглибленням

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

Алгори́тм пошуку́ в глибину́ з ітеративним заглибленням (англ. Iterative deepening depth-first search, IDDFS) — алгоритм для обходу дерева. Цей алгоритм є розвиненням алгоритму пошуку в глибину.

Опис алгоритму

Пошук з ітеративним заглибленням (або, точніше, пошук в глибину з ітеративним заглибленням) являє собою загальну стратегію, що часто використовується в поєднанні з пошуком в глибину, яка дозволяє знайти найкращу межу глибини. В дійсності в алгоритмі пошуку в глибину існує одна проблема - вибір правильної глибини, на якій треба зупинитись. Якщо вона буде занадто малою, то розв'язок не буде знайдено; якщо занадто великою, то можливо буде марно витрачено багато часу та ресурсів. Ці проблеми вирішуються шляхом поступового збільшення межі (котра спочатку стає рівною 0, потім 1, потім 2 і так далі) до тих пір, поки не буде знайдена ціль. Така подія відбувається після того, як межа глибини досягає значення d, глибини самого поверхневого цільового вузла.

В пошуку з ітеративним заглибленням поєднуються переваги пошуку в глибину та пошуку в ширину. Як і пошук в глибину, він характеризується дуже скромними вимогами до пам'яті, а саме, значенням O(bd). Як і пошук в ширину, він є повним, якщо коефіцієнт розгалуження є скінченним, та оптимальним, якщо вартість шляху являє собою неспадну функцію глибини вузла.

Властивості алгоритму

Пошук з ітеративним заглибленням на перший погляд може здатися марнотратним, оскільки одні й ті ж самі стани формуються декілька разів (так як пошук кожного разу починається з початку). Але, як виявилося, такі повторні операції не є занадто дорогими.

Причина цього в тому, що в дереві пошуку з одним і тим самим (або майже тим самим) коефіцієнтом розгалуження на кожному рівні більшість вузлів знаходяться на нижньому рівні, тому не має великого значення те, що вузли на верхніх рівнях формуються багаторазово. В пошуку з ітеративним заглибленням вузли на нижньому рівні (з глибиною d) формуються один раз, ті вузли, що знаходяться на рівні, що передує нижньому, формуються двічі, і так далі, аж до дочірніх вузлів кореневого вузла, котрі формуються d разів. Тому загальна кількість вузлів, що формуються, виражається наступною формулою:

N(IDS) = (d)b + (d-1)b² + … + (1)b^d

яка відповідає часовій складності порядку 0(bd). Цю кількість можна порівняти з кількістю вузлів, що формуються при пошуку в ширину:

N(BFS) = b + b² + … + b^d + (b^d+1-b)

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

Наприклад, якщо b = 10 і d = 5, то відповідні оцінки кількості вузлів приймають наступні значення:

W(IDS) = 50 + 400 + 3000 + 20 000 + 100 000 = 123 450

N(BFS) = 10 + 100 + 1000 + 10 000 + 100 000 + 999 990 = 1 111 100

Взагалі кажучи, ітеративне заглиблення - це метод неінформативного пошуку, якому слід надати перевагу в тих умовах, коли наявний великий простір пошуку, а глибина розв'язку невідома.

Пошук з ітеративним заглибленням аналогічний до пошуку в ширину в тому плані, що в ньому при кожній ітерації перед переходом на наступний рівень досліджується повний рівень нових вузлів.

Приклад

Для наступного графу:

пошук в глибину, що починається з A, припускаючи що ліві вузли в графі обираються перед правими, і припускаючи що пошук пам'ятає раніше відвідані вузли і не буде проходити по них знов, буде проходити вузли в такій послідовності: A, B, D, F, E, C, G.

Використання такого ж пошуку, але не пам'ятаючи відвіданих вузлів, приведе до проходження вузлів в такому порядку: A, B, D, F, E​​, A, B, D, F, E​​, і т.д., тобто пошук потрапить до A, B, D, F , E циклу і ніколи не досягне C або G.

Пошук з ітеративним заглибленням запобігає появі такого циклу і досягає таких вузлів на таких глибинах (припускаючи що пошук відбувається зліва направо, як і вище):

• 0: A
• 1: A (повторно), B, C, E

(Зауважимо, що пошуком з ітеративним заглибленням зараз розглядається C, коли звичайний пошук в глибину цього не зробив.)

• 2: A, B, D, F, C, G, E, F

(Відзначимо що пошук тепер бачить E через інший шлях, і петлі приходять до F двічі.)

• 3: A, B, D, F, E, C, G, E, F, B

Для цього графу, якщо буде додана більша глибина, два цикли "ABFE" і "AEFB" просто стануть довшими, перш ніж алгоритм здається і намагається пройти іншу гілку.

Алгоритм

Алгоритм пошуку з ітеративним заглибленням, в якому повторно застосовується пошук з обмеженням глибини при послідовному збільшенні меж. Він завершує свою роботу після того, як знаходиться розв'язок, або процедура пошуку з обмеженням глибини повертає значення failure, а це означає, що розв'язку не існує.

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}

Пошук з обмеженням глибини може здійснюватися рекурсивно наступним чином. Зверніть увагу, що потрібно тільки перевірити чи є вузол цільовим коли глибина нульова (depth == 0), тому що коли глибина більша за нуль (depth > 0), DLS(пошук з обмеженням глибини) відкриває вузли, які він вже проходив у попередній ітерації IDDFS(пошук з ітеративним заглибленням).

DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth > 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return no-solution
}

Історія

Ітеративне чи прогресивне заглиблення вперше згадується Адріаном Де Гроотом в дисертації «Думка та вибір в шахах» (англ. Thought and choice in chess). Річард Корф про "відкриття" Пошуку в глибину з ітеративним заглибленням:

Пошук в глибину з ітеративним заглибленням був без сумніву відкритий декілька разів незалежно один від одного. Перше використання алгоритму, що було задокументовано в літературі - це в програмі "Atkin's Chess 4.5 program". Берлінер відзначав, що пошук в ширину поступається алгоритму пошуку в глибину з ітеративним заглибленням.

Споріднені алгоритми

Схожою до пошуку з ітеративним заглибленням є пошукова стратегія під назвою пошук з ітеративним подовженням. Такий пошук працює зі збільшенням(або обмеженням) вартості шляхів замість збільшення(обмеження) глибини. Він відкриває вузли в порядку зростання вартості шляху, тому першим цільовим вузлом є вузол з найдешевшою вартістю шляху. Але пошук з ітеративним подовженням несе істотні накладні витрати, що робить його менш корисним, ніж ітеративний пошук з заглибленням.

Література

Стюарт Рассел, Питер Норвиг Искусственный интеллект: современный подход. — М.: Вильямс, 2007. С. 1424. ISBN 0-13-790395-2

Див. також

• Список алгоритмів
• Пошук у ширину
• Обхід дерева