Bab 4. Informed Search Review Pada bab 3 dapat disimpulkan hal hal sbb: • • • •
Ada banyak cara untuk memanfaatkan knowledge saat menformulasikan suatu masalah dalam bentuk states dan operators. GENERAL-SEARCH algorithm hanya dapat memanfaatkan knowledge yang diperoleh dari type antrian (queuing function) yang menentukan children nodes yang akan di “generate” berikutnya. Uninformed search strategies dapat dimanfaatkan untuk mencari solusi bagi suatu masalah dengan cara men “generate” new states secara sistematic dan memeriksa/membandingkan state tersebut dengan goal state. Cara ini umumnya tidak effisien karena strategy yang dipakai “defined by picking the order of node expansion”.
Mengingat kelemahan diatas maka dikembangkan search techniques yang berbeda dengan blind search diatas yang disebut Heuristic search. Ada dua cara heuristic search yang banyak digunakan yaitu: 1. Best First Search 2. A* search (baca: A star).
Pengertian “Heuristic” Blind search hanya dapat membedakan suatu node merupakan goal node atau non-goal node. Pada kenyataannya terdapat beberapa “problem-specific knowledge” yang dimiliki yang dapat membantu membimbing (“guide”) proses searching, yang disebut heuristic. Kata “heuristic” diturunkan dari bahasa Greek “heuriskein” yang artinya “to find” atau “to discover”. Beberapa definisi dari heuristic dijumpai antara lain: • The study of methods for discovering and inventing problem solving techniques, partucularly for the problem of coming up with mathematical proff [George Polya, 1957] • A process that may solve a given problem, but offers no guarantees of doing so is called a heuristic for that problem [Newell & Simon, 1963] Misalnya: h(n) = estimate of distance from node n to a goal node. (straight line on map). Jika diberikan list of nodes yang dapat di “expand” maka node dengan h(n) minimal yang paling menjanjikan menuju pada goal state.
Best First Search • • •
Idea: gunakan suatu evaluation function untuk setiap node dalam menentukan tingkat “desirability” dari node tersebut dan expand most desirable unexpanded node, Implementasi : insert successors in decreasing order of desirability Special cases dari Best First Search adalah Greedy Search dan A* atau A Star.
Greedy Search Akan kita tinjau contoh tentang Romania yang lalu
• • • •
Evaluation function h (n) = estimate of cost from n to goal Misalnya hSLD (n) = straight line distance from n to Bucharest Greedy search akan meng expand node yang kelihatannya “closest to goal”. Greedy search steps dapat dilihat pada gambar berikut
Karakteristik dari Greedy Search: Complete ??
No, dapat stuck di loop, misalnya: lasi Neamt lasi Complete in finite space with repeated-state checking
Time??
O (b ), but a good heuristic can give dramatic improvement
m
Neamt
m
Space??
O (b ), keeps all nodes in memory
Optimal??
No
hSLD dari Arad ke Bucharest adalah melalui path Bucharest Fagaras Sibiu Arad Dan mendapatkan total cost 140 + 99 + 211 = 450 Greedy search tidak optimal karena dengan melalui path Arad Sibiu Rimnicu Pitesti Bucharest akan mendapatkan total cost 140 + 80 + 97 + 101 = 418, jadi lebih kecil dari hSLD diatas. Maka Best First adalah Greedy karena setiap kali Best First takes biggest step.
A * search A * didasarkan pada suatu basic Idea yaitu “avoid expanding paths that already expensive”. Evaluation function: f (n) = g (n) + h (n) Dimana:
g (n) = cost so far to reach n h (n) = estimated cost to goal from n f (n) = estimated total cost of path through n to goal
Pada A* , kita perhitungkan 2 factor yaitu 1. Path dari start sampai ke current position n melalui function g(n) dan ini merupakan suatu actual value 2. Path dari current position n ke goal melalui fungsi h(n) dan ini merupakan suatu estimasi. Total kedua nilai inilah yang akan menghasilkan estimasi path cost dari start to goal melalui current possition n.
A* search menggunakan admissible heuristic dimana h (n) lebih kecil atau maksimum sama dengan h* (n) dimana h* (n) adalah true cost dari n. Misalnya hSLD (n) tidak pernah lebih besar dari actual road distance. A* bersifat optimal.
A* search steps Start:
Arad h (n) = hSLD (Arad) = 366
Expand Arad: 1. Zerind with distance from Arad = 75
hSLD (Zerind) = 374 f (Zerind) = 75 + 374 = 449 2. Sibiu with distance from Arad = 140 hSLD (Sibiu) = 253 f (Sibiu) = 140 + 253 = 393 3. Timisoara with distance from Arad = 118 hSLD (Sibiu) = 329 f (Sibiu) = 118 + 329 = 447 Dari tiga buah expanded node diatas, A* akan meng “expand” Sibiu untuk ekspansi selanjutnya mengingat cost to Bucharest through Sibiu is the lowest. Keseluruhan search sampai ke Bucharest dapat dilihat pada gambar dibawah
Contoh : Eight Puzzle
Ada dua kemungkinan heuristik yang dapat digunakan untuk 8-puzzle problem diatas yaitu: h1(n) = number of misplaced tiles h2(n) = total Manhattan distance (number of squares from desired location of each tile) Manakah dari kedua heuristics diatas yang lebih baik ? untuk digunakan dalam search. Dari hasil perhitungan/pengamatan kedua state S dan G diatas diperoleh: h1(S) = 7 h2(S) = 2 + 3 + 3 + 2 + 4 + 2 + 0 + 2 = 18
If h2(n) > atau sama dengan h1(n) untuk seluruh nilai n ( jadi keduanya admissible) maka h2 akan lebih baik dari pada h1 untuk search. Untuk beberapa contoh problem lainnya penggunaan A* dengan h(n) admissible yang berbeda dibandingkan dengan IDS pada d (depth) = 14 akan diperoleh perbandingan yang sangat significant seperti dibawah ini: d = 14 Search Nodes expanded 1 Nodes expanded 2
IDS 3.473.941 Too many
A* (h1) 539 39.135
A* (h2) 113 1.641
Dari tabel diatas terlihat A* jauh lebih baik dari IDS dan A* akan sangat tergantung pada pemilihan algoritma admissible heuristik yang digunakan yaitu nilai h(n). Different heuristic function akan sangat berpengaruh pada saat nilai d semakin besar seperti terlihat pada tabel berikut:
Seringkali sulit dalam mendapatkan suatu heuristics yang admissible. Untuk mengatasi hal ini, admissible heuristic bisa didapatkan (derived) dari exact solution cost of a relaxed version dari problem ybs. Sebagai contoh: • Jika rules dari 8-puzzle problem are relaxed (disederhanakan) dimana tile dapat dipindahkan kemana saja (anywhere), maka h1(n) akan memberikan shortest solution. • Jika rules dari 8-puzzle problem are relaxed (disederhanakan) dimana tile dapat dipindahkan ke any adjacent square, maka h2(n) akan memberikan shortest solution. • Pada problem TSP, jika path merupakan any structure yang menghubungkan seluruh cities, kita akan memperoleh minimum spanning tree heuristic. Seringkali pada problem tertentu, path is irrelevant answer, namun goal state adalah solusi yang diinginkan. Akibatnya, state space akan merupakan suatu set of “complete” configuration, misalnya mencari optimal configuration pada TSP atau mencari konfigurasi yang memenuhi suatu constraint tertentu seperti halnya pada n-queens problem. Untuk kasus problem seperti diatas, seringkali harus digunakan iterative improvement algorithm, dimana kita harus menyimpan suatu „single current state“ dan try to improve that through iteration.
Contoh relaxed problem 1
2
