Banyak persoalan yang dapat diselesaikan dengan metode search. Salah satunya adalah persoalan missionaries dan cannibal yang sering dikaitkan dengan topik intelijensia buatan. Banyak pendekatan yang dapat dilakukan untuk persoalan tersebut, namun permasalahannya adalah tidak setiap pendekatan akan memberikan solusi terbaik yang memiliki cost, waktu dan ruang yang efisien. Postingan ini akan mengeksplor kasus missionaries dan cannibal tersebut dengan menggunakan algoritma Depth First Search (DFS) yang akan melakukan penelusuran terhadap pohon ruang status secara mendalam dengan variasi penghindaran looping dengan tujuan untuk mengurangi cost, waktu komputasi dan ruang pencarian solusi.
- Konsep Depth First Search (DFS)
Depth First Search selalu mengembangkan salah satu node pada level terdalam dari pohon. Hanya ketika mencapai titik mati (non-goal node yang tidak mungkin diekspansi) akan dilakukan backtrack ke node induk dan mengembangkan node pada level berikutnya.
- Penyelesaian Masalah dengan Deppth First Search (DFS)
Pada kasus berikut algoritma DFS diatas mengalami beberapa penambahan karena simpul akan dibunuh tidak hanya karena Q kosong tapi juga karena jumlah kanibal lebih banyak dari jumlah missionaries pada salah satu atau kedua sisi sungai atau karena simpul tersebut pernah dibangkitkan sebelumnya. Jika ditulis secara prosedural maka akan tampak sebagai
berikut :
1. Masukkan simpul akar ke dalam antrian Q. Masukkan kedalam closed list Jika simpul akar adalah simpul tujuan maka solusi telah ditemukan.Stop
2. Jika Q kosong, tidak ada solusi. Stop
3. Ambil simpul v dari kepala antrian Jika jumlah kanibal lebih banyak dari jumlah missionaris pada salah satu atau kedua sisi atau simpul pernah dibangkitkan sebelumnya, kembali ke langkah 2
4. Bangkitkan semua anak dari simpul v, masukkan v kedalam closed list. jika tidak memiliki anak lagi, kembali ke langkah 2. tempatkan semua anak dari v di awal antrian Q
5. Jika anak dari simpul v adalah simput tujuan, solusi telah ditemukan, kalau tidak kembali ke langkah 2 Pada permasalahan ini state dinotasikan dengan sebuah tuple
<Xm,Xc, status posisi perahu>
Xm = Jumlah missionaries tersisa
Xc = Jumlah kanibal tersisa
Posisi perahu dapat berupa huruf B yang berarti perahu berada di sebelah barat dan T yang berarti perahu berada di sebelah timur. Jika digambarkan dengan pohon maka kondisi awal adalah sebagai berikut :
<0m,0c><3m,3c,B>
Kondisi tersebut berarti bahwa perahu ada disebelah Barat dengan jumlah missionaries dan kanibal pada sisi tersebut masing-masing tiga, sedangkan pada sisi Timur sungai masih kosong. Untuk mempermudah dan menjaga konsistensi dalam kasus ini ditentukan urutan perpindahan missionaries dan kanibal adalah sebagai berikut :
<1m,0c><1m,1c><2m,0c><1c,0m><2c>
pengembangan node selalu dimulai dari sisi kiri.Dari kondisi awal tersebut maka node yang akan dikembangkan adalah <1m,0c> . jika digambarkan adalah sebagai berikut :
karena pada simpul dua di sebelah barat jumlah kanibal lebih banyak dari jumlah missionaries maka simpul tersebut mati. Pencarian kemudian berbalik ke simpul satu dan membangkitkan simpul anak lain yang masih mungkin untuk dibangkitkan.
Pencarian terus dilakukan seperti pada gambar diatas, ketika simpul nomor lima dibangkitkan diketahui bahwa simpul tersebut sama dengan simpul yang pernah dibangkitkan sebelumnya yaitu simpul 3, simpul lima kemudian dibunuh ditandai dengan L3 yang berarti looping terhadap simpul 3, maka simpul tersebut dibunuh lalu backtrack ke pohon induk kemudian mengembangkan simpul-simpul anak lainnnya
Seperti yang dapat dilihat dari gambar 4 . simpul 6 dan 7 ikut dibunuh karena pada salah satu sisi, jumlah kanibal lebih banyak dari missionaries dan akhirnya dikembangkan simpul 8. karena simpul 9 dan 10 terjadi looping dan simpul 8 tidak mungkin membangkitkan simpul anak lagi maka, simpul 4 lah yang akan membangkitkan anak, begitu seterusnya hingga tercapai solusi atau tidak terdapat solusi sama sekali ( pohon ruang status akhir ruang status keseluruhan disertakan dalam lampiran).
