Ograničena pretraga u dubinu

U računarstvu ograničena pretraga u dubinu (engl. depth-limited search, DLS) je algoritam za obilazak čvorova u grafu. To je modifikacija algoritma pretrage u dubinu. DLS se koristi kod algoritma pretrage u dubinu iterativnim produbljivanjem

O algoritmu

DLS radi potpuno isto kao i uobičajeni DFS algoritam, ali prevazilazi problem kompletnosti uvođenjem granice dubine pretrage. Zbog toga se i u slučaju kada bi algoritam mogao da proširi (proširiti – pogledati decu čvora) čvor izvan granice dubine to neće desiti, pa stoga ne može doći do beskonačne pretrage, ili do zaglavljivanja u ciklusu. Tako će DLS naći rešenje ako se ono nalazi u zadatoj granici dubine.

Algoritam (neformalni)

1. Odredi čvor iz kojeg će početi pretraga i dodeli maksimalnu dubinu pretrage (granicu pretrage)
2. Proveri da li je trenutni čvor ciljni čvor
   • ako nije: ne radi ništa
   • ako jeste: return
3. Proveri da li se trenutni čvor nalazi u okviru granice dubine pretrage
   • ako nije: ne radi ništa
   • ako jeste:
     1. Proširi čvor i sačuvaj svu njegovu decu na stek
     2. Pozovi DLS rekurzivno za sve čvorove sa steka i vrati se na korak 2

Pseudokod

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

Osobine

Prostorna složenost

Pošto DLS interno koristi DFS algoritam za pretragu, prostorna složenost DLS-a je ista kao i kod običnog DFS algoritma.

Vremenska složenost

Iz istog razloga kao i kod prostorne složenosti, i vremenska složenost DLS algoritma jednaka je vremenskoj složenosti DFS-a i iznosi is O($\vert V\vert +\vert E\vert$) gde je $\vert V\vert$ broj čvorova u grafu a $\vert E\vert$ broj pretraženih grana. Primetite da DLS ne pretražuje ceo graf već samo onaj deo koji leži u okviru zadate granice.

Kompletnost

Iako DLS ne može da pretražuje beskonačno duge putanje, niti može ostati zaglavljen u petlji, uopšteno gledano algoritam nije kompletan pošto ne nalazi ni jedno rešenje koje se nalazi van zadate granice dubine pretrage, ali ukoliko se granica dubine pretrage postavi tako da bude veća od dubine na kojoj se nalazi rešenje algoritam postaje kompletan.

Optimalnost

DLS algoritam nije optimalan. On i dalje poseduje problem DFS algoritma a to je prvo istražuje jednu putanju do samog kraja, zbog čega se može desiti da se nađe rešenje koje je skuplje od nekog drugog rešenja koje se nalazi na drugoj putanji.

Literatura

• 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