Перегляд вихідного коду сторінки Пошук з обмеженням глибини

{{Алгоритми пошуку графами}}

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

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

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

== Алгоритм (неформальний) ==
# Визначити вершину, з якої слід починати пошук, і призначити максимальну глибину пошуку
# Перевірити, чи є поточна вершина цільовим станом
#* Якщо не є цільовим станом: Нічого не робити
#* Якщо є цільовим станом: Повернути поточну вершину
# Перевірити, чи знаходиться поточна вершина в межах максимальної глибини пошуку
#* Якщо поточна вершина знаходиться поза межею максимальної глибини пошуку: Нічого не робити
#* Якщо поточна вершина знаходиться в межах максимальної глибини пошуку:
#*# Розгорнути вершину і додати усі дочірні вершини до [[Стек|стеку]]
#*# Викликати пошук з обмеженням глибини для всіх вершин стеку і повернутися до кроку 2

== Псевдокод ==

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

== Властивості ==

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

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

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

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

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

== Література ==
* ''Стюарт Рассел, Питер Норвиг'' Искусственный интеллект: современный подход.&nbsp;— М.: Вильямс, 2007. С. 1424. ISBN 978-5-8459-0887-2 {{ref-ru}}, ISBN 0-13-790395-2 {{ref-en}}
* [http://window.edu.ru/resource/274/69274/files/itmo443.pdf ''И.&nbsp;А.&nbsp;Бессмертный.'' Искусственный интеллект]&nbsp;— СПб: СПбГУ ИТМО, 2010.&nbsp;— 132 с. {{ref-ru}}
* [https://web.archive.org/web/20160419205030/http://36.msiu.ru/books/14 Основы искусственного интеллекта: учебно-методическое по-собие / Н.&nbsp;В.&nbsp;Лукьянова, Д.&nbsp;Ю.&nbsp;Куприянов, Н.&nbsp;А.&nbsp;Роганова.]&nbsp;— М.: МГИУ, 2012.&nbsp;— 92 с. {{ref-ru}}
* [http://elib.bsu.by/bitstream/123456789/7689/14/Лекция%2014.doc Стратегія неінформаційного пошуку, лекція] {{ref-ru}}

== Див. також ==
* [[Список алгоритмів]]
* [[Пошук у глибину]]
* [[Обхід дерева]]

{{Algorithms-stub}}

[[Категорія:Алгоритми пошуку]]
[[Категорія:Алгоритми на графах]]