Lihat sumber Masalah misionaris dan kanibal

'''Masalah misionaris dan kanibal''' dan '''masalah suami-suami pencemburu''' adalah [[masalah melintasi sungai]] klasik.<ref>[https://archive.org/details/sim_mathematical-gazette_1989-06_73_464/page/73 'The Jealous Husbands' and 'The Missionaries and Cannibals']. ''The Mathematical Gazette''. June 1989. Vol. 73 (464).</ref> Masalah misionaris dan kanibal adalah sebuah [[permainan masalah]] terkenal dalam [[kecerdasan buatan]], di mana masalah tersebut dipakai oleh [[Saul Amarel]] sebagai contoh representasi masalah.<ref>Saul Amarel. [http://www.cc.gatech.edu/~jimmyd/summaries/amarel1968-1.html On representations of problems of reasoning about actions]. ''Machine Intelligence''. Elsevier/North-Holland. 1968. Vol. 3.</ref><ref>Roberto Cordeschi. ''Searching in a Maze, in Search of Knowledge: Issues in Early Artificial Intelligence''. ''Reasoning, Action and Interaction in AI Theories and Systems: essays dedicated to Luigia Carlucci Aiello''. Springer. 2006. Vol. 4155. doi:10.1007/11829263_1. ISBN 978-3-540-37901-0.</ref>

== 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.<ref>[https://archive.org/details/sim_mathematical-gazette_1989-06_73_464/page/73 'The Jealous Husbands' and 'The Missionaries and Cannibals']. ''The Mathematical Gazette''. June 1989. Vol. 73 (464).</ref>

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.<ref>[https://archive.org/details/sim_mathematical-gazette_1989-06_73_464/page/73 'The Jealous Husbands' and 'The Missionaries and Cannibals']. ''The Mathematical Gazette''. June 1989. Vol. 73 (464).</ref>

== 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''.<ref>Raffaella Franci. ''Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia''. ''From China to Paris: 2000 Years Transmission of Mathematical Ideas''. Franz Steiner Verlag. 2002. ISBN 3-515-08223-9.</ref><sup>,&nbsp;p.&nbsp;291.</sup>

{| class="wikitable"
! 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.<ref>Raffaella Franci. ''Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia''. ''From China to Paris: 2000 Years Transmission of Mathematical Ideas''. Franz Steiner Verlag. 2002. ISBN 3-515-08223-9.</ref><sup>,&nbsp;p.&nbsp;291.</sup>

{| class="wikitable"
! 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.<ref>[https://archive.org/details/sim_mathematical-gazette_1989-06_73_464/page/73 'The Jealous Husbands' and 'The Missionaries and Cannibals']. ''The Mathematical Gazette''. June 1989. Vol. 73 (464).</ref><sup>,&nbsp;p.&nbsp;74.</sup> 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.<ref>Raffaella Franci. ''Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia''. ''From China to Paris: 2000 Years Transmission of Mathematical Ideas''. Franz Steiner Verlag. 2002. ISBN 3-515-08223-9.</ref><sup>,&nbsp;pp.&nbsp;291–293.</sup> Masalah tersebut kemudian ditempatkan dalam bentuk para tuan dan pelayan; perumusan dengan para misionaris dan kanibal belum muncul sampai akhir abad ke-19.<ref>[https://archive.org/details/sim_mathematical-gazette_1989-06_73_464/page/73 'The Jealous Husbands' and 'The Missionaries and Cannibals']. ''The Mathematical Gazette''. June 1989. Vol. 73 (464).</ref><sup>,&nbsp;p.&nbsp;81</sup> Jumlah pasangan dan ukuran perahu yang diragamkan muncul pada permulaan abad ke-16.<ref>Raffaella Franci. ''Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia''. ''From China to Paris: 2000 Years Transmission of Mathematical Ideas''. Franz Steiner Verlag. 2002. ISBN 3-515-08223-9.</ref><sup>,&nbsp;p.&nbsp;296.</sup> 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.<ref>[https://archive.org/details/sim_mathematical-gazette_1989-06_73_464/page/73 'The Jealous Husbands' and 'The Missionaries and Cannibals']. ''The Mathematical Gazette''. June 1989. Vol. 73 (464).</ref>

== Referensi ==
<references />

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Masalah+misionaris+dan+kanibal&oldid=29569521 Wikipedia bahasa Indonesia], revisi 29569521 (2026-08-13T04:14:27Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

<!-- WIKI_UNISSULA_PRESENTATION_V4 -->