-
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-