13
cost
sejauh
ini
(bukan
perkiraan
total
cost)
terkecil
memiliki
nilai cost
sejauh
ini
lebih
besar
dari
cost
path
yang
ditemui
menuju
tujuan.
Dengan
cara
itu,
dan
hanya
dengan
cara
itu
dapat
terjamin
bahwa
tidak
ada path
masa
depan
akan
ditemukan
yang
membentuk shortcut.
Ini merupakan kondisi pengakhiran efektif yang dapat dilihat pada Dijkstra, dan
dapat
ditunjukkan
bahwa
menerapkan
kondisi
ini
akan
menghasilkan
jumlah fill yang
sama selayaknya
menggunakan algoritma pathfinding Dijkstra. Node mungkin saja
dicari dengan urutan yang berbeda, dan mungkin saja ada sedikit perbedaan dalam
himpunan node di open list,
namun tingkat fill rata-rata sama. Dengan kata
lain, Dijkstra
mengambil seluruh kelebihan performa dari A* dan membuatnya tidak bernilai.
Implementasi A* seluruhnya bergantung pada kenyataan bahwa A*
dapat
menghasilkan hasil yang tidak optimal secara teoritis. Untungnya, hal ini dapat
dikendalikan dengan
fungsi
heuristik.
Tergantung pada pemilihan
fungsi
heuristik,
hasil
optimal
akan
terjamin,
atau
hasil
sub-optimal
yang
memberikan
eksekusi
yang
lebih
cepat dapat dengan sengaja diijinkan.
Karena A* sering berhubungan dengan hasil sub-optimal, implementasi A* dalam
jumlah
besar
malah
berakhir
saat node tujuan dikunjungi pertama tanpa menunggunya
untuk
menjadi terkecil di open list. Kelebihan performa A*
tidak sebesar
melakukan
hal
yang sama
pada Dijkstra, namun banyak pengembang merasa setiap bit berharga,
terutama saat algoritma tidak dibutuhkan untuk menjadi optimal.
e. Mengambil Path
Path
terakhir
didapat
dengan
cara
yang
benar-benar
sama
seperti
sebelumnya:
dengan
memulai dari tujuan dan
mengakumulasi koneksi
saat bergerak
mundur ke start
 |