{{indexmenu_n>6}}
<timer 2000-01-01 00:00:01=2017-03-27 00:00:01>
Obsah této stránky bude přístupný od 27. 3. 2017.
</timer>

<timer 2017-03-27 00:00:01=->
====== Prohledávání stavového prostoru: neinformované prohledávání ======

návod pro seminární cvičení

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

=== Cíl cvičení ===

Prakticky procvičit znalosti prezentované na přednášce a vysvětlit na příkladech pojmy stavový prostor, stav, stavový operátor, expanze stavu a pojmy z teorie složitosti.

===== Bludiště =====

Máte dánu mapu bludiště. Černá políčka jsou neprostupná. Úkolem je naplánovat cestu z místa A do místa B (nebo C). //(Šedá pole mají význam při cvičení na informované prohledávání.)//

{{:courses:a3b33kui:cviceni:obrazky:06_obr1.png?800|Mapa bludiště - počáteční stav}}

=== Úkol ===

Nalezněte cestu z místa A do místa B pomocí následujících algoritmů:

  * prohledávání do šířky
  * prohledávání do hloubky
  * iterative deeping depth-first search

//Pro jednotlivé algoritmy určete, zda jsou úplné, ukončí se, zda jsou optimální a jaká je jejich časová a paměťová složitost.//
 
Situace při prohledávání do hloubky s jiným pořadím expanze uzlů. Nalezená cesta není nejkratší. Porovnejte s předchozím případem.

{{:courses:a3b33kui:cviceni:obrazky:06_obr2.png?800|Mapa bludiště - expandované uzly}}

X – closed   O – open

===== Další příklady =====

==== Kanibalové a misionáři ====

Skupina 3 kanibalů a 3 misionářů dorazí k řece a potřebují se přes ni přepravit. K dispozici mají loď s nosností max. 2 osoby. Jestliže počet kanibalů na břehu převýší počet misionářů, kanibalové misionáře přemůžou a snědí. Navrhněte postup, kterým přepravíte přes řeku všechny misionáře i kanibaly.

=== Popis stavu ===

s = (Počet kanibalů na pravém břehu, Počet misionářů na pravém břehu, Pozice lodi, Počet kanibalů na levém břehu, Počet misionářů na levém břehu)

{{:courses:a3b33kui:cviceni:obrazky:06_obr3.png?800|Stavový prostor úlohy}}

//Stavový prostor úlohy//

==== Přelévání vody ====

Máte k dispozici 2 prázdné nádoby s objemem 3 a 4 litry bez označení míry a neomezený zdroj vody. Cílem je dosáhnout stavu, kdy v jedné z nádob jsou 2 litry vody.

==== Lišák ====

Máte čtvercovou hrací desku s devíti místy a osmi očíslovanými kameny. Začínáte s náhodným rozmístěním kamenů, koncový stav je charakterizován přiřazením jednotlivých kamenů daným místům.
</timer>