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

Алгоритм для реалізації обмеженого пошуку вглиб (АОПГ) (англ. 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)
  }
}

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

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

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

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

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

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

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

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.