Search
Autoři textu: Milan Rollo, Eduard Semsch, Štěpán Urban, Viliam Lisý a Petr Benda Úprava: Tibor Strašrybka
Cvičení je zaměřeno na procvičení znalostí o informovaném prohledávání stavového prostoru. Cílem je, aby studenti pochopili UCS algoritmus, greedy algoritmus, A* a byli schopni uvažovat o jejich vlastnostech a omezeních. Plán cvičení je:
Máte dánu mapu bludiště. Černá políčka jsou neprostupná, cena průchodu šedým polem je 3, bílým polem 1, úkolem je naplánovat cestu z místa A do místa B (nebo C) s minimální cenou.
Použijte UCS algoritmus pro nalezení cesty do bodu B, při startu v bodu A. Nalezne algoritmus optimální řešení?
Aplikujte best-first search algoritmus. Jako hodnotící funkci využijte vzdálenost od cíle v taxikářské metrice (suma absolutních rozdílů v obou souřadnicích, také manhattanská vzdálenost). Při stejném ohodnocení jsou preferována bílá pole, při stejném ohodnocení bílých polí je následovník vybrán náhodně.
Úkol stejný jako výše, liší se jen algoritmus.
Aplikujte algoritmus A, heuristika je opět dána vzdáleností do cíle v taxikářské metrice.
Úkol stejný jako výše, porovnejte počet kroků a optimalitu řešení mezi třemi algoritmy. Jde v tomto případě o algoritmus A nebo A*?
V továrně je třeba naplánovat (rozvrhovat) výrobu 50 druhů produktů na výrobní lince. Omezení jsou dána kapacitou linky v kusech/hodinu pro každý druh produktu a požadavky na dodávky daného počtu kusů různých produktů v čase (řádově stovky požadavků). Zisk (tzn. optimalita) je ovlivněn rovnoměrností zatížení linky (kvůli ceně přesčasů a prostojů) a cenou za den skladování každého předčasně vyrobeného kusu.
Z praktických důvodů (čas nastavení strojů) je nutné pokud možno vyrábět souvislé zakázky kusů jednoho druhu. Nulový počáteční sklad.
Navrhněte formální zápis problému, popište stavový prostor a omezení, navrhněte heuristiku a diskutujte o vlastnostech A* algoritmu při řešení této úlohy.
Letadlo: Může letět ve čtyřech letových hladinách, spotřeba paliva v první je 5 jednotek paliva/jednotka vzdálenosti, druhé 4 atd. Spotřeba paliva při stoupání je 10, při klesání 1. Letadlo se má přemístit mezi letišti vzdálenými 10 jednotek vzdálenosti. Nádrž letadla pojme 50 jednotek paliva, optimalizujte spotřebu.