Warning
This page is located in archive.

Prohledávání stavového prostoru - informované prohledávání

Autoři textu: Milan Rollo, Eduard Semsch, Štěpán Urban, Viliam Lisý a Petr Benda
Úprava: Tibor Strašrybka

Úvod

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:

  • Informované prohledávání stavového prostoru
  • Prohledávání podle dosavadní ceny - příklad na mapě. Uniform Cost Search (f = g)
  • Prohledávání podle budoucí ceny, greedy - příklad na mapě. (f = h)
  • A, A* jako kombinace výše zmíněných - příklad na mapě. (f = g + h)
  • Prakticky orientovaná diskuse o vlastnostech A*.

Příklady

Bludiště

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.

Mapa bludiště

1) Algoritmus se stejnoměrnou cenou (Uniform cost search, UCS)

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.

3) A, A*

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*?

Rozvrhování produkce

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.

Příklad na heuristiku

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.

Letové hladiny

courses/a3b33kui/cviceni/08.txt · Last modified: 2017/03/01 01:55 by xnovakd1