7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 1/11

Tugas

Sistem Cerdas

Nama : Rizky Nugraha Amaia

Stambuk : 1361031

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 2/11

1. State Space:

M = Misionaris r = a!a" Sisi iri

= aniba" n = a!a" Sisi anan

Sisi Kiri (Kr) Sisi Kanan (Kn)

eterangan:

# o"om yang ber$arna merah ada"ah ke%adian yang tidak bo"eh ter%adi

Solusi

M=0, K = 0 M=1, K = 0 M=2, K = 0 M=3, K = 0

M=0, K = 1 M=1, K = 1 M=2, K = 1 M=3, K = 1

M=0, K =2 M=1, K =2 M=2, K =2 M=3, K =2

M=0, K = 3 M=1, K = 3 M=2, K = 3 M=3, K = 3

M=0, K =

0

M=1, K =

0

M=2, K =

0

M=3, K =

0

M=0, K =

1

M=1, K =

1

M=2, K =

1

M=3, K =

1

M=0, K

=2

M=1, K

=2

M=2, K

=2

M=3, K

=2

M=0, K =

3

M=1, K =

3

M=2, K =

3

M=3, K =

3

Sisi Kiri Kapal Sisi Kanan

M=3, K =

3

r M=3, K = 3

M=3, K =

1

n M=3, K = 1

M=3, K

=2

r M=3, K =2

M=3, K =

0

n M=3, K = 0

M=3, K =

1

r M=3, K = 1

M=1, K =

1

n M=1, K = 1

M=2, K

=2

r M=2, K =2

M=0, K

=2

n M=0, K =2

M=0, K =

3

r M=0, K = 3

M=0, K =

1

n M=0, K = 1

M=0, K

=2

r M=0, K =2

M=0, K =

0

n M=0, K = 0

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 3/11

2. Production Rule

1 misionaris menyeberang

&ika ' ( 1 dan z = 1 maka )'#1* y* 0+,

- misionaris menyeberang

&ika ' ( - dan z = 1 maka )'#-* y* 0+,

1 kaniba" menyeberang

&ika y ( 1 dan z = 1 maka )'* y#1* 0+,

- kaniba" menyeberang

&ika y ( - dan z = 1 maka )'* y#-* 0+,

1 misionaris dan 1 kaniba"

&ika ' ( 1 dan y ( 1 dan z = 1 maka )'#1* y#1* 0+,

1 misionaris kemba"i

&ika ' . 3 dan z = 0 maka )'/1* y* 1+,

- misionaris kemba"i

&ika ' . - dan z = 0 maka )'/-* y* 1+,

1 kaniba" kemba"i

&ika y . 3 dan z = 0 maka )'* y/1* 1+,

- kaniba" kemba"

&ika y . - dan z = 0 maka )'* y/-* 1+,

1 misionaris dan 1 kaniba" kemba"i

&ika ' . 3 dan y . 3 dan z = 0 maka )'/1* y/1* 1+,

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 4/11

3. Algoritma Breadth First Search

nitia" State = )3*3*1+

oa" State = )0*0*0+,

1+ 2 = )3*3*1+4

5'!and )3*3*1+,

R1 )-*3*0+ Masuk ke 2,

R- )1*3*0+ Masuk ke 2,

R3 )3*-*0+ Masuk ke 2,

R7 )3*1*0+ Masuk ke 2,

R8 )-*-*0+ Masuk ke 2,

-+ 2 = )-*3*0+9 )1*3*0+9 )3*-*0+9 )3*1*0+9 )-*-*0+4

5'!and )-*3*0+,

3+ 2 = )1*3*0+9 )3*-*0+9 )3*1*0+9 )-*-*0+4

5'!and )1*3*0+,

7+ 2 = )3*-*0+9 )3*1*0+9 )-*-*0+4

5'!and )3*-*0+,

R )3*3*1+ ;, Sudah Masuk,

8+ 2 = )3*1*0+9 )-*-*0+4

5'!and )3*1*0+,

R )3*-*1+ Masuk ke 2,

R< )3*3*1+ ;, Sudah Masuk

6+ 2 = )-*-*0+9 )3*-*1+4

5'!and )-*-*0+,

R6 )3*-*1+ ;, Sudah Masuk

R )-*3*1+ Masuk ke 2,R10 )3*3*1+ ;, Sudah Masuk

+ 2 = )3*-*1+9 )-*3*1+4

5'!and )3*-*1+,

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 5/11

R1 )-*-*0+ ;,Sudah Masuk

R- )1*-*0+ Masuk ke 2,

R3 )3*1*0+ ;, Sudah Masuk

R7 )3*0*0+ Masuk ke 2,

R8 )-*1*0+ Masuk ke 2,

+ 2 = )-*3*1+9 )1*-*0+9 )3*0*0+9 )-*1*0+4

