35
2.9.3
Perbandingan Fungsi A* Heuristic
Beberapa fungsi heuristic
yang umum digunakan pada algoritma
pathfinding A* adalah sebagai berikut :
1.
Manhattan Distance
Manhattan distance
adalah fungsi heuristic
standar untuk
algoritma A*. Digunakan pada aplikasi yang memiliki 4 arah
gerakan (tidak dapat bergerak diagonal). Rumus manhattan
distance :
h(n) = d * (abs(x
n
– x
goal
) + abs(y
n
– y
goal
))
Dimana :
d
adalah nilai biaya. d
didapat dari nilai minimum cost
perpindahan antar node.
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.
Berikut adalah kelebihan dari penggunaan fungsi heuristic
manhattan distance :
Semua jalur-jalur dapat ditemukan (masalah dapat
dipecahkan).
Hal ini disebabkan karena pada setiap penambahan nilai
g(n),
pada perhitungan nilai heuristic-nya terjadi pula
perubahan pada nilai d-nya. Sehingga dengan penambahan
nilai g(n), tidak mempengaruhi pencarian jalur.
 |