{{indexmenu_n>9}}
<timer 2000-01-01 00:00:01=2017-04-10 00:00:01>
Obsah této stránky bude přístupný od 10. 4. 2017.
</timer>

<timer 2017-04-10 00:00:01=->
====== 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.

{{:courses:a3b33kui:cviceni:obrazky:08_obr1.png?800|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í?

=== 2) Hladové uspořádané prohledávání (Greedy best-first search) ===

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.

{{:courses:a3b33kui:cviceni:obrazky:08_obr2.png?800|Letové hladiny}}
</timer>