ai 20111024

Metode Pelacakan Heuristik

SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN TEKNIK KOMPUTER INDONESIA (STMIK-INDONESIA)

© 2011

Inteligensi Buatan (MKB6403)

Kuliah 5

Uninformed VS Informed Search

� Uninformed search hanya menggunakan informasi daridefinisi masalah. Sedangkan informed search menggunakaninformasi lain (contoh: path cost) dalam mencari solusi

� Jenis-jenis uninformed search:

� Breadth-first search

Depth-first search� Depth-first search

� Depth-limited search

� Iterative deepening search

� Jenis-jenis informed search:

� Uniform cost search

� Greedy best-first search

� A*search

11/5/2011 Metode Pelacakan Heuristik 2

Best-first search

Uniform Cost Search

• Prinsip uniform cost search:

Lakukan node expansion terhadap node di fringe

yang path cost-nya paling kecil → cheapest solution

• Implementasi: fringe adalah sebuah priority queue• Implementasi: fringe adalah sebuah priority queue

di mana node disortir berdasarkan path cost

function g(n)

• Jika semua step cost sama, uniform cost sama

dengan breadth-first search


Contoh Penerapan UCS

S G

A

B

1

5 5

10


S G

C15 5


S G

A

B

1

5 5

10

S 0


S G

C15 5


S G

A

B

1

5 5

10

S

A C

S

B

0

1 5 15


S G

C15 5

1 5 15


S G

A

B

1

5 5

10

S

A C

S

A B

0

1 5 15


S G

C15 5

1 5 15

G 11


S G

A

B

1

5 5

10

S

A C

S

A B

0

1 5 15B


S G

C15 5

1 5 15

G 11 G 10

LatihanCari solusi dari Arad ke Bucharet dengan menggunakan UCS!


Best-first Search

• Prinsip best-first search:

Lakukan node expansion terhadap node di fringe

yang nilai f(n)-nya paling kecil

• f(n) merupakan sebuah evaluation function yang • f(n) merupakan sebuah evaluation function yang

menyatakan perkiraan seberapa “bagus” suatu

node

• Implementasi: fringe adalah sebuah priority queue

dimana node disortir berdasarkan f(n)


Fungsi Heuristik

• Kunci keberhasilan best-first search terletak pada heuristic

function

• Heuristic adalah:

– rule of thumb

– “kiat-kiat sukses”, “tips-tips keberhasilan”– “kiat-kiat sukses”, “tips-tips keberhasilan”

– informasi tambahan bagi si agent (agar lebih sukses) → informed

search

• Heuristic function h(n) adalah fungsi yang menyatakan

estimasi cost dari n ke goal state

• Ada banyak kemungkinan heuristic function untuk sebuah

masalah


Contoh Fungsi Heuristik


Heuristic function untuk agent turis Rumania:

hSLD(n) = jarak straight-line distance dari n ke Bucharest

Greedy Best-first Search


Lakukan node expansion terhadap node di fringe yang nilai f(n)-nya paling

kecil

• Greedy best-first search selalu memilih node yang kelihatanannya paling

dekat ke goal


Arad 366




kecil


dekat ke goal


Arad

Sibiu ZerindTimisoara

Arad

253 329 374




kecil


dekat ke goal


Arad


Arad

329 374Sibiu

Fagaras OradeaRimnicu

Vilcea176 380 193




kecil


dekat ke goal


Arad


Arad

329 374Sibiu


Vilcea380 193Fagaras

Bucharest 0

A* Search

• Prinsip A* search:

Hindari node yang berada di path yang “mahal”

• Evaluation function f(n) = g(n) + h(n)

– g(n) = path cost ke n– g(n) = path cost ke n

– h(n) = estimasi path cost dari n ke goal

– f(n) = estimasi total cost melalui n


Penerapan A* Search

Arad 366 = 0 + 366


Penerapan A* Search

AradArad

Sibiu Timisoara Zerind

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


Penerapan A* Search

AradArad


447=118+329 449=75+374

Sibiu



Vilcea

415=239+176 671=291+380 413=220+193

Penerapan A* Search

AradArad


447=118+329 449=75+374

Sibiu



Vilcea

415=239+176 671=291+380

Rimnicu

Vilcea

Craiova Pitesti

526=366+160 417=317+100

Penerapan A* Search

AradArad


447=118+329 449=75+374

Sibiu



Vilcea

671=291+380

Rimnicu

Vilcea

Craiova Pitesti

526=366+160 417=317+100

Fagaras

Bucharest

450=450+0

Penerapan A* Search

AradArad


447=118+329 449=75+374

Sibiu



Vilcea

671=291+380

Rimnicu

Vilcea

Craiova Pitesti

526=366+160

Fagaras

Bucharest

450=450+0

Pitesti

Bucharest Craiova

418=418+0 615=455+160

ai 20111024

Education