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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Задача[ред.ред. код]

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

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

Історія[ред.ред. код]

Перша відома поява Задачі про ревнивих чоловіків — в середньовічному тексті 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 поїздок в один кінець, полягає в наступному. Подружні пари представлені у вигляді \alpha (Чоловіки) і \beta (жінка) [1] , p. 291.

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

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

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

Розв'язання на 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, ISBN 3515082239.