36
Dengan menggunakan fungsi heuristic manhattan
distance, didapatkan
nilai iterasi dan jumlah langkah yang
paling kecil dibanding dengan menggunakan fungsi
heuristic yang lainnya.
2.
Straight Line Distance
Straight line distance
adalah fungsi heuristic
yang digunakan
pada aplikasi yang dapat bergerak ke
segala arah/sudut. Rumus
straight line distance :
h(n) = sqrt((x
n
– x
goal
)² + (y
n
– y
goal
)²)
Dimana :
x
n
adalah koordinat x dari node pertama pada grid.
x
goal
adalah koordinat x dari final node.
y
n
adalah koordinat y dari node pertama pada grid.
y
goal
adalah koordinat y dari final node.
Kekurangan penggunaan fungsi heuristic straight line distance,
yaitu :
Masalah tidak semua dapat dipecahkan. Terutama pada
pengujian dengan menggunakan nilai g(n) yang besar.
Dalam algoritma A* dengan fungsi heuristic straight line
distance, apabila terdapat sedikit hambatan pada ruang
pencarian maka walaupun ditemukan jalurnya, pasti
membutuhkan banyak iterasi.
Kesulitan pencarian jalur tersebut, terjadi karena dalam
perhitungan nilai fungsinya, yaitu h(n) = sqrt((x
n
– x
goal
)²
+ (y
n
–
y
goal
)²), maka nilai yang dihasilkan kecil sehingga
 |