Některé cesty vedou k nalezení cíle možná rychleji. Jak to můžeme odhadnout. Heuristická funkce. Jaké heuristiky jsou nejlepší, přípustné?
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.