11
dipindahkan ke open list saat
mereka ditemukan pada
ujung koneksi. Node dipindahkan
ke closed list setelah diproses dalam iterasi masing-masing.
Tidak seperti sebelumnya, node dari open
list dengan perkiraan total cost terkecil
dipilih
pada
setiap
iterasi,
yang
hampir
selalu
berbeda
dari node
dengan
cost terkecil
sejauh ini.
Perubahan
ini
mengijinkan
algoritma
tersebut
memeriksa node
yang
lebih
menjanjikan
terlebih
dahulu.
Jika
node
memiliki
perkiraan total
cost
yang
kecil,
maka
node
tersebut
pasti
memiliki
cost sejauh
ini
yang
relatif
kecil
dan
perkiraan
jarak
ke
tujuan yang relatif kecil pula. Jika perkiraannya akurat,
maka nodes yang lebih dekat ke
tujuan akan dipertimbangkan terlebih
dahulu, mempersempit pencarian ke area yang
paling menguntungkan.
c. Menghitung Jarak Sejauh Ini untuk Open dan Closed Nodes
Seperti sebelumnya, setelah sampai pada open atau closed node selama
iterasi, dan
nilai
yang
terekam
harus
direvisi.
Nilai
cost
sejauh
ini
terhitung
wajar,
dan
jika
nilai
baru
lebih
rendah dari
nilai
untuk node
yang sudah
ada,
maka
nilainya perlu di-update.
Dilakukan
perbandingan
ini
secara
ketat
berdasarkan
nilai cost
sejauh
ini
(hanya
nilai
yang dapat diandalkan, karena tidak mengandung nilai perkiraan apa pun), bukan
perkiraan total cost.
Tidak seperti Dijkstra, algoritma A* dapat menemukan rute yang lebih baik
menuju
node
yang
sudah
ada
pada closed
list.
Jika
nilai
sebelumnya
sangat
optimistis,
maka node mungkin telah diproses untuk berpikir bahwa itu adalah pilihan terbaik,
yang
pada kenyataannya, bukan.
Hal
ini
mengakibatkan knock-on problem. Jika node
yang
meragukan telah
diproses dan dimasukkan dalam
closed list,
maka berarti semua koneksinya telah
 |