Metoda prohledávání do hloubky s postupným prohlubováním, Iterative depth-first search (IDFS)

Popis

Vychází z algoritmu DFS, respektive LDSF. Modifikace je taková, že parametr který udával v metodě LDFS maximální možnou hloubku zanoření není v IDFS konstantní, ale nabývá postupně hodnot od Jde tedy o opakované spouštění prostého algoritmu LDSF, kdy prohledávání LDFS je spouštěno vždy od začátku pro každý postupně narůstající parametr až do chvíle nalezení cíle či vyčerpání stavového prostoru.

Algoritmus:

1. Nastav
2. Nastav hloubku prohledávání na
3. Inicializuj množiny OPEN=[], CLOSE=[],
4. Vlož počáteční stav do OPEN.
5. Pokud je množina OPEN prázdná, ukonči algoritmus, řešení nebylo v hloubce nalezeno, jdi na bod 2. Jinak pokračuj dalším bodem.
6. Vyjmi první stav zleva z množiny OPEN a prověř, zda se nejedná o cílový stav. Pokud ano, máme řešení a algoritmus končí. V opačném případě vyjmutý stav drž v paměti a pokračuj dalším bodem.
7. Zapiš vyjmutý stav do CLOSE.
8. Prověř, zda se vyjmutý stav  nenachází v maximální přípustné hloubce Pokud ano, pokračuj bodem 5. V opačném případě pokračuj dalším bodem.
9. Prověř, expanduj vyjmutý stav generuj jeho následníky, další stavy.
10. Vlož všechny následníky stavu kteří nejsou v množině CLOSE na začátek množiny OPEN.
11. Pokračuj bodem 5.

Vlastnosti algoritmu

Pro konečné větvení b je tento algoritmus úplný. Je i optimální.

Časová složitost je exponenciální, podobně jako u BFS a DFS.

(10)

Zápis časové složitosti vlastně odpovídá tomu, že při opakovaném spouštění algoritmu DFS projdeme pro cíl v hloubce d-krát uzly první úrovně stromu, (d-1)-krát uzly další úrovně atd. Algoritmus DFS je tedy spuštěn d-krát vždy s maximální hloubkou o jedničku větší.  Reálně je často časová složitost metody IDFS lepší, než u BFS, která přidává ještě expanzi jedné vrstvy uzlů (na úrovni stromu obsahující cíl).

Prostorová složitost je lineární, naprosto stejná jako u DFS.

(11)

Výhody a nevýhody

Jedná se v případě, kdy neznáme velikost a maximální hloubku prohledávaného prostoru o obvykle nejdříve volenou neinformovanou metodu prohledávání. Kombinuje v sobě výhody metod DFS a BFS, tedy relativně nízké paměťové nároky a zejména úplnost a optimálnost. Časová složitost je jen průměrná. V praktické úloze horší než DFS, ale často lepší než BFS. Například pro a dostáváme dle vztahů Prohledávání stavového prostoru (10) a Prohledávání stavového prostoru (3) pro časovou složitost