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 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)Prohledávání stavového prostoru (3) pro časovou složitost

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