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

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

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

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

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