Penyelesaian The Missionaries and The Canibal Problem

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 :

https://id.scribd.com/doc/288475990/Penyelesaian-Masalah-the-Missionaries-and-Cannibals-Problem-Menggunakan-Algoritma-Searching-BFS-Dan-DFS