Ograničena pretraga u dubinu
U računarstvu ograničena pretraga u dubinu (, 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) 
 Odredi čvor iz kojeg će početi pretraga i dodeli maksimalnu dubinu pretrage (granicu pretrage)
 Proveri da li je trenutni čvor ciljni čvor
 ako nije: ne radi ništa
 ako jeste: return
 Proveri da li se trenutni čvor nalazi u okviru granice dubine pretrage
 ako nije: ne radi ništa
 ako jeste: 
 Proširi čvor i sačuvaj svu njegovu decu na stek
 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() gde je  broj čvorova u grafu a  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, }-

Графовски алгоритми
Алгоритми претраживања
U računarstvu ograničena pretraga u dubinu ( , 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 ) Odredi čvor iz kojeg će početi pretraga i dodeli maksimalnu dubinu pretrage ( granicu pretrage ) Proveri da li je trenutni čvor ciljni čvor ako nije : ne radi ništa ako jeste : return Proveri da li se trenutni čvor nalazi u okviru granice dubine pretrage ako nije : ne radi ništa ako jeste : Proširi čvor i sačuvaj svu njegovu decu na stek Pozovi DLS rekurzivno za sve čvorove sa steka i vrati se na korak 2 Pseudokod DLS ( node , goal , depth ) { if ( depth >= ) { 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 ( ) gde je broj čvorova u grafu a 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 Artificial Intelligence : A Modern Approachd ed . ) , Upper Saddle River , New Jersey : Prentice Hall , }- Графовски алгоритми Алгоритми претраживања