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é?

Po tomto cvičení student

• rozumí významu heuristické funkce;
• na malých instancích prohledávacích problémů umí ověřit, zda je heuristická funkce přípustná a konzistentní;
• rozumí pojmu rekurze, umí implementovat jednoduché rekurzivní algoritmy.

1. Dotazy k hledání v bludišti
2. Kvíz I, II
3. Rekurzivní implementace výpočtu Fibonacciho posloupnosti a její analýza
4. Seznámení s programovací úlohou Reversi

• kvíz na vlastnosti heuristik.

Naprogramujte rekurzivně výpočet faktoriálu $f(n) = n!$

Návod

Vizualizace volání:

Naprogramujte rekurzivně výpočet Fibonacciho posloupnosti. $f(n) = f(n-1) + f(n-2)$. Analyzujte počet volání funkce a hloubku zanoření.

Strom volani:

Demo code:

• Dokončete implementaci A* algoritmu, odevzdejte do úlohy 02-search.
• Druhou povinnou úlohu 03-reversi si představíme příště. Doma si ale zkuste prostředí Reversi prozkoumat (návod naleznete zde).
  • Spusťte hru.
  • Zkuste si vytvořit hráče.