FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

Systematické informované prohledávání s A*

Zpět na výběr úloh

Úloha 1: Robotické skladiště IV.

  1. Vyřešte úlohu pro první i druhý sklad pomocí algoritmu A*. Zvolte vhodnou heuristiku.
  2. Je zvolená heuristika přípustná? Je monotónní? Co to znamená pro A*?
  3. Je získané řešení optimální?

Úloha 2: Rychlé poslání zprávy IV.

  1. Použijte heuristiku vypočítanou Dijkstrovým algoritmem z minulé hodiny pro algoritmus A*.
  2. Vymyslete heuristiku, která půjde snadněji spočítat. Je přípustná? Je monotónní? Co to znamená pro algoritmus A*?
  3. Použijte svou heuristiku v algoritmu A* a porovnejte rychlost jeho běhu, sekvenci expanzí uzlů a kvalitu nalezeného řešení s A* využívajícím předchozí heuristiku.

Úloha 3: Doručení balíčku IV.

  1. Vyřešte úlohu pomocí algoritmu A*.
  2. Je zvolená heuristika přípustná? Je monotónní?
  3. Porovnejte s řešením pomocí Dijkstrova algoritmu. Který algoritmus má menší dobu běhu? Který expanduje méně uzlů?

Úloha 4: Hra 2048 IV.

  1. Použijte heuristiku z minulého cvičení a vyřešte úlohu pomocí algoritmu A*.
  2. Je řešení optimální?
  3. Porovnejte sekvenci expanzí uzlů s DFS a hladovým prohledáváním.

Úloha 5: CNC vrtačka IV.

  1. Použijte heuristiku z minulého cvičení a vyřešte úlohu pomocí algoritmu A*.
  2. Jaké vlastnosti má algoritmus A* s touto heuristikou? Najde optimální řešení?