21
menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari
selalu dapat ditemukan.
Heuristic
memperbaiki proses pencarian solusi walaupun tidak harus sampai
mengatasi kasus terburuk (worst case scenario). Heuristic
ini mengembangkan
efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan
kelengkapan (completeness). Algoritma ini biasanya mencari solusi yang dekat
dengan solusi yang terbaik dan proses pencariannya cepat dan mudah. Fungsi
heuristic
h(n)
adalah perkiraan biaya termurah dari node
n
ke node
tujuan. Fungsi
heuristic
melambangkan cost
yang akan dikeluarkan agent, jika memilih node
tertentu.
Heuristic
adalah sebuah algoritma yang mungkin saja menemukan solusi
yang baik tetapi tidak ada bukti bahwa solusinya tidak bisa menjadi buruk secara
tidak masuk akal, dan tidak ada argument tentang ini bahwa hal ini mungkin saja bisa
terjadi.
Fungsi heuristic
yang sempurna
akan membuat algoritma A* langsung
menuju final node
tanpa harus mencari ke arah lain. Sehingga jika fungsi heuristic-
nya terlalu underestimate
akan menyebabkan algoritma ini beranggapan bahwa ada
rute yang lebih baik dari rute yang ada. Untuk fungsi heuristic
yang underestimate,
bila nilainya terlalu rendah akan menyebabkan algoritma ini seperti algoritma
Dijkstra yang mencari kesegala arah yang mungkin. Hal ini dikarenakan tidak
cukupnya informasi mengenai masalah yang dihadapi, sehingga menyebabkan
algoritma A* melakukan pencarian lebih banyak dan lebih lama.
 |