Metoda prohledávání do hloubky s omezenou hloubkou prohledávání, Limited depth-first search (LDFS)

Popis

Jedná se metodu principiálně naprosto shodnou s DFS, pouze je zde definována maximální hloubka povoleného zanoření algoritmu

Algoritmus:

1. Inicializuj množiny OPEN=[], CLOSE=[].
2. Vlož počáteční stav do OPEN.
3. Pokud je množina OPEN prázdná, ukonči algoritmus, řešení v maximální přípustné hloubce neexistuje. Jinak pokračuj dalším bodem.
4. 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.
5. Zapiš vyjmutý stav do CLOSE.
6. Prověř, zda se vyjmutý stav  nenachází v maximální přípustné hloubce Pokud ano, pokračuj bodem 3. V opačném případě pokračuj dalším bodem.
7. Prověř, expanduj vyjmutý stav generuj jeho následníky, další stavy.
8. Vlož všechny následníky stavu kteří nejsou v množině CLOSE na začátek množiny OPEN.
9. Pokračuj bodem 3.

Vlastnosti algoritmu

Algoritmus není úplný pro cíl ležící v hloubce vetší než je maximální povolená hloubka zanoření l. Pro tedy není úplný. Jinak ano. Optimální není.

Časová i prostorová složitost algoritmu odpovídá DFS s limitní hloubkou tedy časová složitost LDFS je

(8)

Prostorová složitost LDFS je rovna

(9)

Výhody a nevýhody

Jsou opět stejné, jako v případě DFS, LDFS pouze zajišťuje ukončení běhu algoritmu v konečném čase a nalezení řešení, které je v menší, než limitní hloubce.