Slovník | Vyhledávání | Mapa webu
 
Analýza a hodnocení biologických datUmělá inteligence Prohledávání stavového prostoru Metody prohledávání Neinformované prohledávání

Logo Matematická biologie

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.

 
vytvořil Institut biostatistiky a analýz Masarykovy univerzity | | zpětné odkazy | validní XHTML 1.0 Strict