====== 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.InfEasyMaze'', blíže viz [[courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:specifikace|Specifikace]].
  
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]].  


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

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

Termín odevzdání úlohy lze vidět v [[https://cw.felk.cvut.cz/upload/|Upload systému]]. 

   * Odevzdávat budete ZIP archív s vaším modulem ''agent.py'' a případně se všemi moduly, které tento modul importuje. **Tyto soubory musí být v kořeni archívu, archív nesmí obsahovat žádné adresáře!**


===== Instrukce pro úlohu =====

   - Vytvořte si ve vašem oblíbeném IDE projekt a v něm soubor ''agent.py'' podle [[.:specifikace|specifikace]].
   - Pro testování před odevzdáním využijte testovací prostředí {{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:kuimaze_search.zip|kuimaze_search.zip}}.
     - Zip soubor rozbalte do složky s Vaším projektem.
     - Pro plné spuštění, včetně vizualizace, je zapotřebí mít nainstalované python3 balíčky AI-gym, numpy a pillow. Pro jejich instalaci použijte následující příkazy v terminálu: 
<code bash>
pip3 install gym numpy
sudo apt-get install python3-pil.imagetk
</code>