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

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

Naprogramujte algoritmus A*, který najde optimální cestu do cílového stavu. Pokud cesta neexistuje, výsledné řešení je None. 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.

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 03-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é.)