Pretraga u dubinu iterativnim produbljivanjem

Pretraga u dubinu iterativnim produbljivanjem (engl. Iterative deepening depth-first search, IDDFS) je strategija pretrage u kojoj se algoritam Ograničene pretrage u dubinu uzastopno upotrebljava povećavajući granicu dubine sa svakom narednom iteracijom dok ne dostigne vrednost $d$, dubinu najbližeg ciljnog stanja. IDDFS je identičan algoritmu pretrage u širinu (BFS), ali koristi mnogo manje memorije; svakom iteracijom čvorovi drveta pretrage su posećeni istim redosledom kao kod pretrage u dubinu (DFS), ali je kumulativni redosled u kojem su čvorovi prvi put posećeni kao kod BFS pretrage.

Osobine

IDDFS kombinuje prostornu efikasnost DFS algoritma i kompletnost BFS algoritma (kada je faktor grananja konačan). Optimalni rezultati se dobijaju kada je cena puta neopadajuća funkcija od dubine čvora. Prostorna složenost IDDFS je $O(bd)$, gde je $b$ faktor grananja, a $d$ je dubina najbližeg cilja. Iterativnim produbljivanjem se ista stanja posećuju više puta, što se može učiniti kao veliko rasipanje vremena, ali dolazi se do zaključka da nas to i ne košta previše, pošto se u drvetu pretrage većina čvorova nalazi u donjem nivou, tako da višestruka poseta višim nivoima nije preterano bitna. .

Kada se radi o drvetu igara (game tree) glavna prednost IDDFS algoritma je to što se u ranijoj fazi pretrage teži poboljšanju uobičajeno korišćenih heuristika, kao što su killer heuristic i alfa-beta odsecanje (alpha-beta pruning), tako da se može doći do preciznije pretpostavke rezultata različitih čvorova pri krajnjoj pretrazi u dubinu. Takođe pretraga se izvršava brže pošto je urađena u boljem redosledu. Na primer algoritam alfa-beta odsecanja je najefikasniji ukoliko prvo traži najbolje moguće poteze.

Druga prednost ovog algoritma ogleda se u njegovom odzivu. S obzirom da početne iteracije koriste male vrednosti za $d$, izvršavaju se izuzetno brzo. Ovo omogućava algoritmu da dostavi rane pretpostavke o rezultatu skoro trenutno, koje postaju sve preciznije kako se $d$ povećava. Kada se koristi u iterativnoj postavci, kao na primer u programu za šah, ova osobina omogućava programu da u bilo kom trenutku odigra trenutno najbolji dosada pronađeni potez. Ovo se može formulisati na sledeći način. Svaki nivo pretrage korekurzivno (corecursively) daje bolju aproksimaciju rešenja, iako se u svakom koraku sav posao odvija rekurzivno. Ovo nije moguće postići klasičnim DFS algoritmom, koji ne pruža momentalne rezultate. Vremenska složenost IDDFS algoritma u dobro uređenom drvetu je ista kao kod DFS algoritma $O(b^{d})$.

Prilikom pretrage iterativnim produbljivanjem, čvorovi na donjem nivou su prošireni (proširiti – pogledati decu čvora) jednom, oni na sledećem nivou dva puta i tako sve do korena drveta pretrage koje je prošireno $d+1$ puta. . Ukupan broj proširivanja pri pretrazi iterativnim produbljivanjem je

$(d+1)1+(d)b+(d-1)b^{2}+\cdots +3b^{d-2}+2b^{d-1}+b^{d}$

$\sum _{i=0}^{d}(d+1-i)b^{i}$

For $b=10$ and $d=5$ the number is

6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

Sveukupno, pretraga iterativnim produbljivanjem od nivoa 1 do nivoa $d$ proširuje samo oko 11% više čvorova nego BFS, sa faktorom grananja 1, ili ograničena pretraga u dubinu do nivoa $d$, kada je $b=10$. Čak i kada je faktor grananja 2, pretraga iterativnim produbljivanjem, traje samo dva puta duže od potpune BFS pretrage. Ovo znači da je vremenska složenost IDDFS algoritma i dalje $O(b^{d})$, a prostorna $O(d)$ kao kod običnog DFS algoritma. Generalno gledano,IDDFS bi uvek trebalo da bude prvi izbor, kada se vrše velike pretrage i kada nam dubina na kojoj se nalazi naše rešenje nije poznata.

Primer

Za sledeći graf:

DFS algoritam kreće iz čvora A. Pretpostavimo da se prvo posećuju leve grane čvorova, kao i to da pretraga pamti prethodno posećene čvorove tako da ih neće ponovo posećivati (pošto je u pitanju mali graf). Rezultat pretrage će izgledati ovako: A, B, D, F, E, C, G. Ukoliko izvršimo istu pretragu bez pamćenja prethodno posećenih čvorova rezultat je sledeći: A, B, D, F, E, A, B, D, F, E…itd, dakle dobijamo petlju A, B, D, F, E zbog koje nikada nećemo posetiti čvorove C i G.

Pretraga iterativnim produbljivanjem sprečava nastajanje ove petlje pa će čvorovi, ukoliko važi pretpostavka da se prvo posećuju leve grane pa onda desne, biti posećeni u sledećem redosledu:

• 0: A
• 1: A (ponovljeno), B, C, E

(Primetimo da se iterativnim produbljivanjem sada došlo do čvora C, dok običnim DSF-om nije.)

• 2: A, B, D, F, C, G, E, F

(Primetimo da i dalje možemo videti C ali se ono pojavljuje kasnije, takođe možemo videti da se do čvora E sada dolazi drugačijom putanjom)

• 3: A, B, D, F, E, C, G, E, F, B

Algoritam

Sledeći pseudokod predstavlja IDDFS algoritam implementiran pomoću rekurzivnog algoritma Ograničene pretrage u dubinu (depth-limited search, DLS)

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}

Algoritam Ograničene pretrage u dubinu se može rekurzivno implementirati na sledeći način. Primetite da se provera da li je nađen ciljni čvor vrši samo kada je depth == 0, jer kada je depth > 0, DLS proverava čvorove koje je posetio u prethodnim iteracijama IDDFS-a.

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

Srodni algoritmi

Sličan IDDFS algoritmu je algoritam pretrage iterativnim produžavanjem, koji radi sa granicama cene puta umesto sa granicama dubine pretrage kao IDDFS. On obilazi čvorove u takvom redosledu da cena putanje raste, pa je zato prvi ciljni čvor na koji se naiđe onaj sa najjeftinijom putanjom. Kada se porede ova dva algoritma dolazi se do zaključka da je IDDFS efikasniji od pretrage iterativnim produžavanjem. .