SEARCHING Russel and Norvig. 2003. Artificial Intelligence: a Modern Approach. Prentice Hall. Suyanto, Artificial Intelligence. 2005. Bandung:Informatika
Program Studi Ilmu Komputer FPMIPA UPI
RNI – IK460(Kecerdasan Buatan), 15 September 2014
Metode Searching • Blind/Un-informed Search – Breadth-First Search (BFS) – Depth-First Search (DFS)
• Heuristic/Informed Search – Hill Climbing – A*
2
Ukuran Performansi • • • •
Completeness Time Complexity Space Complexity Optimality
3
Studi Kasus: Pencarian Jalur Terpendek Arad-Bucharest
http://homepages.ius.edu/RWISMAN/C463/html/chapter3-4.gif 4
Studi Kasus: Water-Jug Problem • Bagaimana cara mengisi Tabung X dengan tepat 2 liter air? • Masing-masing galon tidak memiliki skala ukuran.
Tabung X (4 liter)
Tabung Y (3 liter)
Himpunan keadaan (state), dengan S = {X,Y} X = jumlah air pada tabung berkapasitas 4 liter, X N. Y = jumlah air pada tabung berkapasitas 3 liter, Y N Initial state = (0,0) Goal state = (2,0)
5
Aturan Produksi X
Y
Aturan Produksi
X’
Y’
X<4
Y
1
4
Y
X
Y<3
2
X
3
X>0
Y
3
0
Y
X
Y>0
4
X
0
X + Y> = 4
Y>0
5
4
Y – (4 – X)
X>0
X + Y>=3
6
X-(3-Y)
3
X + Y< = 4
Y>0
7
X+Y
0
X>0
X + Y< = 3
8
0
X+Y
1. Isi penuh tabung X 2. Isi penuh tabung Y 3. Kosongkan tabung X 4. Kosongkan tabung Y
5. Tuangkan air dari tabung Y ke tabung X sampai tabung X penuh 6. Tuangkan air dari tabung X ke tabung Y sampai tabung Y penuh 7. Tuangkan seluruh air dari tabung Y ke tabung X 8. Tuangkan seluruh air dari tabung X ke tabung Y
6
Search Space 0,0
Aturan no.2
INITIAL STATE 0,3
4,0
Aturan no.7 4,3
0,0
3,0
4,3
0,0
Aturan no.2 0,0
3,3
Aturan no.5 4,3
4,2
0,3
Aturan no.3 0,2
Aturan no.7
GOAL STATE
2,0
7
Solusi 0
0
0
3
3
0
3
3
4
2
4
3
4
3
4
3
4
3
4
3
http://lazytoad.com/lti/ai/hw1-1.html 8
Blind/Un-informed Search
Breadth-First Search (BFS) • Pencarian tanpa informasi awal (blind). • Pencarian pada semua simpul dalam setiap level secara berurutan dari kiri ke kanan. • Complete dan optimal. • Jika percabangan(b) dan kedalaman solusi (d), maka jumlah state yang harus disimpan adalah O(bd). Misal: b=10, d=8, 106 simpul=1 detik, 1 simpul=100 bytes Jumlah state: 100 + 101 + 102 + 103 + 104 + 105 + 106 + 107 + 108 = 111.111.111 108 simpul
Waktu proses: 108 / 106 = 100 detik (1,67 menit)
Memory yang dibutuhkan:
Pencarian di kedalaman atau level 14??
(108)(102)=1010 bytes (10 gigabytes) 10
Searching using BFS A
1
B
2
4
8
H
C
D
E
I
J
F
K
L
G
M
N
O
11
Depth-First Search (DFS) •
• •
• •
Pencarian solusi dengan penulusuran simpul (dimulai dari yang paling kiri) sampai kedalaman tertentu. Jika solusi tidak ditemukan, pencarian solusi berpindah ke simpul berikutnya (sebelah kanan) juga sampai kedalaman tertentu. State yang sudah ditelusuri dan bukan percabangan ke state yang belum ditelusuri akan dihapus dari memory. Memory yang dibutuhkan O(bd), dengan b=faktor percabangan dan m=kedalaman maksimum pohon pencarian. Misal: b=10, d=3 Jumlah state DFS: 1 + 10 + 10 + 10 =31 simpul -- > space bm; time bm Jumlah state BFS: 100 + 101 + 102 + 103 = 1.111 103 simpul -- > space bd; time bd Keuntungannya jika solusi ada pada kedalaman di ranting kiri, pencarian menjadi lebih cepat. Kelemahannya, dengan kedalaman tak hingga pencarian DFS menjadi tidak complete dan tidak optimal.
12
Searching using DFS A
1
2
3
4
B
C
D
H
E
I
J
F
K
L
G
M
N
O
13
Quiz : Crossing the River (with a Wolf, a Goat, and a Cabbage) • http://www.mathcats.com/explore/river/crossing.htmll
14
Heuristik/Informed Search
Fungsi Heuristik • Fungsi heuristik adalah fungsi perkiraan dari initial state menuju goal state. Contoh, (p1,p2), (q1,q2) : Euclidean distance
Manhattan distance (city block distance)
16
Fungsi Heuristik (lanj.) • Fungsi heuristik yang terbaik adalah yang mendekati namun tidak lebih besar dari nilai sebenarnya. A -> B
B -> C
C -> D
Koordinat
A(20,10)-B(35,10)
B(35,10)-(55,10)
C(55,10)-D(65,10)
h(n)
15
20
10
g(n)
16
100
10
A
B
C
D 17
Hill Climbing • Metode Hill Climbing sering digunakan jika terdapat fungsi heuristic yang baik untuk mengevaluasi state (Rich, 1991). • Menuju pusat kota gedung tertinggi Fungsi heuristik jarak dari tempat berada ke gedung tertinggi State yang diinginkan jarak terpendek • Terdapat dua jenis Hill Climbing (HC): 1. Simple HC (HC Sederhana) 2. Steepest-Ascent HC (HC dengan memilih kemiringan yang paling tajam/ curam) 18
Simple HC 1. Evaluasi state awal, jika state awal sama dengan tujuan, maka proses berhenti. Jika tidak sama dengan tujuan maka lanjutkan proses dengan membuat state awal sebagai state sekarang. 2. Kerjakan langkah berikut sampai solusi ditemukan atau sampai tidak ada lagi operator baru yang dapat digunakan dalam state sekarang: a. Cari sebuah operator yang belum pernah digunakan dalam state sekarang dan gunakan operator tersebut untuk membentuk state baru. b. Evaluasi state baru. i. Jika state baru adalah tujuan, maka proses berhenti ii. Jika state baru tersebut bukan tujuan tetapi state baru lebih baik daripada state sekarang, maka buat state baru menjadi state sekarang. iii. Jika state baru tidak lebih baik daripada state sekarang, maka kembali ke langkah 2 a. 19
Simple HC
A
f = 23
G
f=0
Solusi optimum di level 2
S
f = 20
B
f = 17
≈ G
Solusi tidak optimal!
C
f=7
G
f=0
≈ f=0
Solusi di level 6
Solusi di level 4 20 20
Steepest-Ascent HC 1. Evaluasi initial state. Jika state ini adalah goal state, maka kembalikan state ini sebagai solusi dan keluar dari fungsi. Jika state ini bukan goal state, lanjutkan proses dengan initial state sebagai current state (keadaan sekarang). 2. Ulangi sampai solusi ditemukan atau sampai tidak ada perubahan terhadap current state: a. Misalkan SUK adalah suatu state yang menjadi suksesor dari current state. b. Untuk setiap operator yang bisa dilakukan terhadap current state, kerjakan: i. Aplikasikan Operator tersebut dan bangkitkan new state. ii. Evaluasi new state. Jika merupakan goal state, bandingkaan new state dengan SUK. Jika new state lebih baik dari SUK, maka ganti SUK dengan new state. Jika tidak lebih baik, SUK tidak perlu diganti. c. Jika SUK lebih baik dari current state, maka ganti current state dengan SUK.
21
Steepest-Ascent HC
A
f = 23
G
f=0
Solusi optimum di level 2
S
f = 20
B
f = 17
≈ G
Solusi tidak optimal!
C
f=7
G
f=0
≈ f=0
Solusi di level 6
Solusi di level 4 22 22
A* • Pencarian jalur terpendek dari S menuju G
80
23
Penyelesaian • Fungsi heuristik: n
S
A
B
C
D
E
F
G
H
J
K
L
M
h(n)
80
80
60
70
85
74
70
0
40
100
30
20
70
• Penyelesaian : f(n)=h(n) + g(n) Open
Closed
None
Open
S (80) S A (90)
A,B,C,D,E
None
E (S)
D, J
Open
D (110)
B (80)
J (130)
G (100) B (A)(S)
B (85) C (100)
A (115)
D (120)
F (95) (100)
E (84)
Closed
K (100) (105)
A, F, K
Closed
None
A (S)
B, G
F (B)
K
K (F)
G
K (95)
G (95) G (K)
24
Tugas Individu • • • • • •
Iterative Deepening A* (IDA*) Simplified Memory-Bounded A* (SMA*) Bi-directional A* (BDA*) Modified bi-directional A* (MBDA*) Dynamic Weighting A* (DWA*) Beam A* (BA*)
25
Tugas Kelompok Simulasi teknik pencarian (searching) pada game “8-puzzle” menggunakan algoritma: • BFS Initial State Goal State • DFS 8 4 6 1 2 3 1 7 4 5 6 • Hill Climbing 5 3 2 7 8 • A* Tools: Matlab 26
