Masalah misionaris dan kanibal

Grafik solusi Masalah Melintasi Sungai Suami-suami Pencemburu.

Masalah misionaris dan kanibal dan masalah suami-suami pencemburu adalah masalah melintasi sungai klasik. Masalah misionaris dan kanibal adalah sebuah permainan masalah terkenal dalam kecerdasan buatan, dimana masalah tersebut dipakai oleh Saul Amarel sebagai contoh representasi masalah.

Masalah

Dalam masalah misionaris dan kanibal, tiga misionaris dan tiga kanibal harus melintasi sebuah sungai memakai sebuah perahu yang hanya dapat menampung dua orang. Permasalahannya adalah, untuk kedua tepian sungai tersebut, jika misionaris ada pada satu tepi, mereka tak boleh kalah jumlah dengan para kanibal (jika demikian, kanibal akan menyantap misionaris). Perahu tak dapat melintasi sungai sendiri dengan tanpa ada orang yang ada di perahu tersebut. Dan dalam beberapa variasi, salah satu kanibal hanya memiliki satu lengan dan tak dapat berbaris.

Dalam masalah suami-suami pencemburu, para misionaris dan kanibal diganti menjadi tiga pasangan suami istri, dengan permasalahan bahwa tidak ada wanita yang dapat berada dengan pria lain tanpa ada suaminya yang juga hadir. Dalam permasalahan tersebut, tak ada wanita dan pria yang berada di sebuah tepi sungai dengan wanita yang kalah jumlah dengan pria, karena jika demikian, wanita tersebut berada dalam keadaan tanpa suami mereka. Sehingga, saat mengubah pria menjadi misionaris dan wanita menjadi kanibal, solusi apapun terhadap masalah suami-suami pencemburu juga akan menjadi solusi terhadap masalah misionaris dan kanibal.

Solusi

Solusi terawal yang diketahui terhadap masalah suami-suami pencemburu, memakai 11 pergerakan satu arah, adalah sebagai berikut. Pasangan-pasangan suami-istri diwakili sebagai α (laki-laki) dan a (perempuan), β dan b, and γ dan c.^, p. 291.

Angka pergerakan	Tepi awal	Pergerakan	Tepi akhir
(awal)	αa βb γc
1	βb γc	αa →
2	βb γc	←α	a
3	α β γ	bc →	a
4	α β γ	← a	b c
5	αa	βγ →	b c
6	αa	← βb	γc
7	a b	αβ →	γc
8	a b	← c	α β γ
9	b	a c →	α β γ
10	b	← β	αa γc
11		βb →	αa γc
(akhir)			αa βb γc

Ini adalah solusi tersingkat terhadap masalah tersebut, tetapi bukan satu-satunya solusi tersingkat.^, p. 291.

Jumlah kunjungan	Tepi awal	Perjalanan	Tepi akhir
(awal)	αa βb γc
1	βb γc	αa →
2	βb γc	← a	α
3	β γc	ab →	α
4	β γc	← b	αa
5	γc	βb →	αa
6	γc	← b	αa β
7	γ	bc →	αa β
8	γ	← c	αa βb
9		γc →	αa βb
(akhir)			αa βb γc

Sejarah

Kemunculan pertama yang diketahui dari masalah suami-suami pencemburu ada dalam teks abad pertengahan Propositiones ad Acuendos Juvenes, biasanya diatributkan kepada Alcuin (wafat 804). Dalam perumusan Alcuin, pasangan-pasangan tersebut adalah para saudara dan saudari, tetapi hambatannya masih sama—tak ada wanita yang dapat bersama dengan pria lain tanpa kehadiran saudaranya.^, p. 74. Dari abad ke-13 sampai ke-15, masalah tersebut diketahui di seluruh belahan Eropa Utara, dengan pasangan-pasangan tersebut saat ini disebut para suami dan istri.^{, pp. 291–293.} Masalah tersebut kemudian ditempatkan dalam bentuk para tuan dan pelayan; perumusan dengan para misionaris dan kanibal belum muncul sampai akhir abad ke-19.^, p. 81 Jumlah pasangan dan ukuran perahu yang diragamkan muncul pada permulaan abad ke-16.^, p. 296. Cadet de Fontenay menempatkan sebuah pulau di tengah sungai pada 1879; sebuah ragam dari masalah tersebut, dengan perahu dua orang, sepenuhnya dipecahkan oleh Ian Pressman dan David Singmaster pada 1989.