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

Systematické neinformované prohledávání

Zpět na výběr úloh

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

task 1 warehouse
Obrázek 1. Zobrazení rozložení regálů ve druhém skladu
  1. Vyřešte úlohu z minulého týdne pomocí algoritmu BFS.
  2. Své řešení rozšiřte i pro druhý (větší) sklad se dvěma roboty a dvěmi napájecími stanicemi (před levým a pravým krajním regálem). Každý robot dostane zadanou pozici balíčku, který má vyzvednout. Oba roboti současně a bez kolize dojedou od nabíjecích stanic pro svoje balíčky do regálu, odvezou je na překladiště (hromady balíků před regály) a odjedou se nabíjet na nabíjecí stanici. Většina regálů má podél své délky 50 zastavení pro robota. Krajní regály jsou kratší a mají pouze 45 zastavení (pro zachování délek přidejte před tyto regály 5 pseudo-zastavení, na kterých v praxi robot nebude stavět).

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

  1. Vyřešte úlohu z minulého týdne pomocí algoritmu DFS.
  2. Přidejte do grafu dummy uzly tak, aby se každá hrana transformovala na cestu délky své latence (např. do hrany (U16)--(U17) s ohodnocením 2 přidáte 1 dummy uzel, čímž získáte cestu (U16)--(d1)--(U17)). Vyřešte takto expandovaný graf pomocí algoritmu BFS.
    • Kolik procent uzlů z expandovaného grafu zabírají původní uzly?
    • Při výpisu řešení pište pouze původní uzly. Má získané řešení minimální latenci?

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

  1. Vyřešte úlohu z minulého týdne pomocí algoritmu DFS.
  2. Přidejte do grafu dummy uzly tak, aby se každá hrana transformovala na cestu podle své délky (např. do hrany (Liberec)--(Jablonec nad Nisou) s ohodnocením 10 přidáte 9 dummy uzlů, čímž získáte cestu (Liberec)--(d1)--(d2)--…​--(d9)--(Jablonec nad Nisou)). Vyřešte takto expandovaný graf pomocí algoritmu BFS.
    • Kolik procent uzlů z expandovaného grafu zabírají původní uzly?
    • Při výpisu řešení pište pouze původní uzly. Má získané řešení minimální délku?
    • Jde omezit počet přidaných uzlů při zachování kvality řešení? Existuje spojitost s největším společným dělitelem či nejmenším společným násobkem?

Úloha 4: Hra 2048 II.

  1. Vyřešte úlohu z minulého týdne pomocí algoritmu DFS. Hrajte i za počítač (tzn. počítač vám zde "jde na ruku" a dělá přesně to, co chcete).
  2. Přidejte alternativní řešení pomocí algoritmu BFS.
  3. Odpovězte na otázky:
    • Kolik uzlů musely jednotlivé algoritmy expandovat?
    • Kolik je u DFS řešení nesloučených dlaždic? Kolik je u BFS?
    • Liší se množina čísel přidávaných počítačem v rámci DFS/BFS řešení?

Úloha 5: CNC vrtačka II.

  1. Vyřešte úlohu z minulého týdne pomocí algoritmu DFS.
  2. Přidejte řešení pomocí algoritmu BFS.
  3. Přidejte řešení pomocí algoritmu DFS s iterativním prohlubováním.
  4. Odpovězte na otázky:
    • Jaké jsou paměťové / časové požadavky jednotlivých algoritmů?
    • Jaký algoritmus najde optimální řešení? Algoritmus nemusí být polynomiální vzhledem k délce vstupu.