12
dipertimbangkan.
Mungkin
saja
seluruh
himpunan
node
memiliki cost
sejauh ini
berdasarkan
node
sejauh
ini
dari
node
yang
diragukan.
Meng-update
nilai
dari
node
yang
meragukan tidaklah cukup. Seluruh koneksinya juga harus diperiksa kembali untuk
mendistribusikan nilai baru tersebut.
Dalam kasus
perevisian
node
dalam
open
list,
hal
ini
tidak
diperlukan,
karena
diketahui bahwa koneksi dari sebuah node dalam open list belum diproses. Namun,
ada
cara sederhana untuk memaksa algoritma untuk menghitung kembali dan menyebarkan
nilai
baru
tersebut. Node
dari
closed
list
dapat
dipindahkan
kembali
ke
open
list,
yang
kemudian
akan
menunggu
sampai
tertutup dan koneksinya telah dipertimbangkan
kembali. Node yang bergantung pada nilainya kemudian akan diproses sekali lagi.
Jadi, closed nodes
yang
nilainya
telah
direvisi
dikeluarkan
dari
closed
list
dan
ditempatkan
ke
open
list.
Open
nodes
yang
memiliki
nilai
terevisi
tetap
pada open
list,
seperti sebelumnya.
d. Mengakhiri Algoritma
Dalam banyak
implementasi,
A*
berakhir
saat
node
tujuan
adalah node
terkecil
pada
open list.
Namun
node
yang
memiliki
nilai
perkiraan total
cost
terkecil
(dan oleh
karena
itu
akan
diproses
pada
iterasi
berikutnya
dan
dimasukkan
dalam closed
list)
mungkin
saja
nilainya
harus direvisi
nanti. Tidak ada
lagi
jaminan bahwa
hanya karena
node
tersebut
paling
kecil
di open
list,
maka
shortest
path akan
didapat
di
sana.
Maka,
mengakhiri
A*
saat
node
tujuan
merupakan
terkecil
di
open
list
tidak akan
menjamin
bahwa rute terpendek telah ditemukan.
Oleh
karena
itu,
wajar
untuk
bertanya
apakah A*
dapat
dijalankan
sedikit
lebih
lama untuk menghasilkan hasil yang terjamin optimal. Hal ini dapat dilakukan ini
memerintahkan
algoritma
tersebut
untuk
berakhir
hanya
jika
node
di
open
list
dengan
 |