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, 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í

• p. 101, St 12:45: 20210224-082505_planealtitude_cviko101.pdf
• p. 102, St 14:30: 20210224-082448_planealtitude_cviko102.pdf
• p. 103, Čt 12:45: plane_altitude_ct_25feb_p103_cz.pdf
• p. 104, Čt 14:30: 20210225-111909_planealtitude_cviko104.pdf
• p. 105, Pá 9:15: plane_altitude_pa_26feb_p105_cz.pdf

• prezentace Search_II_example_cz.pdf

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í ''kuigraphs.py''. Základní komunikační rozhraní je stejné jako pro kuimaze. Tedy

import kuigraphs
env = kuigraphs.KuiGraph()
observation = env.reset()
states_with_costs = env.expand(state) # list of tuples ('a',1)
env.set_path(path)

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

env = kuimaze.InfEasyMaze()

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

• Python queue nebo heapq vám mohou pomoci při ukládání uzlů prohledávacího stromu.

• visualizace řešení n-1 puzzle