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

Nesystematické prohledávání stavového prostoru

Zpět na výběr úloh

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

V této části se z plánování trasy pro roboty přesuneme na plánování rozložení zboží. Pro první prodejnu obtimalizujeme pouze 7 regálů na středu.

  1. Z předchozího prodeje máte pro malý i velký sklad seznam výrobků s pravděpodomnosmi, že si je zákazníci vyberou (a robot pro ně bude muset zajet). Pomocí algoritmu hill-climbingu optimalizujte rozložení výrobků ve skladu (pro zjednodušení bude každý výrobek zabírat plochu regálu o velikosti jednoho zastavení robota z jedné strany regálu).
  2. Vyberte náhodně 100 výrobků podle daných pravděpodobností (výběr s opakováním) a porovnejte ujetou vzdálenost před optimalizací a po optimalizaci.

Úloha 2: MAX-SAT

MAX-SAT je problém nalezení takového ohodnocení proměnných, aby celkový počet splněných klauzulí v Booleovské formuli v konjunktivní normální formě (CNF) byl co největší.

  1. Použijte tabu prohledávání prostoru ohodnocení proměnných a získejte co nejlepší řešení. Při testování svého algoritmu můžete použít veřejné datasety (stáhněte si variantu complete-unweighted).
  2. Jak byste do problému MAX-SAT převedli např. problém vytvoření rozvrhu, kdy o úterní cvičení od 14:30 do 16:00 v místnosti 349 stojí předměty A, B, C? Jak byste přidali další předměty, místnosti?

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

Dostali jste úkol naplánovat trasu pro dodávku plnou balíků, která má objet 6 měst (Praha, Brno, Ostrava, Plzeň, Liberec, České Budějovice) a vrátit se do Prahy, odkud také vyjede. Vzdálenosti mezi městy máte uvedené v datovém souboru.

  1. Vymyslete vhodné kódování problému
  2. Použijte simulované žíhání k optimalizaci délky trasy.
  3. Vytvořte graf závislosti klesající teploty na celkové délce trasy.

Úloha 4: Hra 2048 V.

Věčným snem (a noční můrou) programátorů je automatizace programování. Dnes se tomu s příchodem LLM (anglická zkratka pro velké jazykové modely) možná blížíme trochu víc, ale zde si zkusíme postup o něco starší (cca z roku 1990) – genetické programování.

  1. Pomocí algoritmu genetického programování vyšlechtěte řídící funkci pro hru 2048, která bude pro každé rozložení čísel vracet celé číslo 0 až 3 (směr tahu).
  2. Vyberte operátory pro tuto funkci (např. ternární, less_than apod.).
  3. Vyberte operátory křížení a mutace (např. prohození podstromu u křížení, nahrazení podstromu u mutace)
  4. Implementujte algoritmus a fitness funkci (inspirujte se např. počítáním skóre v základní hře 2048)

Úloha 5: CNC vrtačka V.

  1. Pomocí genetického algoritmu hledejte co nejlepší řešení Hamiltonovské cesty
  2. Jako prvotní řešení volte náhodnou permutaci.
  3. Jak spojit dvě řešení při křížení?
  4. Jak upravit řešení při mutaci?
  5. Vytvořte graf vývoje nejlepšího řešení v závislosti na číslu generace
  6. Jak ovlivňuje velikost populace kvalitu řešení?