Ai 20111024
0 likes586 views
Dokumen tersebut membahas metode-metode pencarian dalam masalah penyelesaian masalah yang meliputi: (1) pencarian tidak terinformasi seperti breadth-first search dan depth-first search, (2) pencarian terinformasi seperti uniform cost search, greedy best-first search, dan A* search, (3) contoh penerapan uniform cost search dan A* search untuk masalah agen turis Rumania.
Ai 20111024
- 1. Metode Pelacakan Heuristik Inteligensi Buatan (MKB6403) Kuliah 5 SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN TEKNIK KOMPUTER INDONESIA (STMIK-INDONESIA) 息 2011 Uninformed VS Informed Search Uninformed search hanya menggunakan informasi dari definisi masalah. Sedangkan informed search menggunakan informasi lain (contoh: path cost) dalam mencari solusi Jenis-jenis uninformed search: Breadth-first search Depth-first search Depth-limited search Iterative deepening search Jenis-jenis informed search: Uniform cost search Greedy best-first search Best-first search A*search 11/5/2011 Metode Pelacakan Heuristik 2
- 2. 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 di mana node disortir berdasarkan path cost function g(n) Jika semua step cost sama, uniform cost sama dengan breadth-first search 11/5/2011 Metode Pelacakan Heuristik 3 Contoh Penerapan UCS A 1 10 B 5 5 S G 15 C 5 11/5/2011 Metode Pelacakan Heuristik 4
- 3. Contoh Penerapan UCS A S 0 1 10 B 5 5 S G 15 C 5 11/5/2011 Metode Pelacakan Heuristik 5 Contoh Penerapan UCS A S 0 1 10 B 5 5 S G A 1 B 5 C 15 15 C 5 11/5/2011 Metode Pelacakan Heuristik 6
- 4. Contoh Penerapan UCS A S 0 1 10 B 5 5 S G A 1 B 5 C 15 15 C 5 G 11 11/5/2011 Metode Pelacakan Heuristik 7 Contoh Penerapan UCS A S 0 1 10 B 5 5 S G A 1 B 5 C 15 15 C 5 G 11 G 10 11/5/2011 Metode Pelacakan Heuristik 8
- 5. Latihan Cari solusi dari Arad ke Bucharet dengan menggunakan UCS! 11/5/2011 Metode Pelacakan Heuristik 9 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 menyatakan perkiraan seberapa bagus suatu node Implementasi: fringe adalah sebuah priority queue dimana node disortir berdasarkan f(n) 11/5/2011 Metode Pelacakan Heuristik 10
- 6. Fungsi Heuristik Kunci keberhasilan best-first search terletak pada heuristic function Heuristic adalah: rule of thumb 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 11/5/2011 Metode Pelacakan Heuristik 11 Contoh Fungsi Heuristik Heuristic function untuk agent turis Rumania: hSLD(n) = jarak straight-line distance dari n ke Bucharest 11/5/2011 Metode Pelacakan Heuristik 12
- 7. Greedy Best-first Search Prinsip 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 11/5/2011 Metode Pelacakan Heuristik 13 Greedy Best-first Search Prinsip 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 Sibiu 253 Timisoara 329 Zerind 374 11/5/2011 Metode Pelacakan Heuristik 14
- 8. Greedy Best-first Search Prinsip 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 Sibiu Timisoara 329 Zerind 374 Rimnicu Fagaras 176 Oradea 380 193 Vilcea 11/5/2011 Metode Pelacakan Heuristik 15 Greedy Best-first Search Prinsip 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 Sibiu Timisoara 329 Zerind 374 Rimnicu Fagaras Oradea 380 193 Vilcea Bucharest 0 11/5/2011 Metode Pelacakan Heuristik 16
- 9. 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 h(n) = estimasi path cost dari n ke goal f(n) = estimasi total cost melalui n 11/5/2011 Metode Pelacakan Heuristik 17 Penerapan A* Search Arad 366 = 0 + 366 11/5/2011 Metode Pelacakan Heuristik 18
- 10. Penerapan A* Search Arad Sibiu Timisoara Zerind 393=140+253 447=118+329 449=75+374 11/5/2011 Metode Pelacakan Heuristik 19 Penerapan A* Search Arad Sibiu Timisoara Zerind 447=118+329 449=75+374 Rimnicu Fagaras Oradea Vilcea 415=239+176 671=291+380 413=220+193 11/5/2011 Metode Pelacakan Heuristik 20
- 11. Penerapan A* Search Arad Sibiu Timisoara Zerind 447=118+329 449=75+374 Rimnicu Fagaras Oradea Vilcea 415=239+176 671=291+380 Craiova Pitesti 526=366+160 417=317+100 11/5/2011 Metode Pelacakan Heuristik 21 Penerapan A* Search Arad Sibiu Timisoara Zerind 447=118+329 449=75+374 Rimnicu Fagaras Oradea Vilcea 671=291+380 Bucharest Craiova Pitesti 450=450+0 526=366+160 417=317+100 11/5/2011 Metode Pelacakan Heuristik 22
- 12. Penerapan A* Search Arad Sibiu Timisoara Zerind 447=118+329 449=75+374 Rimnicu Fagaras Oradea Vilcea 671=291+380 Bucharest Craiova Pitesti 450=450+0 526=366+160 Bucharest Craiova 418=418+0 615=455+160 11/5/2011 Metode Pelacakan Heuristik 23