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.