Uspořádané prohledávání

Uspořádané prohledávání (anglicky ) je jeden z algoritmů na prohledávání stavového prostoru. Na rozdíl od prohledávání do hloubky, které vždy pokračuje v hledání v nejvzdálenějším dostupném stavu, a prohledávání do šířky, které pokračuje naopak z jednoho k počátku nejbližších stavů, funguje uspořádané prohledávání tak, že si z vrcholů k prohledávání vybere ten z hlediska hledaného stavu nejslibnější. Přirozená implementace uspořádaného prohledávání použije k ukládání prioritní frontu, zatímco prohledávání do šířky používá obyčejnou frontu a prohledávání do hloubky zásobník (obvykle se jedná v rámci rekurze o zásobník volání). Na rozdíl od dvou ostatních zmíněných algoritmů je uspořádané prohledávání algoritmem informovaným, neboť se při uspořádávání vrcholů opírá vstupní data. Ty mohou obsahovat známou cenu vrcholů nebo hran nebo heuristiku, kterou se odhaduje jejich slibnost. Zejména u čistě lokální heuristiky se tím také jedná o algoritmus hladový.

Obdobnou myšlenku má nebo rozvíjí řada specializovanějších vyhledávacích algoritmů, například Dijkstrův algoritmus, A*, B* nebo paprskové prohledávání. Naopak na samotný algoritmus uspořádaného prohledávání se lze dívat jako na rozšíření gradientního prohledávání o paměť.

Reference

Kategorie:Vyhledávací algoritmy