====== 02 Prohledávání II ======
Některé cesty vedou k nalezení cíle možná rychleji. Jak to můžeme odhadnout. Heuristická funkce. Jaké heuristiky jsou //nejlepší, přípustné//?

  * Diskuse nad řešením prvního DÚ
  * Kvíz I, II
  * Prohledávací rozcvička

===== Kvíz I =====
 /* * kvíz, jak optimálně naplánovat let
  * bodovaný, bonusových 0.5bodu
  * řešení odevzdat do BRUTE do úlohy **lab02quiz**, 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
  * správné řešení prodiskutujeme na příštím cvičení
*/

> {{page>courses:b3b33kui:internal:quizzes#Plánování letových hladin}}

/*
==== Zadání kvíz I ====
  * p. 101, St 12:45: {{ :courses:b3b33kui:cviceni:program_po_tydnech:20210224-082505_planealtitude_cviko101.pdf | 20210224-082505_planealtitude_cviko101.pdf}}
  * p. 102, St 14:30: {{ :courses:b3b33kui:cviceni:program_po_tydnech:20210224-082448_planealtitude_cviko102.pdf | 20210224-082448_planealtitude_cviko102.pdf}}
  * p. 103, Čt 12:45: {{ :courses:b3b33kui:cviceni:program_po_tydnech:plane_altitude_ct_25feb_p103_cz.pdf |plane_altitude_ct_25feb_p103_cz.pdf}}
  * p. 104, Čt 14:30: {{ :courses:b3b33kui:cviceni:program_po_tydnech:20210225-111909_planealtitude_cviko104.pdf} | 20210225-111909_planealtitude_cviko104.pdf}} 
  * p. 105, Pá 9:15: {{ :courses:b3b33kui:cviceni:program_po_tydnech:plane_altitude_pa_26feb_p105_cz.pdf | plane_altitude_pa_26feb_p105_cz.pdf }}
*/  

===== Kvíz II =====
/*  * prezentace {{ :courses:b3b33kui:cviceni:program_po_tydnech:search_ii_example_cz.pdf |Search_II_example_cz.pdf }} */

> {{page>courses:b3b33kui:internal:quizzes#padajici_2_vejce}}


===== Prohledávácí rozcvička =====
Ačkoli mnozí jste již netrpěliví skočit na hledání cesty v bludišti, začněte jednoduchým grafem. Je to menší problém, bude se vám snáz krokovat a debugovat. Hledání cesty v grafech z přednášky si můžete vyzkoušet pomocí ''{{ :courses:b3b33kui:cviceni:program_po_tydnech:kuigraphs.py |kuigraphs.py}}''. Základní komunikační rozhraní je stejné jako pro ''kuimaze''. Tedy
<code python>
import kuigraphs
env = kuigraphs.KuiGraph()
observation = env.reset()
states_with_costs = env.expand(state) # list of tuples ('a',1)
env.set_path(path)
</code>
''state'' je písmeno, jako v přednášce, 'S', 'a', ... 'G'. Vyzkoušejte různé strategie prohledávání. Pokud napíšete dostatečně obecně, stejný kód bude fungovat i pro případ
<code python>
env = kuimaze.InfEasyMaze()
</code>

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

> {{page>courses:b3b33kui:internal:cviceni:tyden_02#programming}}
===== 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]] řešení n-1 puzzle