====== 1. Prohledávání stavového prostoru ======
Vaším úkolem je naprogramovat [[https://en.wikipedia.org/wiki/A*_search_algorithm|algoritmus A*]] k prohledávání stavového prostoru [[https://en.wikipedia.org/wiki/State_space_search|State_space_search]].


===== Formulace úlohy =====
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ě ''[[..:kuimaze:10_searchproblem|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 [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html|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. 


===== Jak na to =====
   - [[..:kuimaze:00_install|Zprovozněte si]] balíček ''kuimaze2'', pokud jste to ještě neudělali.
   - Seznamte se s prostředím [[..:kuimaze:10_searchproblem|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.)
   - Vytvořte modul ''agent.py'' podle specifikací.

<WRAP important round>
   * Vaše řešení musí být kompatibilní s [[..:..:cvičení:python_version|požadovanou verzí Pythonu]], jinak nemusí správně fungovat automatické hodnocení.
</WRAP>

===== Třída Agent a její metody =====
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.|

==== Tipy ====
Následující moduly Pythonu mohou být užitečné při implementaci jistých částí A* algoritmu: [[https://docs.python.org/3.11/library/queue.html|queue]], [[https://docs.python.org/3.11/library/heapq.html|heapq]].


===== Odevzdání =====

  * Termín odevzdání úlohy najdete v [[https://cw.felk.cvut.cz/brute|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!


===== Hodnocení =====
Bodové ohodnocení za rešení úlohy lze vidět v [[.:hodnoceni|hodnoceni]].


===== Vizualizace =====
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é.)
{{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:normal9.png|}}