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() 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[уреди | уреди извор]