5'!and )-*3*1+,

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 6/11

5'!and )1*-*1+,

1+ 2 = )1*3*1+9 )-*-*1+4

5'!and )1*3*1+,

1+ 2 = )-*-*1+4

5'!and )-*-*1+,

R1 )1*-*0+ ;, Sudah Masuk

R- )0*-*0+ Masuk ke 2,

R3 )-*1*0+ ;, Sudah Masuk

R7 )-*0*0+ ;, Sudah Masuk

R8 )1*1*0+ ;, Sudah Masuk

1

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 7/11

-3+ 2 = )0*-*1+9 )1*0*0+9 )0*0*0+4

5'!and )0*-*1+,

R3 )0*1*0+ ;,

R7 )0*0*0+ ;,

-7+ 2 = )1*0*0+* )0*0*0+4

5'!and )1*0*0+,

-8+ 2 = )0*0*0+4

5'!and )0*0*0+, Goal State te"ah di>a!ai* sto!,

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 8/11

. Algoritma !epth First Search

nitia" State = )3*3*1+

oa" State = )0*0*0+,

1+ S = ?)3*3*1+? 4

5'!and )3*3*1+,

R1 )-*3*0+ Masuk ke S,

R- )1*3*0+ Masuk ke S,

R3 )3*-*0+ Masuk ke S,

R7 )3*1*0+ Masuk ke S,

R8 )-*-*0+ Masuk ke S,

-+ S = ?)-*3*0+9 )1*3*0+9 )3*-*0+9 )3*1*0+9 )-*-*0+? 4

5'!and )-*3*0+,

3+ S = ?)1*3*0+9 )3*-*0+9 )3*1*0+9 )-*-*0+? 4

5'!and )1*3*0+,

7+ S = ?)3*-*0+9 )3*1*0+9 )-*-*0+? 4

5'!and )3*-*0+,

R )3*3*1+ ;, Sudah Masuk

8+ S = ?)3*1*0+9 )-*-*0+? 4

5'!and )3*1*0+,

R )3*-*1+ Masuk ke S,

R< )3*3*1+ ;, Sudah Masuk

6+ S = ?)-*-*0+?9 ?)3*-*1+? 4

5'!and )3*-*1+,

R1 )-*-*0+ ;, Sudah Masuk

R- )1*-*0+ Masuk ke S,

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searchi 9/11

10

R3 )3*1*0+ ;, Sudah Masuk

R7 )3*0*0+ Masuk ke S,

R8 )-*1*0+ Masuk ke S,

+ S = ?)-*-*0+?9 ?)1*-*0+9 )3*0*0+9 )-*1*0+? 4

5'!and )1*-*0+,

+ S = ?)-*-*0+?9 ?)3*0*0+9 )-*1*0+? 4

5'!and )3*0*0+,

R )3*1*1+ Masuk ke S,

R )3*-*1+ ;, Sudah Masuk

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searc 10/11

11

R- )0*-*0+ Masuk ke S,

R3 )-*1*0+ ;, Sudah Masuk

R7 )-*0*0+ ;, Sudah Masuk

R8 )1*1*0+ ;, Sudah Masuk

18+ S = ?)-*-*0+?9 ?)-*1*0+?9 ?)-*0*0+?9 ?)0*-*0+? 4

5'!and )0*-*0+,

R6 )1*-*1+ ;, Sudah Masuk

R )-*-*1+ ;, Sudah Masuk

R )0*3*1+ Masuk ke S,

R10 )1*3*1+ ;, Sudah Masuk

16+ S = ?)-*-*0+?9 ?)-*1*0+?9 ?)-*0*0+?9 ?)0*3*1+? 4

5'!and )0*3*1+,R3 )0*-*0+ ;,

R7 )0*1*0+ Masuk ke S,

1+ S = ?)-*-*0+?9 ?)-*1*0+?9 ?)-*0*0+?9 ?)0*1*0+? 4

5'!and )0*1*0+,

R6 )1*1*1+ Masuk ke S,

R )-*1*1+ ;, Sudah Masuk

R )0*-*1+ Masuk ke S,

R< )0*3*1+ ;, Sudah Masuk

R10 )1*-*1+ ;, Sudah Masuk

1+ S = ?)-*-*0+?9 ?)-*1*0+?9 ?)-*0*0+?9 ?)1*1*1+9 )0*-*1+? 4

5'!and )1*1*1+,

R1 )0*1*0+ ;, Sudah Masuk

R3 )1*0*0+ Masuk ke

S, R8 )0*0*0+ Masuk ke

S,1

7/24/2019 Penyelesaian-Masalah-The-Missionaries-and-Cannibals-Problem-menggunakan-Algoritma-Searching-BFS-dan-DFS (

http:///reader/full/penyelesaian-masalah-the-missionaries-and-cannibals-problem-menggunakan-algoritma-searc 11/11

1-