Disini saya akan menjelaskan cara penyelesaian The
Missionaries dan The Canibal Problem dengan meggunakan teknik DFS atau Depth First Search.
Penyelesaian ini saya dapatkan dari sebuah makalah
yang telah di upload ke sebuah website. Berikut link website tersebut https://id.scribd.com/doc/288475990/Penyelesaian-Masalah-the-Missionaries-and-Cannibals-Problem-Menggunakan-Algoritma-Searching-BFS-Dan-DFS
.
Pertama saya akan menjelaskan apa itu The
Missionaries and The Canibal Problem dan rules awal dari problem tersebut :
1) Terdapat 3 orang misionaris dan 3 kanibal di salah satu sisi sungai.
2) Mereka semua harus menyeberangi sungai menggunakan 1 kapal yang bermuatan maksimal 2 orang.
3) Jika pada salah satu sisi sungai terdapat misionaris dan jumlah misionaris pada sisi tersebut lebih sedikit dari jumlah kanibal pada sisi sungai yang sama maka misionaris akan dimakan oleh kanibal.
Diasumsikan bahwa :
x = jumlah misionaris di sisi kiri sungai,
y = jumlah kanibal di sisi kiri sungai,
z = jumlah kapal di sisi kiri sungai. Jika 0,
berarti kapal berada di sisi kanan sungai.
a = jumlah misionaris di sisi kanan sungai.
b = jumlah kanibal di sisi kanan sungai.
Dibuatkan State Space Sebagai berikut
State berlatar kuning merupakan state yang tidak diperbolehkan, sebab jumlah misionaris pada salah salah satu sisi lebih sedikit dari jumah kanibalnya, sehingga misionaris akan dimakan kanibal.
Setelah itu kita mendefinisikan problem dari
pembahasan ini yaitu :
-Initial State
atau State awal State awal daari problem ini yaitu berada pada (3,3,1)
-Succesor Function disini merupakan Production Rule dari permasalahan yang akan dibahas disini
- Goal Test atau tujuan yang ingin dicapai yaitu berada pada (0,0,0)
- Path Cost atau jumlah aksi yang diperlukan untuk menyelesaikan
permasalahan
Dalam penyelesaian
menggunakan DFS terdapat beberapa Production
Rule atau syarat pemecahan, berikut Production
Rulenya
1) 1 misionaris menyeberang ke sisi kanan sungai.
Jika x≥1 dan z=1 maka (x-1, y, 0).
2) 2 misionaris menyeberang ke sisi kanan sungai.
Jika x≥2 dan z=1 maka (x-2, y, 0).
3) 1 kanibal menyeberang ke sisi kanan sungai.
Jika y≥1 dan z=1 maka (x, y-1, 0).
4) 2 kanibal menyeberang ke sisi kanan sungai.
Jika y≥2 dan z=1 maka (x, y-2, 0).
5) 1 misionaris dan 1 kanibal menyeberang ke sisi kanan sungai.
Jika x≥1 dan y≥1 dan z=1 maka (x-1, y-1, 0).
6) 1 misionaris kembali ke sisi kiri sungai.
Jika x<3 dan z=0 maka (x+1, y, 1).
7) 2 misionaris kembali ke sisi kiri sungai.
Jika x<2 dan z=0 maka (x+2, y, 1).
8) 1 kanibal kembali ke sisi kiri sungai.
Jika y<3 dan z=0 maka (x, y+1, 1).
9) 2 kanibal kembali ke sisi kiri sungai.
Jika y<2 dan z=0 maka (x, y+2, 1).
10) 1 misionaris dan 1 kanibal kembali ke sisi kiri sungai.
Jika x<3 dan y<3 dan z=0 maka (x+1, y+1, 1).
Selain Production Rule di atas, terdapat aturan lain yaitu jika pada salah
satu sisi sungai terdapat misionaris dan jumlah misionaris pada sisi tersebut lebih sedikit dari jumlah kanibal pada sisi sungai yang sama maka misionaris akan dimakan oleh kanibal. Hal ini tidak boleh terjadi.
Aturan tersebut dituliskan :
Untuk sisi kiri sungai: Jika x > 0 dan x < y maka state tidak diperbolehkan.
Untuk sisi kanan sungai: Jika a > 0 dan a < b maka state tidak diperbolehkan.
Diketahui
bahwa a = 3-x dan b= 3-y;
a > 0;
3-x > 0;
3 > x;
x
< 3;
a < b;
3-x < 3-y;
-x < -y;
x > y;
Sehingga
aturan untuk sisi kanan sungai dapat ditulis menjadi:
Jika
x < 3 dan x > y maka state tidak diperbolehkan.
Penyelesaian
dengan Algoritma Depth First Search
Initial State
= (3,3,1) dan Goal State = (0,0,0).
Algoritma DFS menggunakan stack yang bersifat
LIFO (Last In First Out). State akan dimasukkan ke dalam stack
dan di-expand dari data terakhir. Jika state sudah pernah masuk ke dalam
stack S, akan diberi tanda X. Jika terdapat beberapa state dengan
kedalaman yang sama, akan dimasukkan sekaligus ke dalam stack. State
yang memiliki kedalaman yang sama tersebut akan di-expand sesuai urutan
(dari yang paling kiri). Untuk menunjukkan perbedaan kedalaman, akan digunakan
tanda pembatas ||.
1) S = [ |(3,3,1)| ]
Expand (3,3,1).
R1 → (2,3,0) Masuk ke
S.
R2 → (1,3,0) Masuk ke
S.
R3 → (3,2,0) Masuk ke
S.
R4 → (3,1,0) Masuk ke
S.
R5 → (2,2,0) Masuk ke
S.
2) S = [ |(2,3,0); (1,3,0); (3,2,0); (3,1,0);
(2,2,0)| ]
Expand (2,3,0).
Merupakan state yang tidak diperbolehkan, pada sisi kiri sungai terdapat
misionaris tetapi lebih sedikit dari jumlah kanibal di sisi sungai yang sama
(x>0 dan x<y).
3) S = [ |(1,3,0); (3,2,0); (3,1,0); (2,2,0)| ]
Expand (1,3,0).
Merupakan state yang tidak diperbolehkan, pada sisi kiri sungai terdapat
misionaris tetapi lebih sedikit dari jumlah kanibal di sisi sungai yang sama
(x>0 dan x<y).
4) S = [ |(3,2,0); (3,1,0); (2,2,0)| ]
Expand (3,2,0).
R8 → (3,3,1) X. Sudah pernah dimasukkan ke
dalam S.
5) S = [ |(3,1,0); (2,2,0)| ]
Expand (3,1,0).
R8 → (3,2,1) Masuk ke
S.
R9 → (3,3,1) X. Sudah
pernah dimasukkan ke dalam S.
6) S = [ |(2,2,0)|; |(3,2,1)| ]
Expand (3,2,1).
R1 → (2,2,0) X.
R2 → (1,2,0) Masuk ke
S.
R3 → (3,1,0) X.
R4 → (3,0,0) Masuk ke
S.
R5 → (2,1,0) Masuk ke
S.
7) S = [ |(2,2,0)|; |(1,2,0); (3,0,0); (2,1,0)| ]
Expand (1,2,0). State
yang tidak diperbolehkan.
8) S = [ |(2,2,0)|; |(3,0,0); (2,1,0)| ]
Expand (3,0,0).
R7 → (3,1,1) Masuk ke
S.
R8 → (3,2,1) X.
9) S = [ |(2,2,0)|; |(2,1,0)|; |(3,1,1)| ]
Expand (3,1,1).
R1 → (2,1,0) X.
R2 → (1,1,0) Masuk ke
S.
R3 → (3,0,0) X.
R5 → (2,0,0) Masuk ke
S.
10) S = [ |(2,2,0)|; |(2,1,0)|; |(1,1,0); (2,0,0)| ]
Expand (1,1,0).
R6 → (2,1,1) Masuk ke
S.
R7 → (3,1,1) X.
R8 → (1,2,1) Masuk ke
S.
R9 → (1,3,1) Masuk ke
S.
R10 → (2,2,1) Masuk ke
S.
11) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(2,1,1);
(1,2,1); (1,3,1); (2,2,1)| ]
Expand (2,1,1).
Merupakan state yang tidak diperbolehkan, pada sisi kanan sungai terdapat
misionaris tetapi lebih sedikit dari jumlah kanibal di sisi sungai yang sama
(x<3 dan x>y).
12) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(1,2,1);
(1,3,1); (2,2,1)| ]
Expand (1,2,1). State
yang tidak diperbolehkan.
13) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(1,3,1);
(2,2,1)| ]
Expand (1,3,1). State
yang tidak diperbolehkan.
14) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(2,2,1)|
]
Expand (2,2,1).
R1 → (1,2,0) X.
R2 → (0,2,0) Masuk ke
S.
R3 → (2,1,0) X.
R4 → (2,0,0) X.
R5 → (1,1,0) X.
15) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(0,2,0)|
]
Expand (0,2,0).
R6 → (1,2,1) X.
R7 → (2,2,1) X.
R8 → (0,3,1) Masuk ke
S.
R10 → (1,3,1) X.
16) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(0,3,1)|
]
Expand (0,3,1).
R3 → (0,2,0) X.
R4 → (0,1,0) Masuk ke
S.
17) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(0,1,0)|
]
Expand (0,1,0).
R6 → (1,1,1) Masuk ke
S.
R7 → (2,1,1) X.
R8 → (0,2,1) Masuk ke
S.
R9 → (0,3,1) X.
R10 → (1,2,1) X.
18) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(1,1,1);
(0,2,1)| ]
Expand (1,1,1).
R1 → (0,1,0) X.
R3 → (1,0,0) Masuk ke
S.
R5 → (0,0,0) Masuk ke
S.
19) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|;
|(0,2,1)|; |(1,0,0); (0,0,0)| ]
Expand (1,0,0). State
yang tidak diperbolehkan.
20) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|;
|(0,2,1)|; |(0,0,0)| ]
Expand (0,0,0). Goal
State telah dicapai, stop.
Jadi, Algoritma DFS berhasil menemukan solusi untuk the
missionaries and cannibals problem setelah melakukan 20 kali perulangan.
Dengan melacak jalur yang dilalui, diperoleh solusi:
Ilustrasi penyelesaian dengan Algoritma Depth First Search
Source :
