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 menyebarang 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 cirri 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.
Constraint Puzzle
Game “Missionaries and Cannibals” terasa lebihsulit ketika diberikan aturan – aturan yang harusdipatuhi oleh pemain. Aturan – aturan tersebut antara lain:
• Ada tiga misionaris dan tiga kanibal yang harus menyebrang sungai.
• Hanya disediakan satu perahu.
• Perahu bisa berjalan jika ada minimal satu orang atau satu kanibal (satu
penumpang).
• Perahu maksimaum berisi dua (1 kanibal/1 misionaris /2 kanibal /2
misionaris)
• Jumlah kanibal tidak boleh lebih banyak dari jumlah misionaris di salah satu sisi
daratan.
• Jika jumlah kanibal lebih banyak dari jumlah misionaris pada suatu sisi daratan
maka kanibal akan memakan misionaris.
• Pemain berhasil menyelesaikan permainan jika semua misionaris dan
semua kanibal ada di sisi seberang yang menjadi tujuan.
Algoritma Breadth-First Search
Pengertian
Breadth First Search adalah algoritma pencarian solusi yang melakukan pencarian pada graf atau pohon berakar secara melebar dengan caramengunjungi 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 - simpulyang tadi dikunjungi , demikian seterusnya.Jika diilustrasikan dalam pohon berakar, makasemua simpul pada x dikunjungi lebih dahulu sebelum simpul-simpul pada x + 1. Algoritma ini memerlukan sebuah antrian (queue) Q untuk dapat menyimpan simpul yang telah dikunjungi. Setiap simpul yang telah dikunjungi
Prinsip Pencarian Solusi pada BFS
Secara umum, prinsip pencarian solusi dengan algoritma Breadth First Search (BFS) dimulai dengan simpul akar (simpul akar terlebih dahulu dimasukkan dalam antrian, lalu di pop()), lalu mengekspansi simpul-simpul anak dari dari simpul akar, dan memasukkan simpul anak dalam sebuah antrian. Antrian tadi digunakan untuk memberikantanda pada simpul – simpul tetangga yang nantinya akan dikunjungi berdasarkan urutan yang ada pada antrian. Penjabaran dari langkah – langkah pada prinsip pencarian solusi dengan algoritma BFS ini adalah sebagai berikut :
- Akar dimasukkan dalam antrian (Simpulpaling awal yang akan dikunjungi).
- Simpul yang ada pada awal antrian diambil dan dilakukan pengecekan untuk mengetahui status simpul tersebut sebagai solusi permasalahan atau tidak, dan mengekspansi anak-anaknya jika ada.
- Jika simpul yang sudah dicek tadi merupakan solusi permasalahan, pencarian selesai dan hasil dikembalikan.
- Jika simpul yang sudah dicek sebelumnya bukan merupakan solusi permasalahan,
semua simpul yang bertetanggan dengan simpul tadi (simpul anak) dimasukkan
kedalam antrian.
- Jika antrian ternyata telah kosong dan semua simpul sudah dicek maka status pencarian selesai dan berarti solusi tidak ditemukan.
- Hal ini dilakukan secara berulang (simpul berisi solusi ditemukan/sampai antrian
kosong)
PENERAPAN BFS PADA PUZZLE
Tiap-tiap state pada puzzle dijadikan sebuahsimpul 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, makayang dapat dipindahkan adalah Misionaris atau
Kanibal yang berada di sisi kanan, dan sebaliknya.Pada tahap pencarian, state awal dimasukkan kedalam antrian, dan dikunjungi paling awal (pertamadi-dequeue), dari state awal, diexpand anak-anak dari simpul state awal tersebut, dan masing-masing
anak dimasukkan ke dalam antrian (di-enqueue).Kunjungi simpul pada antrian paling awal(di-dequeue), dan periksa simpul tersebut. Apabila pada simpul yang dikunjungi memiliki lebih banyak kanibal daripada misionaris pada suatu sisi, maka
state pada simpul tersebut merupakan state salah,dan tidak usah di-expand. Simpul yang dikunjungi juga dimasukkan pada tabel boolean sebagai penanda bahwa simpul tersebut telah dikunjungi agar simpul tersebut tidak dikunjungi jika ditemukan kembali. Jika simpul yang dikunjungi
bukan state salah, dan bukan solusi, maka expand simpul tersebut dan masukkan anak-anak simpulter sebut dalam antrian. Lakukan kembali pengunjungan simpul dari antrian yang di-dequeue hingga ditemukan simpul solusi.Runtutan langkah-langkah dari state awal hingga solusi dapat diperolah dengan melakukan backtrack tiap parent dari simpul solusi ke simpul state awal. Berikut pohon state yang dibuat, dari simpul stateawal hingga simpul solusi:
Warna merah berarti state tersebut salah, merah + garis bawah berarti state tersebut telah dikunjungi.
ANALISIS
Penggunaan algoritma BFS pada pencarian solusi puzzle Missionaries and kannibals menghasilkan langkah-langkah menuju solusi yang optimal (terpendek), ini dikarenakan pencarian dilakukann secara melebar dari simpul akar hingga simpul akhir. Tidak seperti penggunaan algoritma DFS (Dept-First Search), yang lebih mengutamakan kedalaman untuk mencapai ke simpul solusi. 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.
KESIMPULAN
Algoritma Breadth-First Search (BFS) dapat diterapkan dalam berbagai macam masalah untuk melakukan pencarian solusi, salah satunya pada puzzle Missionaries and Cannibals. Algoritma BFS melakukan pencarian pada graf atau pohon dengan cara melebar, yang tentu memerlukan memori dan langkah pencarian yang lebih banyak dibandingkan dengan Depth-First Search.Keuntungan menggunakan BFS adalah langkah dari state awal ke state akhir optimal (terpendek).
REFERENSI
Knuth, Donald E. (1997), The Art Of Computer Programming Vol 1. 3rd ed.(http://www-cs-faculty.stanford.edu/~knuth/taocp.html)
http://games.tejasri.in/2010/08/missionaries-cannibals-problem.html
Munir, Rinaldi. 2009. Diktat Kuliah Strategi Algoritmik IF2251 Strategi Algoritmik. Departemen Teknik Informatika ITB
informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2007.../MakalahIF2251-2008-060.pdf
0 Komentar