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

Systematické informované prohledávání (heuristiky, hladové prohledávání)

Zpět na výběr úloh

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

  1. Vyřešte úlohu pro první i druhý sklad pomocí hladového prohledávání. Zvolte vhodnou heuristiku.
  2. Je zvolená heuristika přípustná? Je monotónní?
  3. Je získané řešení optimální?

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

  1. Vyřešte úlohu pomocí Dijkstrova algoritmu.
  2. Poznamenejte si do každého uzlu vzdálenost do cíle (získanou Dijkstrovým algoritmem).
  3. Použijte vypočítané vzdálenosti do cíle jako heuristiku. Je tato heuristika přípustná? Je monotónní?
  4. Je řešení získané hladovým prohledáváním s touto heuristikou optimální? Musíme znovu spustit Dijkstrův algoritmus pro přepočítání heuristiky, pokud dostaneme jinou dvojici uzlů?

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

  1. Vyřešte úlohu pomocí hladového algoritmu.
  2. Je zvolená heuristika přípustná? Je monotónní?
  3. Porovnejte s řešením pomocí Dijkstrova algoritmu.

Úloha 4: Hra 2048 III.

  1. Zvolte jako heuristiku h=11-log2(n), kde n je největší číslo v mřížce
  2. Je tato heuristika přípustná? Je monotónní?
  3. Najde hladové prohledávání s touto heuristikou řešení dříve než DFS?

Úloha 5: CNC vrtačka III.

  1. Přidávejte uzly do řešení postupně. Nechť m1 je suma ohodnocení hran minimální kostry dosud nepřidaných uzlů (můžete použít např. Jarníkův algoritmus). Nechť m2 je minimální délka hrany z dosud nepřidaných uzlů do již přidaných uzlů. Nechť m3 je minimální délka hrany z dosud nepřidaných uzlů do prvního přidaného uzlu. Pak h=m1+m2+m3.
  2. Je tato heuristika přípustná? Je monotónní?
  3. Najde hladové prohledávání s touto heuristikou řešení (Hamiltonovskou kružnici) s menším ohodnocením než řešení od DFS?