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

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.

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í.)

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.

X – closed O – open

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.

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)

Stavový prostor úlohy

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.

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.