18
Dimana :
•
d
adalah
nilai biaya. Dimana
nilai d
didapat dari
nilai
minimum
cost
perpindahan antar node
•
Xn adalah koordinat X dari node pertama pada grid
•
Xgoal adalah koordinat X dari final node
•
Yn adalah koordinat dari node pertama pada grid
•
Ygoal adalah koordinat Y dari final node.
2.7.1
Perbandingan Fungsi
Heuristic
:
1.
Menggunakan 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.
•
Dengan menggunakan fungsi
heuristic
manhattan
distance,
didapatkan nilai
iterasi
dan
jumlah
langkah
yang
paling
kecil
dibanding dengan menggunakan fungsi heuristic yang lain.
2.
Menggunakan fungsi heuristic straight
line distance
•
Masalah
tidak semuanya dapat dipecahkan.
Terutama
pada pengujian
dengan menggunakan nilai g yang besar.
•
Dalam
algoritma
A
Star
dengan
fungsi
heuristic
straight
line
distance, apabila
terdapat
sedikit
hambatan
pada
ruang
pencarian,
 |