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:
- Inicializuj množiny OPEN=[], CLOSE=[].
- Vlož počáteční stav do OPEN.
- 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.
- 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.
- Zapiš vyjmutý stav do CLOSE.
- 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.
- Prověř, expanduj vyjmutý stav generuj jeho následníky, další stavy.
- Vlož všechny následníky stavu kteří nejsou v množině CLOSE na začátek množiny OPEN.
- 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.