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í podle ceny, Uniform cost search (UCS)

Popis

Jedná se o modifikaci algoritmu BFS. Tuto metodu řadíme také mezi neinformované metody, byť pro ni neplatí, že přechody mezi jednotlivými stavy jsou stejně pravděpodobné. Hrany jednotlivých přechodů v grafu jsou oproti BFS ohodnoceny různými, známými hodnotami, které vyjadřují náročnost, cenu přechodu při aplikaci daného operátoru. Procházené uzly následníků jsou uspořádávány ve frontě s prioritou podle nižší ceny přechodu k následníkovi a v tomto pořadí tedy i procházeny.

Vlastnosti algoritmu

Vlastnosti algoritmu opět odpovídají algoritmu BFS. Algoritmus je úplný a optimální pro nenulovou cenu přechodů větší než kde je konstanta.

Časová i prostorová složitost je rovna

(12)
Výhody a nevýhody

Jsou naprosto shodné jako u výchozího algoritmu BFS.

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