Misionáři a kanibalové
Úloha č. 1 pro cvičení k předmětu Vybrané kapitoly z umělé inteligence
Zadání:Implementujte vlastní řešení problému zvaného Misionáři a kanibalové (problémje popsán na konci tohoto
textu). Pro implementaci použijte hledání do šířky ve stromu, který representuje prostor všech možných řešení
(implementace zahrnuje vygenerování a prohledání tohoto stromu).
Účelem cvičení je vyzkoušet si řešení typické jednoduché úlohy z oblasti umělé inteligence. Řešení obdobných úloh
výrazně pomáhá proniknutí do větší hloubky a pochopení některých záležitostí umělé inteligence.
Studenti a studentky vypracují řešení každý zcela samostatně, programovací jazyk si mohou sami zvolit. Stručné
zhodnocení problému a dosažených výsledků (stačí text v ASCII/ANSI) zašlou e-mailem na adresu
zizka@fi.muni.cz; subject e-mailu bude obsahovat text KANIBALOVE a dále jméno a příjmení autorky/autora
řešení (napr. KANIBALOVE Novakova Josefa). E-mail musí v příloze obsahovat také zdrojový kód programu
včetně kopie případných výpisů programu apod., aby bylo možno řešení zhodnotit. Termín je do půlnoci 15.prosince
2004, později to není možné. Pokud nebude úkol splněn, ze závěrečného hodnocení předmětu bude odečteno 10%,
což může ovlivnit výsledné ohodnocení předmětu, které se skládá z písemky na zkoušce (max. 70%) a ze tří úloh
ve cvičení (max. 3x10%=30%).
Misionáři a kanibalové
Tři misionáři a tři kanibalové jsou na jedné straně řeky a mají k dispozici jednu loďku, která uveze jednoho nebo
dva lidi. Úkolem je najít způsob přepravy všech šesti lidí na druhou stranu řeky tak, aby nikdy nezůstala skupina
misionářů s číselnou převahou kanibalů na jednom místě (břehu). Tento problém patří mezi proslulé problémy
v oblasti umělé inteligence, protože byl jako první v literatuře formulován z analytického hlediska (v r. 1968). Zde
je nutno napřed výrazně abstrahovat, zbavit úlohu nepotřebných detailů (které by se v reálné situaci přirozeně
vyskytly). Číselná převaha není v loďce možná, takže zbývají pouze oba břehy jako možnosti. Čas dopravy není
nutný. Pokud má do loďky nastoupit cestující, je jedno, který kanibal či misionář, na kterém břehu se začíná... apod.
a) Stavy: stav se skládá z uspořádané sekvence tří čísel representujících počet misionářů, počet kanibalů, a počet
loděk na každém břehu. Tedy počáteční stav je (3, 3, 1) na výchozím břehu, (0, 0, 0) na cílovém.
b) Operátory: z každého stavu existují možné operátory: do loďky 1 nebo 2 misionáři, 1 nebo 2 kanibalové,
1 misionář a 1 kanibal, tj. max. 5 operátorů, i když ve většině stavů jich bude zřejmě méně kvůli vyhnutí se
nepřípustným stavům. (Pozn.: kdybychom rozlišovali jednotlivce jako různé osoby, pak bychom měli 27 operátorů,
ale v úloze netřeba rozlišovat jednotlivce.)
c) Test cíle: dosažení stavu (0, 0, 0) na výchozím břehu, (3, 3, 1) na cílovém.
d) Cena cesty: počet přejezdů přes řeku (cílem je minimální počet přejezdů, tj. co nejlacinější řešení). Uvedený
stavový prostor je dostatečně malý, takže pro počítač je nalezení výsledku triviální, pro lidi je problém o dost
obtížnější, zejména proto, že některé nezbytné kroky se zdají být retrográdní.