Проблем мисионара и канибала
Проблем мисионара и канибала, као и проблем љубоморних мужева, представља класичан проблем преласка реке.[1] Овај проблем је врло добро познат као пример показатељ у вештачкој интелигенцији, где га је Саул Амарел користио као пример представљања проблема.[2][3]
Проблем уреди
У овом проблему, три мисионара и три канибала треба да пређу реку користећи брод који може да превезе највише двоје, под претпоставком да, ако је бар један мисионар на броду, не сме бити надмашен у бројности од стране канибала, јер би га у том случају појели. Чамац не може сам да пређе реку, тј. без икога ко би њиме управљао. У неким варијацијама овог проблема, један од канибала има само једну руку тако да не може да весла.
Што се тиче проблема љубоморних мужева, мисионари и канибали су у ствари три венчана пара. Постоји услов да ниједна жена не може бити са другим мушкарцем у чамцу осим ако је њен муж присутан. С обзиром на овај услов, на обали не може бити више жена него мужева, јер би у том случају свакако било жена на обали чији мужеви нису присутни. Самим тим, кад заменимо мушкарце са мисионарима и жене са канибалима, било које решење овог проблема биће и решење проблема мисионара и канибала.
Решавање проблема уреди
Амарел је развио систем за решавање овог проблема тако што је тренутно стање представио у облику једноставног вектора <a.b.c>.[4] Елементи вектора представљају број мисионара на почетној страни, број канибала на почетној страни и број чамаца на почетној страни. С обзиром да чамац и сви мисионари и канибали почињу на погрешној страни, вектор је иницијализован на <3,3,1>. Акције су представљене сабирањем или одузимањем како би се манипулисало стањем вектора. На пример, ако сам канибал прелази реку, вектор <0,1,1> би био одузет од иницијалног стања и добија се вектор <3,2,0>. Стање рефлектује чињеницу да и даље постоје три мисионара и два канибала на погрешној страни, и да се чамац сад налази на супротној страни. Како би се проблем решио у потпуности, формирао је једноставно стабло са кореном који представља иницијално стање. Затим се пет потенцијалних акција (вектори <1,0,1>, <2,0,1>, <0,1,1>, <0,2,1> и <1,1,1>) одузимају од почетног стања, при чему се формирају деца чворови корена. Сваки чвор који представља стање у ком на било којој обали има више канибала него мисионара је неважеће стање, и самим тим се одузима из наредних разматрања. Важећа деца чворови су вектори <3,2,0>, <3,1,0>, и <2,2,0>. За сваки од преосталих чворова, деца чворови су генерисани сабирањем вектора сваке од могућих акција. Алгоритам наставља са сабирањем и одузимањем у сваком нивоу стабла све док се не изгенерише чвор чија је вредност вектора <0,0,0>. Ово је циљно стање, и пут од корена стабла до овог чвора представља секвенцу акција која решава проблем.
Решење проблема уреди
Најраније решење проблема љубоморних мужева, користећи 11 путовања у једном смеру, налази се у табели испод. Венчани парови су приказани: први пар: α (мушкарац) и a (жена), други пар: β (мушкарац) и b (жена), и трећи пар: γ (мушкарац) и c (жена).
| Број путовања | Почетна обала | Путовање | Завршна обала |
|---|---|---|---|
| Почетак | αаβbγc | ||
| 1 | βbγc | αa→ | |
| 2 | βbγc | ←α | a |
| 3 | αβγ | bc→ | a |
| 4 | αβγ | ←а | 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 | |
| Крај | αaβbγc |
Ово је најкраће али не и једино најкраће решење. Као што је већ споменуто, ово решење проблема љубоморних мужева ће бити и решење проблема мисионара и канибала заменом мушкараца и мисионара, и жена и канибала. У овом случају можда ћемо занемарити индивидуалне идентитете мисионара и канибала. Добијено решење ће бити једно од четири најкраћа могућа решења.
Варијације уреди
Очигледна генерализација је варирање броја парова, капацитета чамца, или обоје. Ако чамац може да прими само двоје, онда два пара захтевају пет путовања; са четири или више парова, овај проблем не може да се реши. Ако чамац може да пренесе троје, у том случају до пет парова може да пређе на другу обалу. Ако брод може да превезе четворо, било који број парова може да пређе на другу обалу. Једноставан приказ овог проблема преко графа ради анализе и решавања ових генерализација дали су Фрали, Кук и Детрик 1966. године. Ако додамо и острво у средини реке, било који број парова може да је пређе користећи брод који може да превезе двоје. Ако путовања са једне на другу обалу нису дозвољена, онда нам је потребно 8н-6 путовања у једном смеру како би н парова прешло реку. Ако су дозвољена, онда је потребно 4н+1 путовања, ако је број парова већи од 4, иако минимално решење захтева само 16 путовања ако је н једнак 4. Ако љубоморне парове заменимо мисионарима и канибалима, број потребних путовања се не мења ако путовања са обале на обалу нису дозвољена. Ако су дозвољена, број путовања се смањује на 4н-1, под претпоставком да је н бар 3.
Историја уреди
Прва позната појава проблема љубоморних мужева налази се у средњевековном тексту "Propositiones ad Acuendos Juvenes", чије се порекло приписује Алкуину (умро 804.). У његовој формулацији, парови су браћа и сестре, али правило је исто - ниједна жена не може бити у чамцу са мушкарцем осим ако је њен брат присутан. Од 13. до 15. века, овај проблем је постао познат широм Северне Европе, при чему су се парови променили у мужеве и жене. Формулација проблема са мисионарима и канибалима се појавила тек крајем 19. века. Измене у броју парова и величини чамца су настале на почетку 16. века. Кадет де Фонтенај је поставио острво у центар реке 1879. године. Ову варијанту проблема решили су Ијан Пресман и Дејвид Сингмастер 1989. године.
Референце уреди
- ^ Pressman, Ian; Singmaster, David (1989). „'The Jealous Husbands' and 'The Missionaries and Cannibals'”. The Mathematical Gazette. 73 (464): 73–81. JSTOR 3619658.
- ^ Amarel, Saul (1968). Michie, Donald, ур. „On representations of problems of reasoning about actions”. Machine Intelligence. Amsterdam, London, New York: Elsevier/North-Holland. 3: 131–171. Архивирано из оригинала 8. 3. 2008. г.
- ^ Cordeschi, Roberto (2006). „Searching in a Maze, in Search of Knowledge: Issues in Early Artificial Intelligence”. Ур.: Stock, Oliviero; Schaerf, Marco. Reasoning, Action and Interaction in AI Theories and Systems: essays dedicated to Luigia Carlucci Aiello. Lecture Notes in Computer Science. 4155. Berlin/Heidelberg: Springer. стр. 1–23. ISBN 978-3-540-37901-0. doi:10.1007/11829263_1.
- ^ Franci, Raffaella (2002). „Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia”. Ур.: Dold-Samplonius, Yvonne; Dauben, Joseph W.; Folkerts, Menso; van Dalen, Benno. From China to Paris: 2000 Years Transmission of Mathematical Ideas. Stuttgart: Franz Steiner Verlag. стр. 289–306. ISBN 3-515-08223-9.