Informed Search (Heuristic) & Eksplorasinya

Kecerdasan Buatan (KI092301)

Informed Search (Heuristic) & Eksplorasinya Chastine Fatichah Teknik Informatika Institut Teknologi Sepuluh Nopember November 2012

12/8/2012

Informed Search (Heuristic) & Eksplorasinya @ Kecerdasan Buatan (KI092301)

1 / 21

Pokok Bahasan

• Uninformed search strategies • Best-first search • Greedy best-first search • A* Search • Heuristic • Ringkasan 12/8/2012


2 / 21

Informed Search Strategies • Uninformed Search : menggenerate state baru, di cek apakah goal atau tidak  kurang efisien

• Informed Search  menggunakan informasi tambahan  lebih efisien

• Bahasan :

• Best-First Search • Greedy Best-First Search • A* Search • Heuristics

12/8/2012


3 / 21

Best-first Search • Secara umum sama dengan Tree-Search ataupun Graph-Search

• Node yang diexpand berdasarkan evaluation • •

function f(n)  fungsi yang menyatakan perkiraan seberapa “bagus” sebuah node  dipilih yang terkecil Fringe  sebuah antrian (queue) di mana node diurutkan berdasarkan f(n) Contoh:

• Greedy best-first search • A* search

12/8/2012


4 / 21

Step Cost & Straight-Line Distance

12/8/2012


5 / 21

Straight-Line Distance • • • • • • • • • •

Arad Bucharest Craivora Dobreta Eforie Fagaras Giurgiu Hirsova Iasi Lugoj

12/8/2012

366 0 160 242 161 176 77 151 226 244

• • • • • • • • • •

Mehadia Neamt Oradea Pitesti Rimnicu Vilcea Sibiu Timisoara Urziceni Vaslui Zerind


241 234 380 100 193 253 329 80 199 374 6 / 21

Greedy best-first Search

• Evaluation Function h(n) (Heuristics) = Estimasi cost dari n ke goal terdekat Misalnya, hSLD(n)=Straight-Line Distance (jarak lurus) dari Bucharest

• Best First Search mengekspand node yang kelihatan mendekati goal

12/8/2012


7 / 21

Contoh Greedy best-first Search Arad 253 Sibiu 366

176

Arad

253 Sibiu 12/8/2012

329 Timisoara 380

Fagaras

366

Oradea

374 Zerind

193 Rimnicu Videa

0

Buchares Informed Search (Heuristic) & Eksplorasinya @ Kecerdasan Buatan (KI092301)

8 / 21

Keterangan Greedy best-first Search

• Complete ?

• Tidak, bisa terjadi looping, misal : Oradea sebagai goal : Iasi  Neamt  Iasi  Neamt …

• Time ?

• O(bm) namun dengan heuristic yang baik akan memberikan improvement yang besar

• Space ? • O(b ) Setiap node disimpan dalam memory • Optimal ? m

• Tidak, perhatikan kasus rute ke Bucharest

sebelumnya, mestinya tidak melalui Fagaras untuk mencapai optimalnya

12/8/2012


9 / 21

A* Search • Ide : Menghindari expanding path yang mahal • Evaluation Function : f(n) = g(n) + h(n) • g(n) = Cost yang dicapai sampai di n • h(n) = Estimasi cost untuk sampai pd goal dari n • f(n) = Estimasi total cost dari path n sampai goal

• A* : admissible heuristic  tidak overestimate

• h(n) <= h*(n) dimana h*(n)  cost sebenarnya • h(n) >= 0 sehingga h(G) = 0 untuk goal G • Contoh, hSLD(n) tidak overestimate terhadap jarak pada jalan sebenarnya

• A* search  Optimal 12/8/2012


10 / 21

Contoh A* Search Arad

366 = 0 + 366

393 = 140 + 253 449 = 75 + 374 447 = 118 + 329

Sibiu

Timisoara

646 = 280 + 366 415=239+176

Arad

671=291+380413=220+193

Fagaras

Oradea

Rimnicu Videa

591=338+253 450=450+0 526 = 366 + 160

Sibiu

Buchares

Craiova

Bucharest 418=418+0 12/8/2012

Zerind

417=317+100

553=300+253

Pinesti

Sibiu

Sibiu 591=338+253


Rimnicu Videa 450=450+0 11 / 21

Pembuktian Optimalitas A* • •

Seperti pada kasus sebelumnya, misal jika ada G2 (goal lain yang suboptimal) yang telah digenerate dan masuk dalam queue. Dan diketahui n merupakan node yang belum diexpand pada path terpendek menuju Goal yang optimal

• •

f(G2) = g(G2), karena h(G2) = 0 > g(G1), karena G2 suboptimal >= f(n), karena h admissible Karena f(G2) > f(n), maka A* tidak akan mengexpand G2

