際際滷

際際滷Share a Scribd company logo

Pertemuan 05

Download as PPT, PDF
Mekrin Mekrin
Mekrin Mekrin
1 of 10
Download to read offline
Best-First-Search Teknik Best-First-Search adalah teknik search yang menggabungkan kebaikan yang ada dari teknik Depth- First-Search dan Breadth-First-Search. Tujuan menggabungkan dua teknik search ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang ditelusuri. Untuk mendapatkan jalur yang menjanjikan adalah dengan memberikan skala prioritas pada setiap stata saat dihasilkan dengan fungsi heuristic.
Untuk menggunakan Best-First-Search, kita memerlukan dua daftar simpul, yaitu : 1. OPEN berisi simpul yang dihasilkan dari fungsi heuristic tapi belum dievaluasi, memilki antrian prioritas dimana elemen dengan prioritas tertinggi adalah yang memiliki nilai paling baik yang dihasilkan fungsi heuristic. 2. CLOSED berisi simpul yang sudah dievaluasi. Kita perlu tetap menyimpan simpul-simpul ini dalam memori jika kita ingin melakukan search pada Graph, sehingga jika kita menemui suatu simpul kita bisa memeriksa apakah simpul ini sudah pernah dieavaluasi atau belum
Algoritma Best-First-Search : 1. Mulai dengan OPEN hanya berisi initial state 2. Sampai goal ditemukan atau tidak ada lagi simpul yang tersisa dalam OPEN, lakukan : a. Pilih simpul terbaik dalam OPEN b. Telusuri successor-nya c. Untuk tiap successor, lakukan : i. Jika belum pernah ditelusuri sebelumnya, evaluasi simpul ini, tambahkan kedalam OPEN dan catat parentnya. ii. Jika sudah pernah ditelusuri, ganti parent nya jika jalur baru lebih baik dari sebelumnya.
Contoh Best First Search A A CB D(3) (1)(5) (6) A CB D(3) (1)(5) E F(4) Step 1 Step 2 Step 3
A CB D(3) (1)(5) E F(4) (6)G H(6) (5) Step 4
A CB D(3) (1)(5) E F(4) (6)G H(6) (5) I J(2) (1) Step 5
Contoh lain Best-First-Search Diketahui sebuah puzzle berukuran 3X3 yang berisi angka. Permasalahan adalah angka-angka dalam puzzle tersebut belum teratur. Nilai awal puzzle : Goal : Nilai awal = {1,2,blank,4,5,3,7,8,6} Goal = {1,2,3,4,5,6,7,8,blank} Nilai heuristic = f(n) = g(n) + h(n) g(n) = kedalaman dari pohon h(n) = jumlah angka yang masih salah posisi 1 2 4 5 3 7 8 6 1 2 3 4 5 6 7 8
Level 1 Level 2
THE ENDTHE END
THE ENDTHE END

More Related Content

Pertemuan 05

  • 1. Best-First-Search Teknik Best-First-Search adalah teknik search yang menggabungkan kebaikan yang ada dari teknik Depth- First-Search dan Breadth-First-Search. Tujuan menggabungkan dua teknik search ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang ditelusuri. Untuk mendapatkan jalur yang menjanjikan adalah dengan memberikan skala prioritas pada setiap stata saat dihasilkan dengan fungsi heuristic.
  • 2. Untuk menggunakan Best-First-Search, kita memerlukan dua daftar simpul, yaitu : 1. OPEN berisi simpul yang dihasilkan dari fungsi heuristic tapi belum dievaluasi, memilki antrian prioritas dimana elemen dengan prioritas tertinggi adalah yang memiliki nilai paling baik yang dihasilkan fungsi heuristic. 2. CLOSED berisi simpul yang sudah dievaluasi. Kita perlu tetap menyimpan simpul-simpul ini dalam memori jika kita ingin melakukan search pada Graph, sehingga jika kita menemui suatu simpul kita bisa memeriksa apakah simpul ini sudah pernah dieavaluasi atau belum
  • 3. Algoritma Best-First-Search : 1. Mulai dengan OPEN hanya berisi initial state 2. Sampai goal ditemukan atau tidak ada lagi simpul yang tersisa dalam OPEN, lakukan : a. Pilih simpul terbaik dalam OPEN b. Telusuri successor-nya c. Untuk tiap successor, lakukan : i. Jika belum pernah ditelusuri sebelumnya, evaluasi simpul ini, tambahkan kedalam OPEN dan catat parentnya. ii. Jika sudah pernah ditelusuri, ganti parent nya jika jalur baru lebih baik dari sebelumnya.
  • 4. Contoh Best First Search A A CB D(3) (1)(5) (6) A CB D(3) (1)(5) E F(4) Step 1 Step 2 Step 3
  • 5. A CB D(3) (1)(5) E F(4) (6)G H(6) (5) Step 4
  • 6. A CB D(3) (1)(5) E F(4) (6)G H(6) (5) I J(2) (1) Step 5
  • 7. Contoh lain Best-First-Search Diketahui sebuah puzzle berukuran 3X3 yang berisi angka. Permasalahan adalah angka-angka dalam puzzle tersebut belum teratur. Nilai awal puzzle : Goal : Nilai awal = {1,2,blank,4,5,3,7,8,6} Goal = {1,2,3,4,5,6,7,8,blank} Nilai heuristic = f(n) = g(n) + h(n) g(n) = kedalaman dari pohon h(n) = jumlah angka yang masih salah posisi 1 2 4 5 3 7 8 6 1 2 3 4 5 6 7 8