Postupně se prohlubující DFS

O(b^d)

Postupně se prohlubující DFS (IDDFS) spojuje to nejlepší z BFS a DFS. Spustí hloubkově omezené DFS s limitem 0, pak 1, pak 2 a tak dál, přičemž pokaždé začne od začátku. Každé kolo používá paměť úměrnou jen aktuální hloubce (jedna cesta), jako DFS — a protože limit roste po jedné úrovni, uzly se poprvé dosáhnou ve své nejmělčí hloubce, jako u BFS. Zdánlivé plýtvání opakovaným procházením mělkých uzlů je malé: nejhlubší úroveň dominuje práci, takže celek je řádově stejný jako jedno DFS. Je to základ IDA* a hloubkově omezeného prohledávání herních stromů, používá se, když je graf obrovský či nekonečný a paměť je vzácná.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
Zásobník
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Spusť hloubkově omezené DFS s limitem 0 (jen start).
  2. Zvyš limit o jedna a spusť celé DFS znovu od startu.
  3. Každé kolo dosáhne o úroveň hlouběji; mělké uzly se procházejí znovu.
  4. Skonči, jakmile hlubší limit nepřinese žádné nové uzly — vše je nalezeno.

Pseudokód

1IDDFS(graph, start):                # O(b^d)2  for limit = 0, 1, 2, …:           # grow the depth cap3    depthLimitedDFS(start, limit)    # re-explore from scratch4    if no deeper node appeared: stop56depthLimitedDFS(node, limit):7  visit(node)8  if depth(node) < limit:9    recurse into unvisited neighbours