PENERAPAN METODE DEPTH FIRST SEARCH PADA PERMAINAN
MISSIONARIES DAN CANNIBALS
DISUSUN OLEH:
KELOMPOK 3
KETUA : TANWIR (1310520024)
MODERATOR : CANDRA HALIM (1310520067)
SEKRETARIS : LOLIN
INDRISWARI (1410510039)
ANGGOTA :
·
SAHRUN (1310520068)
·
FENI ALFAONITA (1310520066)
·
RISKA SEPTI ADELSA (1310520027)
·
ALDI ARZAKI (1310520028)
·
DIVA YUDA GEOVANI
·
ARDI RAHMAWAN
·
JUJUD HAIRIL ANAM
·
SATRIAWAN (1310520070)
SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER (STMIK)
BUMIGORA MATARAM
PENERAPAN
METODE DEPTH FIRST SEARCH PADA PERMAINAN MISSIONARIES DAN CANNIBALS
I.
PENDAHULUAN
Permainan
ini tidak begitu populer diantara permainan-permainan lainnya disebabkan karena
permainannya sederhana dan interface yang kurang menarik sehingga tidak menarik
orang untuk memainkannya. Namun permainan ini sangatlah bagus untuk mengasah
logika. Karena untuk menyelesaikan permainan ini, dibutuhkan sedikit logika.
Adapun
permainan ini memiliki aturan sebagai berikut.
Pada
saat awal permainan, terdapat dua buah daratan disebelah kanan dan kiri yang
dipisahkan oleh sebuah sungai. Terdapat tiga manusia dan tiga kanibal di sisi
kanan sungai dan sebuah perahu atau boat di sisi kanan sungai. Perahu tersebut
hanya dapat mengangkut paling banyak dua penumpang dan dikendalikan oleh salah
satu penumpang di dalam perahu. Dan perahu hanya dapat bergerak ke kanan atau
kiri.Selain itu juga terdapat aturan bahwa jumlah manusia tidak boleh lebih
sedikit dari jumlah kanibal pada kedua sisinya. Jika jumlah manusia lebih
sedikit dari jumlah kanibal, maka kanibal akan memakan manusia dan game pun
akan berakhir.
Gambar 1. Tampilan awal permainan
Tujuan
akhir dari permainan ini adalah memindahkan ketiga manusia dan ketiga kanibal
dari daratan sebelah kanan ke daratan sebelah kiri dengan selamat. Jadi
dibutuhkan perhitungan yang tepat agar jumlah manusia lebih banyak daripada
jumlah kanibal di setiap sisi atau jumlah manusia sama dengan jumlah kanibal di
setiap sisi.
Berikut penjelasan singkat mengenai teknis permainan. Untuk
menaikkanmissionary atau cannibal, cukup mengkliknya maka missionary atau
cannibal akan otomatis masuk ke perahu. Begitu pula untuk mengeluarkannya dari
perahu tinggal mengklik missionary atau cannibal yang ada di dalam perahu.
Untuk menjalankan perahu, cukup mengklik tombol GO! Yang terletak kanan atas.
II.
ATURAN PERMAINAN
· Ada
tiga misionaris dan tiga kanibal yangharus menyebrang sungai.
· Hanya
disediakan satu perahu.
· Perahu
bisa berjalan jika ada minimalsatu orang atau satu kanibal (satupenumpang).
· Perahu
maksimum berisi dua (1kanibal/1 misionaris /2 kanibal /2misionaris)
· Jumlah
kanibal tidak boleh lebih banyakdari jumlah misionaris di salah satu
sisidaratan.
· Jika
jumlah kanibal lebih banyak darijumlah misionaris pada suatu sisi daratanmaka
kanibal akan memakan misionaris.
· Pemain
berhasil menyelesaikanpermainan jika semua misionaris dansemua kanibal ada di
sisi seberang yangmenjadi tujuan.
III. IDENTIFIKASI
RUANG KEADAAN
Gambar 2. Identifikasi
Ruang Keadaan
IV. KEADAAN AWAL DAN KEADAAN TUJUAN
Dalam proses pemecahan
masalah permainan Missionaries
dan Cannibalsperlu
ditetapkan suatu keadaan awal dan
keadaan tujuan untuk mempermudah penyelesaiannya.
IV.I. KEADAAN AWAL
Gambar 3. State Awal
dari Missionaries and Cannibals
IV.2. KEADAAN TUJUAN
Gambar
4. State Akhir/Tujuan dari Missionaries and Cannibals
V.
DASAR ATURAN (RULE BASE)
Untuk mencapai
keadaan tujuan maka dibuatlah aturan-aturan yang dapat memenuhi semua keadaan yang mungkin terjadi. Adapun aturan-aturan
tersebut adalah sebagai berikut :
|
ATURAN KE
|
ATURAN
|
|
1
|
1M
(Menyebrang)
|
|
2
|
1K
(Menyebrang)
|
|
3
|
1M
(Kembali)
|
|
4
|
1K
(Kembali)
|
|
5
|
2M
(Menyebrang)
|
|
6
|
2K
(Menyebrang)
|
|
7
|
2M
(Kembali)
|
|
8
|
2K
(kembali)
|
|
9
|
1M1K
(Menyebrang)
|
|
10
|
1M1K (Kembali)
|
|
Ket :
M : Missionaris
K : Kanibal
|
|
Tabel1. Aturan Permainan Missionaries dan Canibal
VI.
SOLUSI
Salah satu metode yang dapat dipakai dalam proses pemecahan
permasalahan pada permainan Missionaries dan Cannibalsyaitudengan menggunakan metode DFS(Depth First Search) atau pencarian mendalam.
Depth
First Search adalah algoritma pencariansolusi yang melakukan pencarian pada
graf ataupohon berakar secara mendalam
dengan caramelakukan proses
pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node
yang selevel.
Kelebihan dari metode Depth
First Search yaitu:
·
Membutuhkan memori relatif kecil, karena hanya node-node pada
lintasan yang aktif saja yang disimpan.
·
Secara kebetulan, akanmenemukan solusi
tanpa harus menguji lebih banyak lagi dalam ruang keadaan.
Kelemahan dari metode Depth
First Search yaitu:
·
Memungkinkan tidak ditemukannya tujuan yang
diharapkan
·
Hanya mendapat 1 solusi pada setiap pencarian
Langkah-langkah pencarian
solusimenggunakan metode DFS adalah
sebagai berikut:
·
Solusi dicari dengan membentuk lintasan dari akar sampai daun.
Simpul-simpul yang sudah dilahirkan dinamakan simpul anak kiri dan simpul anak
kanan.
·
Simpul yang dibentuk, terlebih dahulu simpul sebelah kiri dan mendalam
sampai ditemukan solusi.
·
Jika lintasan yang sedang dibentuk tidak mengarah ke solusi, maka lintasan
yang sebelah kiri dihentikan disebut simpul mati dan dilanjutkan ke simpul anak
kanan terdekat. Simpul yang sudah dihentikan (simpul mati) tidak akan pernah
diperluas lagi.
·
Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian
solusi dilanjutkan dengan melakukan pembentukan ke simpul hidup terdekat.
Selanjutnya simpul ini menjadi simpul hidup yang baru.
·
Lintasan baru dibangun kembali sampai lintasan tersebut membentuk solusi.
Solusi permasalahan
untuk pemindahan seluruh Missionaries dan Cannibals dari seberang kanan(asal)
ke seberang kiri(tujuan) pada permainan Missionaries dan Cannibals dengan
metode DFS dapat dilihat pada tabel 1 dan gambar 5 berikut ini.
|
NO
|
KEADAAN
|
ATURAN
|
AKSI
|
HASIL
|
|
1
|
(0,0)
| (3,3) K
AWAL
|
6
|
2 Kanibal
Menyebrang
|
K
(0,2) | (3,1)
|
|
2
|
K
(0,2) | (3,1)
|
4
|
1 Kanibal
Kembali
|
(0,1)
| (3,1) K
|
|
3
|
(0,1)
| (3,1) K
|
6
|
2 Kanibal Menyebrang
|
K
(0,3) | (3,0)
|
|
4
|
K
(0,3) | (3,0)
|
4
|
1 Kanibal
Menyebrang
|
(0,2)
| (3,1) K
|
|
5
|
(0,2)
| (3,1) K
|
6
|
2 Kanibal
Menyebrang
|
K
(2,2) | (1,1)
|
|
6
|
K
(2,2) | (1,1)
|
10
|
1 Missonaris dan
1 kanibal Kembali
|
(1,1)
| (2,2) K
|
|
7
|
(1,1)
| (2,2) K
|
5
|
2 Missionaris
Menyebrang
|
K
(3,1) | (0,2)
|
|
8
|
K
(3,1) | (0,2)
|
4
|
1 Kanibal
Kembali
|
(3,0)
| (0,3) K
|
|
9
|
(3,0)
| (0,3) K
|
6
|
2 Kanibal Menyebrang
|
K
(3,2) | (0,1)
|
|
10
|
K
(3,2) | (0,1)
|
3
|
1 Missionaris
Kembali
|
(2,2)
| (1,1) K
|
|
11
|
(2,2)
| (1,1) K
|
9
|
1 Missionaris
dan 1 Kanibal Menyebrang
|
K
(3,3) | (0,0)TUJUAN
|
Tabel2. Solusi
Permainan Missionaries dan Canibals
Gambar
5. Pohon Pelacakan
Gambar 6 . Pohon Pelacakan BFS
VII.
KESIMPULAN
Algoritma Depth-First Search (DFS) dapat diterapkan
dalam berbagai macam masalah untu kmelakukan pencarian solusi, salah satunya
pada permainan Missionaries and Cannibals. Algoritma DFS melakukan pencarian
pada graf atau pohon dengan cara mendalam, Jadi Jika Nol di Tujuan pada posisi Dalam dan berada dianak kiri akan lebih
Efisien dibandingkan dengan BFS Jika Nol di tujuan pada posisi berbeda diatas
maka BFS lebih Efisien.
PERTANYAAN DAN JAWABAN
Penanya : KHAIRUL IMAM (1310520075)
Kelompok : 4
Pertanyaan : apa alasan anda menggunakan DFS?
Jawaban
: Karena dengan menggunakan
metode DFS, jalur untuk sampai ke goal
state-nya lebih singkat di
dalam permainan missionaries
dan cannibals. Proses pencarian dilakukan pada semua anaknya sebelum dilakukan
pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level
yang lebih tinggi. Proses diulangi terus hingga ditemukan solusi. Lagipula
solusi terdapat di level paling dalam dan berada di anak kiri. Jadi, akan lebih
singkat jika menggunakan metode DFS.
Penanya :
LALU MUH. KUMBAYONI (1310520045)
Kelompok : 2
Pertanyaan : di dalam permainan tersebut terdapat missionaries dan
cannibals. Apa yang dimaksud dengan missionaries?
Jawaban : Missionaries terdiri dari kata ‘misi’ atau dengan kata
lain adalah orang yang membawa misi. Bisa juga dikatakan sebagai orang suci
yang membawa misi untuk mengajak ke ajaran Tuhan. Maka dari itu, di dalam
permainan missionaries dan cannibals, missionaries digambarkan seperti seorang
biksu.
Masukan dan saran dari Ibu Khasnur
Hidjah, S.Kom., M.Cs.
a.
Kurang tepatnya
metode pencarian yang dipakai dalam penyelesaian masalah,
Saran : dalam permainan
kanibal dan misionaris ini tidak hanya DFS yang yang menjadi alternative
penyelesain masalah yaitu bisa juga menggunakn metode pencarian yang lain
seperti metode pencarian heuristik
b.
Pengambilan
kesimpulan yang kurang tepat
Saran : lebih bagusnya
kesimpulan itu disesuaikan dengan judul yang diangkat. Dan kesimpulan yang
disarankan adalah dalam permainan kanibal dan misionaris ini yang menggunakan
metode DFS dan lebih baiknya tidak dandingkan dengan metode BFS karena dalam
judulnya tidak membandingkan antara metode DFS dengan BFS.
VIII. DAFTAR REFERENSI
Kusumadewi,
Sri. 2003. Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha
Ilmu.
Anonymous, http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-007.pdfdiakses
pada tanggal 30 Maret 2015
