Missionaries and Cannibals Problem
Problem
adalah kata yang digunakan untuk menggambarkan suatu
keadaan yang bersumber dari hubungan antara dua faktor atau
lebih yang menghasilkan situasi yang membingungkan. (wikipedia)
Problem didefinisikan dalam 4 item:
1. Initial
State, yaitu memutuskan apa yang harus dilakukan dengan mencari urutan tindakan
yang mengarah pada keadaan (state) yang diinginkan
2.
Successor
function / Action, yaitu kombinasi dari berbagai "tindakan nyata"
3.
Goal
test, yaitu merumuskan tujuan yang ingin dicapai
4.
Path
cost, yaitu menetapkan besarnya biaya untuk setiap jalur yang ada.
Penjelasan Game
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 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.
Game ini terasa lebih
sulit dimainkan oleh pemain jika diberi aturan-aturan yang harus dipatuhi. ini
dia aturan-aturan tersebut:
- 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.
Salah satu metode yang
dipakai dalam pemecahan masalah pada game missionaries and cannibals ini adalah
dengan Breadth First Search (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 memberikan tanda pada simpul –
simpul tetangga yang nantinya akan dikunjungi berdasarkan urutan yang ada pada
antrian.
Penjabaran langkah-langkahnya
sebagai berikut:
1.
Akar
dimasukkan dalam antrian (Simpul paling awal yang akan dikunjungi).
2.
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.
3.
Jika
simpul yang sudah dicek tadi merupakan solusi permasalahan, pencarian selesai
dan hasil dikembalikan.
4.
Jika
simpul yang sudah dicek sebelumnya bukan merupakan solusi
permasalahan, semua simpul yang bertetanggan dengan simpul tadi (simpul
anak) dimasukkan kedalam antrian.
5.
Jika
antrian ternyata telah kosong dan semua simpul sudah dicek maka status
pencarian selesai dan berarti solusi tidak ditemukan.
6.
Hal
ini dilakukan secara berulang (simpul berisi solusi ditemukan/sampai antrian
kosong).
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 kana nada 3 Misionaris, 3 Kanibal dan perahu.
State akhir notasinya adalah `K(3,3)|(0,0)`.
Gambar Puzzle:
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 state awal hingga simpul solusi:
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 (DFS). Keuntungan menggunakan BFS adalah
langkah dari state awal ke state akhir optimal (terpendek).
Tulisan ini dibuat untuk memenuhi tugas mata kuliah
Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT . Prodi
Teknik Informatika Fakultas Teknik UHAMKA.
Referensi:
- https://id.wikipedia.org/wiki/Masalah
- http://slideplayer.info/slide/2379321/
- http://rizalcare.blogspot.co.id/2009/05/tree
- http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-007.pdf
Tidak ada komentar:
Posting Komentar