====== 01 Úvod, Prohledávání ======

===== Výsledky učení =====
Po tomto cvičení student
  * ví, kde si říct o pomoc, když se zasekne (na cvičení, [[https://cw.felk.cvut.cz/forum/forum-1944.html|na diskusním fóru]], na [[https://discordapp.com/channels/690919691404967977/754330370182480003|Discordu]], emailem učiteli);
  * rozumí způsobu, jakým bude v předmětu hodnocen;
  * rozumí pravidlům pro použití AI a pro předcházení plagiarismu;
  * rozezná diskrétní prohledávací problém, umí identifikovat stavy a akce, umí ohodnotit kandidátské řešení/plán;
  * rozumí pojmům //úplný// a //optimální//;
  * má nainstalovaný Python a prostředí ''kuimaze2'';
  * chápe zadání první povinné úlohy ''02-search'';
  * umí použít veřejné rozhraní prostředí ''kuimaze2.SearchProblem'';
  * umí odevzdat řešení úlohy do BRUTE.

===== Úvod =====
  * [[https://cw.fel.cvut.cz/wiki/courses/b3b33kui/start#hodnoceni|Požadavky a hodnocení předmětu]]
  * [[https://cw.fel.cvut.cz/wiki/help/common/plagiaty_opisovani|Pravidla samostatné práce]] a [[courses:b3b33kui:ai|pravidla pro použití nástrojů AI]]
  * Počítačové laboratoře a užitečné služby
    * [[https://cyber.felk.cvut.cz/study/computer-labs/|počítačové laboratoře]] na [[http://cyber.felk.cvut.cz|K133]]  a bezpečnost práce
    * https://www.cesnet.cz/sluzby/owncloud/
    * https://gitlab.fel.cvut.cz
  * [[courses:b3b33kui:cviceni:python_install:start|Instalace Pythonu]] 

===== Kvíz I - bonusový =====
 /* * startovní kvíz, na n-puzzle
  * bodovaný, bonusových 0.5bodu
  * řešení odevzdat do BRUTE do úlohy **lab01quiz**, do půlnoci dne, kdy běží dané cvičení
  * formát: textový soubor, fotka řešení na papíře, pdf - co Vám nejlépe vyhovuje a dokážeme to přečíst
*/

/*==== Kvíz ====*/
> {{page>courses:b3b33kui:internal:quizzes#Plánování letových hladin}}




===== Prohledávání I =====
  * vysvětlení /*, on-line výuka*/
  * budeme diskutovat, jak hledat, když nevím jak je cíl daleko
  * co znamená, že algoritmus prohledávání je //úplný, optimální//. 
  /* * prezentace {{ :courses:b3b33kui:cviceni:program_po_tydnech:searchi_example_cz.pdf |SearchI_example_cz.pdf}}*/

/* ==== Kvíz ==== */
>  {{page>courses:b3b33kui:internal:quizzes#Zapomnětlivý cestovatel}}



===== Seznámení s prostředím KUIMaze =====
  * [[courses:b3b33kui:semestralni_ulohy:kuimaze:00_install|Stáhněte a zprovozněte si prostředí KUIMaze]]
  * Projděte si sekci [[..:..:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:start#jak_na_to|Jak na to]] v popisu úlohy [[..:..:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:start|1. Prohledávání stavového prostoru]]
  * Vytvořte si prostředí ''SearchProblem'', tj. instanci třídy ''kuimaze2.SearchProblem'', s mapou danou obrázkem v souboru ''maps/easy_intro/easy_intro_1.png'':
<code python>
>>> from kuimaze2 import SearchProblem, State
>>> from kuimaze2.map_image import map_from_image
>>> map_path = 'maps/easy_intro/easy_intro_1.png'
>>> env = SearchProblem(map_from_image(map_path), graphics=True)</code>
  * Vykreslete si prostředí metodou ''render()'':
<code>
>>> env.render()
</code>
Měli byste vidět obrázek podobný následujícímu:
{{ :courses:b3b33kui:cviceni:program_po_tydnech:easy_intro_1.png?200 |}}
**Nechte okno s obrázkem otevřené, nezavírejte ho!**
  * Zkuste použít různé metody, které prostředí nabízí:
<code>
>>> start = env.get_start()
>>> start
State(r=0, c=1)
>>> env.get_goals()
[State(r=2, c=4)]
>>> actions = env.get_actions(start)
>>> actions
[<Action.UP: 0>, <Action.RIGHT: 1>, <Action.DOWN: 2>, <Action.LEFT: 3>]
>>> new_state, trans_cost = env.get_transition_result(start, actions[1])
>>> new_state
State(r=0, c=2)
</code>
  * Zkuste zavolat ''env.render()'' znovu. Změnilo se zobrazení nějak?
  * Zkuste přidat do volání metody ''render()'' další parametry:
<code python>
>>> texts = {State(0,0): "S", State(0,1): "1"}
>>> env.render(texts = texts, current_state=State(0,0), next_states=[State(1,0)])
</code>
  * Prozkoumejte ''example_search.py'' a zkuste pochopit, co se tam děje.
  * Zkuste manuálně zkonstruovat cestu ze startu do cíle a vrátit ji z metody ''Agent.find_path()''.
  * Zkuste si takového agenta odevzdat do [[https://cw.felk.cvut.cz/brute/|BRUTE]] do úlohy ''01-easy_search''.

===== Nepovinná úloha 01-easy_search =====
  * Ačkoli jste mnozí již netrpěliví se rovnou vrhnout na implementaci algoritmu A*, zkuste napřed jednodušší algoritmy (BFS, UCS) a jednoduchá bludiště. Je to menší problém, bude se vám snáz krokovat a debugovat, ověříte si správné zacházení s prostředím.
  * Rozmyslete si trochu nad papírem datové struktury, které budete potřebovat. Zkuste implementovat různé strategie/algoritmy. Pokud je implementujete dostatečně obecným způsobem, většina vašeho kódu půjde použít i pro algoritmus A* (což je první povinná úloha).
  * Zkuste svůj algoritmus v modulu ''agent.py'' odevzdat do [[https://cw.felk.cvut.cz/brute/|BRUTE]] a prozkoumejte, jakou zpětnou vazbu vám hodnoticí skript poskytl. 
  * Část bodů je za nalezení validní cesty do cíle, část za nalezení optimální cesty; za prozkoumání větší oblasti než je potřeba jsou naopak bodové srážky. Ale pozor: co stačilo v této úloze nemusí stačit v první povinné úloze! Tam jsou kritéria přísnější!

===== Povinná úloha 1: Hledání cesty v bludišti algoritmem A* =====
  * V [[..:..:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:start|povinné úloze 1]] je vaším úkolem naimplementovat algoritmus A*, který vám bude představen nejpozději na druhé přednášce. Pokud jste ale předchozí prohledávací rozcvičku zvládli rychle a nedělá vám potíže programovat v Pythonu, můžete začít pracovat na první povinné úloze.
  * Nezapomeňte, že cena za přechod z jednoho stavu do jiného nemusí být pro všechny stavy stejná.






===== různé =====
  * [[http://tristanpenman.com/demos/n-puzzle/|visualizace]] různých prohledávacích algoritmů demonstrována na problému n-1 puzzle

===== Domácí úkol =====
  * Rozchodit prostředí ''kuimaze2'' v Pythonu.
  * Dokončit úlohu ''01-easy_search''.
  * Začít pracovat na úloze ''02-search''.