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.
kuimaze2
, pokud jste to ještě neudělali.
kuimaze2
byste také měli najít skript example_search.py
, který také ukazuje, jak se s prostředím dá pracovat.)
agent.py
podle specifikací.
V modulu (souboru) agent.py
implementujte třídu Agent
, která bude poskytovat tyto metody:
metoda | vstupní parametry | výstupní parametry | vysvětlení |
---|---|---|---|
__init__ | environmnent: SearchProblem | žádné | Inicializace agenta. |
find_path | žádné | cesta | Vrací nalezenou cestu nebo None , pokud cestu nenajde. Cestou je myšlen seznam (list) vzájemně sousedících stavů (State ) začínající počátečním stavem a končící cílovým stavem. |
Následující moduly Pythonu mohou být užitečné při implementaci jistých částí A* algoritmu: queue, heapq.
03-search
.
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.