====== 01 Úvod, Prohledávání ======
  * [[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
  * **prohledávání**: vysvětlení
  * zadání první samostatné úlohy

===== 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}}


===== Zadání úlohy: hledání cesty v bludišti =====

V prostředí [[courses:b3b33kui:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:start|Prohledávání stavového prostoru]] naprogramujte nalezení nejlevnější cesty. Nezapomeňte, že cena přechodu mezi pozicemi nemusí být nutně všude stejná.

===== Seznámení s prostředím KUIMaze =====
  * [[courses:b3b33kui:kuimaze:00_instalace|Stáhněte a nainstalujte si prostředí KUIMaze]]
  * Vytvořte prostředí bludiště, tedy instanci třídy ''kuimaze.InfEasyMaze'' s mapou danou obrázkem ''maps/easy_intro/easy_intro_1.bmp'':<code python>
>>> import kuimaze
>>> MAP = 'maps/easy_intro/easy_intro_1.bmp'
>>> env = kuimaze.InfEasyMaze(map_image=MAP)</code>
  * Zobrazte si mapu bludiště metodou ''render()'':<code>
>>> env.render()</code> Měli byste vidět následující obrázek:
{{ :courses:b3b33kui:cviceni:program_po_tydnech:easy_intro_1.png?200 |}} **Okno s obrázkem si zatím nechte otevřené, nezavírejte ho!**
  * Zkuste odhadnout, co dělá metoda ''reset()''. Porovnejte výsledek následujícího volání s obrázkem bludiště:<code python>
>>> env.reset()
((1, 0, 0.0), (4, 2, 0.0))</code>
  * Zkuste odhadnout, co dělá metoda ''expand()'':<code python>
>>> env.expand((1,0))
[[(2, 0), 1.0], [(0, 0), 1.0]]</code>
  * Zkuste znovu zavolat ''env.render()''. Změnil se nějak obrázek?
  * Prozkoumejte ''easy_example.py'' a pokuste se pochopit, co se v něm děje.
  * Zkuste zkonstruovat cestu ze startu do cíle ručně a upravte metodu ''Agent.find_path()'' tak, aby natvrdo vracela tuto vaši cestu.
  * Zkuste tohoto svého Agenta odevzdat do BRUTE do úlohy 01-easy-search, viz níže.




===== Prohledávácí rozcvička - nepovinná úloha 01-easy_search =====
Ačkoli mnozí jste již netrpěliví skočit na implementaci algoritmu A*, zkuste napřed hledání cesty v jednoduchém bludišti. 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 na jednodušším problému. Základní komunikační rozhraní je stejné, tedy
<code python>
import kuimaze
MAP = 'maps/easy_intro/easy_intro_1.bmp'
env = kuimaze.InfEasyMaze(map_image=MAP)
observation = env.reset() # returns start_pos, goal_pos
position = observation[0][0:2] # start position
positions_with_costs = env.expand(position) # list of lists [pos,cost], i.e. [[pos1, cost1],[pos2,cost2],...]
</code>
Odevzdávat budete také modul ''agent.py'', přesně podle [[courses:b3b33kui:semestralni_ulohy:1_prohledavani_stavoveho_prostoru:specifikace|specifikace]].
Vyzkoušejte různé strategie prohledávání. Pokud napíšete dostatečně obecně, stejný kód bude fungovat i pro případ algoritmu A*. Odevzdávat budete do [[https://cw.felk.cvut.cz/upload/|Upload systému]]. 

Rozmyslete si trochu nad papírem datové struktury, které budete potřebovat. 


===== programování hledání =====
  * Python [[https://docs.python.org/3/library/queue.html|queue]] nebo [[https://docs.python.org/3.6/library/heapq.html|heapq]] vám mohou pomoci při ukládání uzlů prohledávacího stromu.


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