6. pencarian heuristik-a
TRANSCRIPT
Fungsi Heuristic:
• Suatu fungsi heuristic dikatakan baik jika bisamemberikan biaya perkiraan yang mendekatibiaya sebenarnya.
• Semakin mendekati biaya sebenarnya, fungsiheuristic tersebut semakin baik.
Ada 2 jenis pencarian terbaik pertama(Best First Search), yaitu:
1. Greedy Best First Search2. Algoritma A*
Greedy Best First Search
• Algoritma ini merupakan jenis algoritma Best First Search yang paling sederhana. Algoritmaini hanya memperhitungkan biaya perkiraansaja,
• Karena hanya memperhitungkan biayaperkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal.
CONTOH
Kesimpulan:
• Dari contoh di atas, Greedy akan menemukansolusi S-B-K-G dengan total jarak = 105
• Padahal ada solusi lain yang lebih optimal yakni: S-A-B-F-K-G dengan total jarak hanya 95
Algoritma A*
• Berbeda dengan Greedy, algoritma ini akanmenghitung fungsi heuristic dengan caramenambahkan biaya sebenarnya denganbiaya perkiraan. Sehingga didapatkan rumus:
• g(n) = biaya sebenarnya dari Node awal kenode n
• h’(n) = biaya perkiraan dari Node n ke node tujuan
Contoh
Perbandingan Greedy Best First Search dengan Algoritma A*
• Greedy tidak bisa menemukan solusi yang optimal
• Algoritma A* dapat menemukan solusi yang optimal
• Algiritma A* lebih baik dalam melakukanpencarian heuristic daripada Greedy Best First Search karena dapat mendapatkan solusi yang optimal.
Contoh terdapat dalam file lain