Ограничена претрага у дубину

У рачунарству ограничена претрага у дубину (енгл. depth-limited search, ДЛС) је алгоритам за обилазак чворова у графу. То је модификација алгоритма претраге у дубину. ДЛС се користи код алгоритма Претраге у дубину итеративним продубљивањем

О алгоритму

ДЛС ради потпуно исто као и уобичајени ДФС алгоритам, али превазилази проблем комплетности увођењем границе дубине претраге. Због тога се и у случају када би алгоритам могао да прошири (проширити – погледати децу чвора) чвор изван границе дубине то неће десити, па стога не може доћи до бесконачне претраге, или до заглављивања у циклусу. Тако ће ДЛС наћи решење ако се оно налази у задатој граници дубине.

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

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)
   }
 }

Особине

Просторна сложеност

Пошто ДЛС интерно користи ДФС алгоритам за претрагу, просторна сложеност ДЛС-а је иста као и код обичног ДФС алгоритма.

Временска сложеност

Из истог разлога као и код просторне сложености, и временска сложеност ДЛС алгоритма једнака је временској сложености ДФС-а и износи ис О($\vert V\vert +\vert E\vert$) где је $\vert V\vert$ број чворова у графу а $\vert E\vert$ број претражених грана. Приметите да ДЛС не претражује цео граф већ само онај део који лежи у оквиру задате границе.

Комплетност

Иако ДЛС не може да претражује бесконачно дуге путање, нити може остати заглављен у петљи, уопштено гледано алгоритам није комплетан пошто не налази ни једно решење које се налази ван задате границе дубине претраге, али уколико се граница дубине претраге постави тако да буде већа од дубине на којој се налази решење алгоритам постаје комплетан.

Оптималност

ДЛС алгоритам није оптималан. Он и даље поседује проблем ДФС алгоритма а то је прво истражује једну путању до самог краја, због чега се може десити да се нађе решење које је скупље од неког другог решења које се налази на другој путањи.

Литература

• Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2