1. Prohledávání stavového prostoru

Vaším úkolem je naprogramovat algoritmus A* k prohledávání stavového prostoru.

Naprogramujte algoritmus A*, který

• vždy najde nejlevnější cestu do některého z cílových stavů;
• pokud cesta do žádného z cílů neexistuje, algoritmus vrátí hodnotu None;
• při hledání cesty algoritmus prozkoumá co nejméně stavů.

K dispozici máte prostředí-bludiště kuimaze2.SearchProblem.

Pro správnou funkčnost algoritmu je zapotřebí zvolit takzvanou heuristickou funkci. Popis jaký dopad mají různé návrhy této funkce na výsledné řešení je velice pěkně zpracován zde. Cena přechodu mezi dvěma sousedními políčky je vždy větší nebo rovna euklidovské vzdálenosti souřadnic těchto políček a obecně není stejná pro všechny páry políček.

1. Zprovozněte si balíček kuimaze2, pokud jste to ještě neudělali.
2. Seznamte se s prostředím SearchProblem. (V balíčku kuimaze2 byste také měli najít skript example_search.py, který také ukazuje, jak se s prostředím dá pracovat.)
3. Vytvořte modul agent.py podle specifikací.

V modulu (souboru) agent.py implementujte třídu Agent, která bude poskytovat tyto metody:

Následující moduly Pythonu mohou být užitečné při implementaci jistých částí A* algoritmu: queue, heapq.

• Termín odevzdání úlohy najdete v BRUTE, úloha 02-search.
• Odevzdejte ZIP archív s vaším modulem agent.py a případně se všemi moduly, které jste vytvořili a které váš agent importuje. Tyto soubory musí být v kořeni archívu, archív nesmí obsahovat žádné adresáře! Neodevzdávejte žádné moduly, které jste dostali od nás!

Bodové ohodnocení za rešení úlohy lze vidět v hodnoceni.

Když úlohu úspěšně vyřešíte, měli byste v závislosti na zvolené mapě být schopni vygenerovat obrázek podobný následujícímu. (Tento konkrétní obrázek pochází z předchozí verze balíčku kuimaze. Aktuální verze generuje obrázky mírně jiné.)