Problem misionara i kanibala

Problem misionara i kanibala, kao i problem ljubomornih muževa, predstavlja klasičan problem prelaska reke. Ovaj problem je vrlo dobro poznat kao primer pokazatelj u veštačkoj inteligenciji, gde ga je Saul Amarel koristio kao primer predstavljanja problema.

Problem

U ovom problemu, tri misionara i tri kanibala treba da pređu reku koristeći brod koji može da preveze najviše dvoje, pod pretpostavkom da, ako je bar jedan misionar na brodu, ne sme biti nadmašen u brojnosti od strane kanibala, jer bi ga u tom slučaju pojeli. Čamac ne može sam da pređe reku, tj. bez ikoga ko bi njime upravljao. U nekim varijacijama ovog problema, jedan od kanibala ima samo jednu ruku tako da ne može da vesla.

Što se tiče problema ljubomornih muževa, misionari i kanibali su u stvari tri venčana para. Postoji uslov da nijedna žena ne može biti sa drugim muškarcem u čamcu osim ako je njen muž prisutan. S obzirom na ovaj uslov, na obali ne može biti više žena nego muževa, jer bi u tom slučaju svakako bilo žena na obali čiji muževi nisu prisutni. Samim tim, kad zamenimo muškarce sa misionarima i žene sa kanibalima, bilo koje rešenje ovog problema biće i rešenje problema misionara i kanibala.

Rešavanje problema

Amarel je razvio sistem za rešavanje ovog problema tako što je trenutno stanje predstavio u obliku jednostavnog vektora <a.b.c>. Elementi vektora predstavljaju broj misionara na početnoj strani, broj kanibala na početnoj strani i broj čamaca na početnoj strani. S obzirom da čamac i svi misionari i kanibali počinju na pogrešnoj strani, vektor je inicijalizovan na <3,3,1>. Akcije su predstavljene sabiranjem ili oduzimanjem kako bi se manipulisalo stanjem vektora. Na primer, ako sam kanibal prelazi reku, vektor <0,1,1> bi bio oduzet od inicijalnog stanja i dobija se vektor <3,2,0>. Stanje reflektuje činjenicu da i dalje postoje tri misionara i dva kanibala na pogrešnoj strani, i da se čamac sad nalazi na suprotnoj strani. Kako bi se problem rešio u potpunosti, formirao je jednostavno stablo sa korenom koji predstavlja inicijalno stanje. Zatim se pet potencijalnih akcija (vektori <1,0,1>, <2,0,1>, <0,1,1>, <0,2,1> i <1,1,1>) oduzimaju od početnog stanja, pri čemu se formiraju deca čvorovi korena. Svaki čvor koji predstavlja stanje u kom na bilo kojoj obali ima više kanibala nego misionara je nevažeće stanje, i samim tim se oduzima iz narednih razmatranja. Važeća deca čvorovi su vektori <3,2,0>, <3,1,0>, i <2,2,0>. Za svaki od preostalih čvorova, deca čvorovi su generisani sabiranjem vektora svake od mogućih akcija. Algoritam nastavlja sa sabiranjem i oduzimanjem u svakom nivou stabla sve dok se ne izgeneriše čvor čija je vrednost vektora <0,0,0>. Ovo je ciljno stanje, i put od korena stabla do ovog čvora predstavlja sekvencu akcija koja rešava problem.

Rešenje problema

Najranije rešenje problema ljubomornih muževa, koristeći 11 putovanja u jednom smeru, nalazi se u tabeli ispod. Venčani parovi su prikazani: prvi par: α (muškarac) i a (žena), drugi par: β (muškarac) i b (žena), i treći par: γ (muškarac) i c (žena).

Broj putovanja	Početna obala	Putovanje	Završna obala
Početak	αaβbγc
1	βbγc	αa→
2	βbγc	←α	a
3	αβγ	bc→	a
4	αβγ	←a	bc
5	αa	Βγ→	bc
6	αa	←Βb	γc
7	ab	αβ→	γc
8	ab	←c	αβγ
9	b	ac→	αΒγ
10	b	←β	αaγc
11		βb→	αaγc
Kraj			αaβbγc

Ovo je najkraće ali ne i jedino najkraće rešenje. Kao što je već spomenuto, ovo rešenje problema ljubomornih muževa će biti i rešenje problema misionara i kanibala zamenom muškaraca i misionara, i žena i kanibala. U ovom slučaju možda ćemo zanemariti individualne identitete misionara i kanibala. Dobijeno rešenje će biti jedno od četiri najkraća moguća rešenja.

Varijacije

Očigledna generalizacija je variranje broja parova, kapaciteta čamca, ili oboje. Ako čamac može da primi samo dvoje, onda dva para zahtevaju pet putovanja; sa četiri ili više parova, ovaj problem ne može da se reši. Ako čamac može da prenese troje, u tom slučaju do pet parova može da pređe na drugu obalu. Ako brod može da preveze četvoro, bilo koji broj parova može da pređe na drugu obalu. Jednostavan prikaz ovog problema preko grafa radi analize i rešavanja ovih generalizacija dali su Frali, Kuk i Detrik 1966. godine. Ako dodamo i ostrvo u sredini reke, bilo koji broj parova može da je pređe koristeći brod koji može da preveze dvoje. Ako putovanja sa jedne na drugu obalu nisu dozvoljena, onda nam je potrebno 8n-6 putovanja u jednom smeru kako bi n parova prešlo reku. Ako su dozvoljena, onda je potrebno 4n+1 putovanja, ako je broj parova veći od 4, iako minimalno rešenje zahteva samo 16 putovanja ako je n jednak 4. Ako ljubomorne parove zamenimo misionarima i kanibalima, broj potrebnih putovanja se ne menja ako putovanja sa obale na obalu nisu dozvoljena. Ako su dozvoljena, broj putovanja se smanjuje na 4n-1, pod pretpostavkom da je n bar 3.

Istorija

Prva poznata pojava problema ljubomornih muževa nalazi se u srednjevekovnom tekstu "Propositiones ad Acuendos Juvenes", čije se poreklo pripisuje Alkuinu (umro 804.). U njegovoj formulaciji, parovi su braća i sestre, ali pravilo je isto - nijedna žena ne može biti u čamcu sa muškarcem osim ako je njen brat prisutan. Od 13. do 15. veka, ovaj problem je postao poznat širom Severne Evrope, pri čemu su se parovi promenili u muževe i žene. Formulacija problema sa misionarima i kanibalima se pojavila tek krajem 19. veka. Izmene u broju parova i veličini čamca su nastale na početku 16. veka. Kadet de Fontenaj je postavio ostrvo u centar reke 1879. godine. Ovu varijantu problema rešili su Ijan Presman i Dejvid Singmaster 1989. godine.