Пошук з обмеженням глибини

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

Алгоритм для реалізації обмеженого пошуку вглиб (АОПГ) (англ. Depth-limited search, DLS) — алгоритм для обходу дерева. Він застосовується в таких алгоритмах, як алгоритм топологічного сортування, алгоритм пошуку сильно зв'язаних компонентів. Цей алгоритм є модифікацією алгоритму пошуку в глибину.

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

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

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

Алгоритм (неформальний)

1. Визначити вершину, з якої слід починати пошук, і призначити максимальну глибину пошуку
2. Перевірити, чи є поточна вершина цільовим станом
   • Якщо не є цільовим станом: Нічого не робити
   • Якщо є цільовим станом: Повернути поточну вершину
3. Перевірити, чи знаходиться поточна вершина в межах максимальної глибини пошуку
   • Якщо поточна вершина знаходиться поза межею максимальної глибини пошуку: Нічого не робити
   • Якщо поточна вершина знаходиться в межах максимальної глибини пошуку:
     1. Розгорнути вершину і додати усі дочірні вершини до стеку
     2. Викликати пошук з обмеженням глибини для всіх вершин стеку і повернутися до кроку 2

Псевдокод

DLS(node, goal, depth) {
  if ( depth >= 0 ) {
    if ( node == goal )
      return node

    for each child in expand(node)
      DLS(child, goal, depth-1)
  }
}

Властивості

Просторова складність

Оскільки пошук з обмеженням глибини використовує пошук в глибину, то просторова [[Обчислювальна складність|складність] еквівалентна складності звичайного пошуку в глибину і вона складає $O(|V|)$. Ємкісна складність — O (b * L) .

Часова складність

Оскільки пошук з обмеженням глибини використовує пошук в глибину, то часова складність еквівалентна складності звичайного пошуку в глибину і вона складає O($\vert V\vert +\vert E\vert$), де $\vert V\vert$ — кількість вершин, $\vert E\vert$ — кількість ребер в досліджуваному графі. Зверніть увагу, що пошук з обмеженням глибини досліджує не весь граф, а тільки ту частину, яка розташована в межах вказаної глибини.

Повнота

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

Оптимальність

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

Недоліки алгоритму

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

Література

• Стюарт Рассел, Питер Норвиг Искусственный интеллект: современный подход. — М.: Вильямс, 2007. С. 1424. ISBN 978-5-8459-0887-2 (рос.), ISBN 0-13-790395-2 (англ.)
• И. А. Бессмертный. Искусственный интеллект — СПб: СПбГУ ИТМО, 2010. — 132 с. (рос.)
• Основы искусственного интеллекта: учебно-методическое по-собие / Н. В. Лукьянова, Д. Ю. Куприянов, Н. А. Роганова. — М.: МГИУ, 2012. — 92 с. (рос.)
• Стратегія неінформаційного пошуку, лекція (рос.)

Див. також

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