Задача про місіонерів та канібалів

Зада́ча про місіонерів і канібалів, а також тісно пов'язана з ними задача про ревнивого чоловіка. — класичні приклади «задач про перетин річки». Ця задача — іграшкова проблема в галузі штучного інтелекту, де вона була використана як приклад .

Задача

Троє місіонерів і троє канібалів мають перетнути річку за допомогою човна, що здатен витримати не більше двох осіб. Є одне обмеження: канібалів на березі не може залишатися більше, ніж місіонерів (бо якщо канібали в більшості, то можуть з'їсти місіонерів). Також човен не може перетнути річку сам по собі, без людей на борту.

Задача ревнивих чоловіків. Замість місіонерів і канібалів є троє одружених пар. Обмеження полягає в тому, що жодна жінка не може перебувати в присутності іншого чоловіка, якщо її чоловіка поряд нема. Відповідно до цього обмеження, кількість жінок на березі не може перевищувати кількість чоловіків, якщо там є хоча б один чоловік. Таким чином, при заміні чоловіків — місіонерами, а жінок — людожерами, будь-який розв'язок задачі ревнивого чоловіка буде також розв'язком задачі про місіонерів та канібалів.

Історія

Вперше задача про ревнивих чоловіків з'явилася в середньовічному тексті «Propositiones» автора Juvenes Acuendos, якого зазвичай пов'язують з Алкуїном (помер 804 року). У формулюванні Алкуїна є пари братів і сестер, але обмежуючий фактор усе той же — жодна жінка не може залишатися з іншими чоловіками, якщо її брата немає поруч. З 13 по 15 століття, задача стала відомою в усій Північній Європі, вже описуючи чоловіків та дружин. Пізніше задачу формулювали в термінах майстрів та слуг. Варіант із місіонерами та людожерами з'явився наприкінці 19 сторіччя.

Рішення

Амарель розробив систему для розв'язку «задачі місіонерів і канібалів». Поточний стан задачі являє собою вектор <a,b,c>. Елементами вектора є: кількість місіонерів, кількість канібалів і кількість суден на тому березі, з якого починається переправа. Якщо спочатку там перебувають човен, і всі місіонери та канібали, то початковий вектор (вектор ініціалізації) буде <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 поїздок в один кінець, полягає в наступному. Подружні пари представлені у вигляді ${\displaystyle \alpha }$ (Чоловіки) і ${\displaystyle \beta }$ (жінка) ^, p. 291.

Номер	Початковий берег	Переїзд	Кінцевий берег
(start)	${\displaystyle \alpha }$a ${\displaystyle \beta }$b ${\displaystyle \gamma }$c
1	${\displaystyle \beta }$b ${\displaystyle \gamma }$c	${\displaystyle \alpha }$a →
2	${\displaystyle \beta }$b ${\displaystyle \gamma }$c	←${\displaystyle \alpha }$	a
3	${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$	bc →	a
4	${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$	← a	b c
5	${\displaystyle \alpha }$a	${\displaystyle \beta }$${\displaystyle \gamma }$ →	b c
6	${\displaystyle \alpha }$a	← ${\displaystyle \beta }$b	${\displaystyle \gamma }$c
7	a b	${\displaystyle \alpha }$${\displaystyle \beta }$ →	${\displaystyle \gamma }$c
8	a b	← c	${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$
9	b	a c →	${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$
10	b	← ${\displaystyle \beta }$	${\displaystyle \alpha }$a ${\displaystyle \gamma }$c
11		${\displaystyle \beta }$b →	${\displaystyle \alpha }$a ${\displaystyle \gamma }$c
(finish)			${\displaystyle \alpha }$a ${\displaystyle \beta }$b ${\displaystyle \gamma }$c

Це найкоротший варіант вирішення проблеми, але це не єдине найкоротше рішення. Якщо, тільки одна людина може вийти з човна в один час, а чоловік повинен бути на березі, щоб рахуватися з його дружиною, а не тільки перебувати в човні на березі: рух від 5 до 6 неможливо, так як тільки як жінка вийшла на берег- вона не буде з чоловіком, незважаючи на його буття тільки в човні. Як згадувалося раніше, це рішення для «задачі про ревнивого чоловіка» стане рішенням для «Задачі місіонерів і канібалів» при заміні чоловіків і жінок місіонерами і канібалами. В цьому випадку можна знехтувати окремими особистостями місіонерів і канібалів. Рішення тільки так як і раніше, проте коротше і є одним з чотирьох найкоротшіх рішень. Якщо жінка в човні на березі (але не на березі) вважається як самостійна (тобто не в присутності будь-якого чоловіка на березі), то ця загадка може бути вирішена в 9 поїздок в один кінець:

Номер	Початковий берег	Переїзд	Кінцевий берег
(start)	${\displaystyle \alpha }$a ${\displaystyle \beta }$b ${\displaystyle \gamma }$c
1	${\displaystyle \beta }$b ${\displaystyle \gamma }$c	${\displaystyle \alpha }$a →
2	${\displaystyle \beta }$b ${\displaystyle \gamma }$c	← a	${\displaystyle \alpha }$
3	${\displaystyle \beta }$ ${\displaystyle \gamma }$c	ab →	${\displaystyle \alpha }$
4	${\displaystyle \beta }$ ${\displaystyle \gamma }$c	← b	${\displaystyle \alpha }$a
5	${\displaystyle \gamma }$c	${\displaystyle \beta }$b →	${\displaystyle \alpha }$a
6	${\displaystyle \gamma }$c	← b	${\displaystyle \alpha }$a ${\displaystyle \beta }$
7	${\displaystyle \gamma }$	bc →	${\displaystyle \alpha }$a ${\displaystyle \beta }$
8	${\displaystyle \gamma }$	← c	${\displaystyle \alpha }$a ${\displaystyle \beta }$b
9		${\displaystyle \gamma }$c →	${\displaystyle \alpha }$a ${\displaystyle \beta }$b
(finish)			${\displaystyle \alpha }$a ${\displaystyle \beta }$b ${\displaystyle \gamma }$c

Розв'язання на Prolog

 /*1 kannibal*/ move(state(X,K2,K3,M1,M2,M3),state(Y,K2,K3,M1,M2,M3)):-opposite(X,Y). move(state(K1,X,K3,M1,M2,M3),state(K1,Y,K3,M1,M2,M3)):-opposite(X,Y). move(state(K1,K2,X,M1,M2,M3),state(K1,K2,Y,M1,M2,M3)):-opposite(X,Y). /*2 kannibala*/ move(state(X,X,K3,M1,M2,M3),state(Y,Y,K3,M1,M2,M3)):-opposite(X,Y). move(state(X,K2,X,M1,M2,M3),state(Y,K2,Y,M1,M2,M3)):-opposite(X,Y). move(state(K1,X,X,M1,M2,M3),state(K1,Y,Y,M1,M2,M3)):-opposite(X,Y). /*3 kannibala*/ move(state(X,X,X,M1,M2,M3),state(Y,Y,Y,M1,M2,M3)):-opposite(X,Y). /*1 missioner*/ move(state(K1,K2,K3,X,M2,M3),state(K1,K2,K3,Y,M2,M3)):-opposite(X,Y). move(state(K1,K2,K3,M1,X,M3),state(K1,K2,K3,M1,Y,M3)):-opposite(X,Y). move(state(K1,K2,K3,M1,M2,X),state(K1,K2,K3,M1,M2,Y)):-opposite(X,Y). /*2 missionera*/ move(state(K1,K2,K3,X,X,M3),state(K1,K2,K3,Y,Y,M3)):-opposite(X,Y). move(state(K1,K2,K3,M1,X,X),state(K1,K2,K3,M1,Y,Y)):-opposite(X,Y). move(state(K1,K2,K3,X,M2,X),state(K1,K2,K3,Y,M2,Y)):-opposite(X,Y). /*3 missionera*/ move(state(K1,K2,K3,X,X,X),state(K1,K2,K3,Y,Y,Y)):-opposite(X,Y). /*1 kannibal, 1 missioner*/ move(state(X,K2,K3,X,M2,M3),state(Y,K2,K3,Y,M2,M3)):-opposite(X,Y). move(state(K1,X,K3,X,M2,M3),state(K1,Y,K3,Y,M2,M3)):-opposite(X,Y). move(state(K1,K2,X,X,M2,M3),state(K1,K2,Y,Y,M2,M3)):-opposite(X,Y). move(state(X,K2,K3,M1,X,M3),state(Y,K2,K3,M1,Y,M3)):-opposite(X,Y). move(state(K1,X,K3,M1,X,M3),state(K1,Y,K3,M1,Y,M3)):-opposite(X,Y). move(state(K1,K2,X,M1,X,M3),state(K1,K2,Y,M1,Y,M3)):-opposite(X,Y). move(state(X,K2,K3,M1,M2,X),state(Y,K2,K3,M1,M2,Y)):-opposite(X,Y). move(state(K1,X,K3,M1,M2,X),state(K1,Y,K3,M1,M2,Y)):-opposite(X,Y). move(state(K1,K2,X,M1,M2,X),state(K1,K2,Y,M1,M2,Y)):-opposite(X,Y). /*1 kannibal, 2 missionera*/ move(state(X,K2,K3,X,X,M3),state(Y,K2,K3,Y,Y,M3)):-opposite(X,Y). move(state(X,K2,K3,M1,X,X),state(Y,K2,K3,M1,Y,Y)):-opposite(X,Y). move(state(X,K2,K3,X,M2,X),state(Y,K2,K3,Y,M2,Y)):-opposite(X,Y). move(state(K1,X,K3,X,X,M3),state(Y,K2,K3,Y,Y,M3)):-opposite(X,Y). move(state(K1,X,K3,M1,X,X),state(K1,Y,K3,M1,Y,Y)):-opposite(X,Y). move(state(K1,X,K3,X,M2,X),state(K1,Y,K3,Y,M2,Y)):-opposite(X,Y). move(state(K1,K2,X,X,X,M3),state(K1,K2,Y,Y,Y,M3)):-opposite(X,Y). move(state(K1,K2,X,M1,X,X),state(K1,K2,Y,M1,Y,Y)):-opposite(X,Y). move(state(K1,K2,X,X,M2,X),state(K1,K2,Y,Y,M2,Y)):-opposite(X,Y). opposite(east,west). opposite(west,east). /*2 kannibala, 1 missioner*/ unsafe(state(X1,X2,X3,Y1,Y2,Y3)):- X1 = east,X2 = east,Y1 = east; X1 = east,X3 = east,Y1 = east; X2 = east,X3 = east,Y1 = east; X1 = east,X2 = east,Y2 = east; X1 = east,X3 = east,Y2 = east; X2 = east,X3 = east,Y2 = east; X1 = east,X2 = east,Y3 = east; X1 = east,X3 = east,Y3 = east; X2 = east,X3 = east,Y3 = east; X1 = west,X2 = west,Y1 = west; X1 = west,X3 = west,Y1 = west; X2 = west,X3 = west,Y1 = west; X1 = west,X2 = west,Y2 = west; X1 = west,X3 = west,Y2 = west; X2 = west,X3 = west,Y2 = west; X1 = west,X2 = west,Y3 = west; X1 = west,X3 = west,Y3 = west; X2 = west,X3 = west,Y3 = west; X1 = east,X2 = east,X3 = east,Y1 = east; X1 = east,X2 = east,X3 = east,Y2 = east; X1 = east,X2 = east,X3 = east,Y3 = east; X1 = west,X2 = west,X3 = west,Y1 = west; X1 = west,X2 = west,X3 = west,Y2 = west; X1 = west,X2 = west,X3 = west,Y3 = west; X1 = east,X2 = east,X3 = east,Y1 = east,Y2 = east; X1 = east,X2 = east,X3 = east,Y1 = east,Y3 = east; X1 = east,X2 = east,X3 = east,Y2 = east,Y3 = east; X1 = west,X2 = west,X3 = west,Y1 = west,Y2 = west; X1 = west,X2 = west,X3 = west,Y1 = west,Y3 = west; X1 = west,X2 = west,X3 = west,Y2 = west,Y3 = west. path(Start,Finish,L,L1):- move(Start,S1), not(unsafe(S1)), not(member(S1,L)), path(S1,Finish,[S1|L],L1),!. path(Finish,Finish,T,T):-!. /* The final state is reached */ go:-go(state(east,east,east,east,east,east),state(west,west,west,west,west,west)). go(Start,Finish):- path(Start,Finish,[Start],L), nl,write("A solution is:"),nl, write_path(L), fail. go(_,_). member(X,[X|_]). member(X,[_|L]):-member(X,L). /*1 kannibal*/ write_move(state(X,K2,K3,M1,M2,M3),state(Y,K2,K3,M1,M2,M3)):-!, write("1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,X,K3,M1,M2,M3),state(K1,Y,K3,M1,M2,M3)):-!, write("1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,X,M1,M2,M3),state(K1,K2,Y,M1,M2,M3)):-!, write("1 kannibal goes from"), write(X), write(" to "), write(Y),nl. /*2 kannibala */ write_move(state(X,X,K3,M1,M2,M3),state(Y,Y,K3,M1,M2,M3)):-!, write("2 kannibala goes from"), write(X), write(" to "), write(Y),nl. write_move(state(X,K2,X,M1,M2,M3),state(Y,K2,Y,M1,M2,M3)):-!, write("2 kannibala goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,X,X,M1,M2,M3),state(K1,Y,Y,M1,M2,M3)):-!, write("2 kannibala goes from"), write(X), write(" to "), write(Y),nl. /*3 kannibala*/ write_move(state(X,X,X,M1,M2,M3),state(Y,Y,Y,M1,M2,M3)):-!, write("3 kannibala goes from"), write(X), write(" to "), write(Y),nl. /*1 missioner*/ write_move(state(K1,K2,K3,X,M2,M3),state(K1,K2,K3,Y,M2,M3)):-!, write("1 missioner goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,K3,M1,X,M3),state(K1,K2,K3,M1,Y,M3)):-!, write("1 missioner goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,K3,M1,M2,X),state(K1,K2,K3,M1,M2,Y)):-!, write("1 missioner goes from"), write(X), write(" to "), write(Y),nl. /*2 missionera*/ write_move(state(K1,K2,K3,X,X,M3),state(K1,K2,K3,Y,Y,M3)):-!, write("2 missionera goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,K3,M1,X,X),state(K1,K2,K3,M1,Y,Y)):-!, write("2 missionera goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,K3,X,M2,X),state(K1,K2,K3,Y,M2,Y)):-!, write("2 missionera goes from"), write(X), write(" to "), write(Y),nl. /*3 missionera*/ write_move(state(K1,K2,K3,X,X,X),state(K1,K2,K3,Y,Y,Y)):-!, write("3 missionera goes from"), write(X), write(" to "), write(Y),nl. /*1 kannibal, 1 missioner*/ write_move(state(X,K2,K3,X,M2,M3),state(Y,K2,K3,Y,M2,M3)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,X,K3,X,M2,M3),state(K1,Y,K3,Y,M2,M3)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,X,X,M2,M3),state(K1,K2,Y,Y,M2,M3)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(X,K2,K3,M1,X,M3),state(Y,K2,K3,M1,Y,M3)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,X,K3,M1,X,M3),state(K1,Y,K3,M1,Y,M3)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,X,M1,X,M3),state(K1,K2,Y,M1,Y,M3)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(X,K2,K3,M1,M2,X),state(Y,K2,K3,M1,M2,Y)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,X,K3,M1,M2,X),state(K1,Y,K3,M1,M2,Y)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,X,M1,M2,X),state(K1,K2,Y,M1,M2,Y)):-!, write("1 missioner, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. /*1 kannibal, 2 missionera*/ write_move(state(X,K2,K3,X,X,M3),state(Y,K2,K3,Y,Y,M3)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(X,K2,K3,M1,X,X),state(Y,K2,K3,M1,Y,Y)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(X,K2,K3,X,M2,X),state(Y,K2,K3,Y,M2,Y)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,X,K3,X,X,M3),state(Y,K2,K3,Y,Y,M3)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,X,K3,M1,X,X),state(K1,Y,K3,M1,Y,Y)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,X,K3,X,M2,X),state(K1,Y,K3,Y,M2,Y)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,X,X,X,M3),state(K1,K2,Y,Y,Y,M3)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,X,M1,X,X),state(K1,K2,Y,M1,Y,Y)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_move(state(K1,K2,X,X,M2,X),state(K1,K2,Y,Y,M2,Y)):-!, write("2 missionera, 1 kannibal goes from"), write(X), write(" to "), write(Y),nl. write_path([H1,H2|T]):-!, write_move(H1,H2),write_path([H2|T]). write_path(_). ?-go. 

Варіації

Очевидним узагальненням є зміна числа ревнивих пар (або місіонерів і канібалів), місткість судна, або обох параметрів. Якщо човен вміщує 2 осіб, то 2 пари вимагають 5 поїздок, від 4 або більше пар, завдання не має рішення.

Якщо човен може вмістити 3 чоловік, то може перевезти до 5 пар, якщо човен може містити 4-х осіб, то можливо перевезти будь-яку кількість пар.

Якщо в середині річки додати острів, то потім будь-яке число пар може перетнути річку за допомогою двох чоловік.

Див. також

• Загадка про лисицю, гуску та мішок бобів
• Ріка (інтелектуальна гра)
• Задача про вовка, козу і капусту

Посилання

1. Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia, Raffaella Franci, pp. 289—306, From China to Paris: 2000 Years Transmission of Mathematical Ideas, edited by Yvonne Dold-Samplonius, Joseph W. Dauben, Menso Folkerts, and Benno van Dalen, Stuttgart: Franz Steiner Verlag, 2002, .