Izvorni kod stranice Ograničena pretraga u dubinu

U računarstvu '''ograničena pretraga u dubinu''' ({{jez-eng-lat|depth-limited search}}, DLS) je algoritam za obilazak čvorova u grafu. To je modifikacija algoritma [[Pretraga u dubinu|pretrage u dubinu]]. '''DLS''' se koristi kod algoritma [[Pretraga u dubinu iterativnim produbljivanjem|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 ==
<syntaxhighlight lang="Python">
 DLS (node, goal, depth) {
   if (depth >= 0 ) {
     if (node == goal )
       return node
 
     for each child in expand(node)
       DLS(child, goal, depth-1)
   }
 }
</syntaxhighlight>

== 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(<math> \vert V \vert + \vert E \vert </math>) gde je <math> \vert V \vert </math> broj čvorova u grafu a <math> \vert E \vert </math> 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), [http://aima.cs.berkeley.edu Artificial Intelligence: A Modern Approach] (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, {{ISBN|0-13-790395-2}}

{{DEFAULTSORT:Ograničena pretraga u dubinu}}
[[Kategorija:Grafovski algoritmi]]
[[Kategorija:Algoritmi pretraživanja]]