16
2.7
Fungsi
Heuristic
Menurut
Amit.J.Patel (2003,
p1),
heuristic
merupakan
aturan-aturan
untuk
memilih
cabang-cabang
yang
memiliki
kemungkinan mengarah
pada
pemecahan
masalah.
Karena
heuristic
menggunakan
informasi
yang terbatas
maka
heuristic
mungkin
gagal
dalam
memprediksi
perilaku
secara
tepat
dalam
suatu
pencarian.
Heuristic
dapat
membantu
menunjukkan arah
yang
tepat
bagi
suatu
algoritma,
tetapi
mungkin juga gagal dalam memberikan petunjuk kepada algoritma tersebut.
Algoritma
A*
tanpa
fungsi
heuristic
yang
baik
akan
memperlambat
pencarian
dan
dapat
menghasilkan
rute
yang
tidak
tepat. Untuk
menghasilkan
rute
yang
benar-
benar
tepat,
maka
fungsi
heuristic-nya
harus
underestimate
terhadap
biaya
dari
suatu
node
ke
final
node.
Fungsi
heuristic
yang
sempurna akan
membuat
algoritma
A*
langsung
menuju
final
node tanpa
harus mencari ke arah-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
ke
segala
arah
yang
mungkin.
Hal
ini
dikarenakan tidak
cukupnya
informasi
mengenai
masalah
yang
dihadapi,
sehingga
menyebabkan algoritma
A*
melakukan pencarian
lebih
banyak
dan
lebih
lama.
Jika
algoritma ini
diharapkan
melakukan pencarian dengan lebih cepat tanpa
memperoleh rute
terpendek,
maka
fungsi
heuristic-nya suatu saat dapat overestimate.
Beberapa fungsi heuristic yang umum digunakan pada algoritma pathfinding
A*
adalah sebagai berikut (Patel, Amit.J., 2003, p1) :
1.
Manhattan Distance
Manhattan Distance adalah fungsi heuristic standar untuk algoritma A*.
 |