The Missionaries and Cannibals Problem

Game “Missionaries and Cannibals” merupakan salah satu game bergenre puzzle yang terkenal di dunia. Game ini bercerita tentang tiga orang misionaris dan tiga kanibal yang ingin menyebrang sungai. Untuk menyebrangi sungai tersebut disediakan perahu yang dapat digunakan oleh kanibal maupun misionaris. Pemain dikatakan berhasil memainkan permainan ini jika sampai akhir permainan jumlah misionaris dan kanibal masing masing tiga. Dan aturan pokok yang menjadi ciri-ciri dari permainan ini, yaitu jumlah kanibal tidak boleh lebih dari jumlah misionari di berbagai sisi. Jika jumlah kanibal lebih banyak dari misionari, maka kanibal akan memakan misionari dan permainan berakhir.

Problem Solving dari Game “Missionaries and Cannibals” dapat dideskripsikan dengan :

• ·     Initial state (status awal), 3 missionaries dan 3 Cannibals ada disisi kiri sungai.     
•       operator/fungsi successor, suatu perpindahan yang diwakili oleh jumlah missionaries dan jumlah cannibal pada satu waktu.
•       Path cost (biaya jalur), jumlah penyebrangan.
•       Goal test (uji tujuan), 3 missionaries dan 3 cannibals ada disisi kanan sungai.

Salah satu metode yang dipakai dalam pemecahan masalah pada game missionaries and cannibals ini adalah dengan Breadth First Search(BFS). Breadth First Search(BFS) adalah algoritma pencarian solusi yang melakukan pencarian pada graf atau pohon berakar secara melebar dengan cara mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Simpul yang belum dikunjungi dan bertetangga dengan simpul – simpul yang tadi dikunjungi, demikian seterusnya.

Pada puzzle ini tiap-tiap state dijadikan sebuah simpul pada pohon. Pada Missionaries and Cannibals, state awal adalah sisi daratan kiri masih kosong, dan sisi daratan kanan berisi 3 Misionaris dan 3 Kanibal. Agar mempermudah penggambaran, maka dibuat notasi untuk tiap-tiap simpul/state. Untuk state awal, notasinya adalah `(0,0)|(3,3)K` yang artinya, di sisi kiri ada 0 Misionaris 0 Kanibal, dan disisi kanan ada 3 Misionaris, 3 Kanibal dan perahu. State akhir notasinya adalah `K(3,3)|(0,0)`. Jika perahu ada di sisi kanan, maka yang dapat dipindahkan adalah Misionaris atau Kanibal yang berada di sisi kanan, dan sebaliknya.

Berikut pohon state yang dibuat, dari simpul state awal hingga simpul solusi :

Warna merah berarti state tersebut salah, merah + garis bawah

berarti state tersebut telah dikunjungi.

State Awal dari Missionaries and Cannibals

State Akhir dari Missionaries and Cannibals

Langkah-langkah Penyelesaian Game “Missionaries and Cannibals” : 

M1 = Misionaris 1

M2 = Misionaris 2

M3 = Misionaris 3

K1 = kanibal 1

K2 = kanibal 2

K3 = kanibal 3

1. Sebrangkan K1 dan K2 terlebih dahulu

2. Setelah sampai disebrangkan, keluarkan satu K1

3. lalu sebrangkan K2 dan masukan K3 lalu sebrangkan mereka.

4. keluarkan k2 dan sebrangkan k3

5. keluarkan k3 dan sebrangkan M1 dan M2

6. keluarkan M1 dan masukan K1, lalu sebrangkan mereka

7. keluarkan k1 dan masukan M3, lalu sebrangkan mereka

8. keluarkan M2 dan M3, lalu sebrangkan K2

9. Masukan K1, lalu sebrangkan mereka

10. Keluarkan K1 dan sebrangkan K2

11. Masukan K3 lalu sebrangkan mereka

Selesai

Analisis

Penggunaan algoritma BFS pada pencarian solusi puzzle Missionaries and Cannibals menghasilkan langkah-langkah menuju solusi yang optimal (terpendek), ini dikarenakan pencarian dilakukan secara melebar dari simpul akar hingga simpul akhir. Kekurangan penggunaan BFS disini, langkah proses pencarian lebih banyak dibandingkan dengan DFS, penggunaan ruang (memori) juga lebih banyak, karena tiap simpul anak-anak hasil ekspansi suatu simpul dimasukkan ke dalam antrian.

Referensi :

http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-007.pdf

https://komputasi.files.wordpress.com/2012/09/kecerdasan-buatan-02.pdf