12/8/2012


12 / 21

Optimalitas A* (Kegunaan) • Lemma : A* mengexpand node  menambah nilai f • Dan secara berangsung-angsur menambah “f•

countour” node-node (bandingkan BFS yang menambah layer) Countour i memiliki node-node dg f=fi dimana fi
12/8/2012


13 / 21

Keterangan A* Search

• Complete ?

• Ya, selama jumlah node f <= f(G) terbatas

• Time ? • Exponensial • Space ? • Setiap node disimpan dalam memory • Optimal ? • Ya

• A* mengekspand node-node dengan f(n) < C* • A* mengekspand beberapa node dengan f(n)=C* • A* Tidak akan mengekspand node dengan f(n)>C*

12/8/2012


14 / 21

Pembuktian Lemma : Consistency •

•

Fungsi Heuristic h(n) dikatakan konsisten jika setiap node n dan setiap successor n’ dari n yang digenerate action a, maka estimasi cost dari n sampai ke goal tidak lebih besar dari cost sampai step n’ + estimasi cost n’ ke goal • h(n) <= c(n,a,n’) + h(n’) Jika h(n) konsisten maka nilai dari f(n) melalui suatu path tidak berkurang/nondecreasing • f(n’) = g(n’)+h(n’) = g(n) + c(n,a,n’) + h(n’) >= g(n) + h(n) = f(n) 12/8/2012


15 / 21

Heuristic Function

• Contoh pada 8-puzzles,

• Rata2  b = 3, d =22 • Dgn menghilangkan repeated state, total state menjadi 9!/2 = 181.440 (tidak terlalu besar)

• Tetapi jika pada 15-puzzle ? Secara •

kasarnya mencapai 1013 state (wow!!!) Dibutuhkan suatu good heuristic function

12/8/2012


16 / 21

8-Puzzle Heuristic Function

• Contoh pada 8-puzzles, diusulkan 2 h(n)

• h1 = Jumlah kotak yang salah penempatan • h2 = Manhatan distance  jumlah dari jarak masing•

masing kotak ke tujuan, dengan aturan aturan tidak bisa bergerak secara diagonal Contoh :

• h1 = 8 • h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18

• Dari kedua fungsi heuristic tersebut sudah sama-sama tidak overestimate (solusi sebenarnya = 26 step) 12/8/2012


17 / 21

• • •

•

Pengaruh Akurasi Heuristic pada Performanya Cara menentukan kualitas heuristic adalah dengan efective branching factor b*

d

N+1 = 1 + b* + (b*) 2 + ..+ (b*)d

2

Misal jika solusi pada d=5 dgn 52 node maka b* = 1.92 Heuristic yang baik  b* mendekati 1 Jika h2(n)>h1(n) untuk semua n maka h2 dominates h1 dan memberi solusi yg lebih baik 12/8/2012

Effective Branching Factor

Search Cost IDS

A*(h1)

A*(h2)

IDS

A*(h1)

A*(h2)

10

6

6

2.45

1.79

1.79

4

112

13

12

2.87

1.48

1.45

6

680

20

18

2.73

1.34

1.30

8

6384

39

25

2.80

1.33

1.24

10

47127

93

39

2.79

1.38

1.22

12

3644035

227

73

2.78

1.42

1.24

14

-

539

113

-

1.44

1.23

16

-

1301

211

-

1.45

1.25

18

-

3056

363

-

1.46

1.26

20

-

7276

676

-

1.47

1.27

22

-

18094

1219

-

1.48

1.28

24

-

39135

1641

-

1.48

1.26


18 / 21

Relaxed Problem • • • • •

Relaxed Problem  mengurangi action pada problem Admissible Hueristic dapat diturunkan dari exact solution pada relaxed problem Jika rule 8-puzle dikendurkan(relaxed) sehingga setiap kotak bisa berpindah kemanapun, maka h1(n) akan memberikan solusi terpendek Jika perpindahan hanya boleh untuk yang berdekatan saja, maka h2(n) memberikan solusi terpendek Key Point: biaya solusi optimal dari relaxed problem tidak lebih besar dari biaya solusi optimal problem sebenarnya

12/8/2012


19 / 21

Ringkasan •

• •

•

Heuristic functions mengestimasi biaya pada rute terpendek Good heuristics dapat secara drastis mengurangi biaya pencarian Greedy best-first search mengekspan h terkecil • incomplete dan tidak selalu optimal A* search mengekspan g + h terkecil • complete dan optimal • optimally efficient (up to tie-breaks, for forward search)

12/8/2012


20 / 21

Sumber : 1. Slide perkuliahan Stuart Russell's (Berkeley) http://aima.cs.berkeley.edu/

12/8/2012


21 / 21

Informed Search (Heuristic) & Eksplorasinya

Recommend Documents