41
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*
tidak
efektif dan
efisien.
Jika
algoritma ini
diharapkan
melakukan pencarian rute
dengan lebih
cepat
tanpa
mengharuskan
memperoleh
rute
terpendek,
maka
fungsi
heuristicnya
suatu saat dapat overestimate
terhadap
biaya dari
suatu
titik
ke tujuan
atau
fungsi
biaya
atas
suatu
jarak
disesuaikan
dengan
fungsi
heuristicnya.
Fungsi
heuristic
yang baik adalah
bila
lebih
rendah dari
biaya
yang
sebenamya
terhadap
jarak
antara
suatu
titik dengan
tujuan.
Fungsi
heuristic
yang
pada
umumnya
digunakan
pada
algoritma
A*
adalah
heuristic
manhattan
distance.
Contoh
heuristic
yang
sering
digunakan pada
pathfinding
yaitu:
I.
Manhattan
distance
adalah
heuristic
standar
untuk
algoritma
A*,
digunakan
pada
aplikasi
yang
hanya
rnerniliki
4 arah
gerakan dan
tidak
boleh
bergerak secara
diagonal.
H(n)
=
b
*
(abs
(n. x- tujuan.
x)
+
abs(n.
y
tujuan.
y))
Dimana:
n= titik
saat
ini
h(n)=
fungsi heuristic dari
titik
n
b= fungsi biaya
x. y =
koordinat (x,
y)
abs=
fungsi
absolute
2.
Diagonal
Distance adalah
heuristic
yang
digunakan apabila
aplikasinya
memiliki 8 arah gerakan atau
bila
bergerak
secara
diagonaL
 |