23
closed
set
digunakan,
maka
h
juga
harus
konsisten
(monoton)
agar
A*
bisa optimal.
Metode A* juga sangat optimal dan efisien untuk setiap heuristic
h, di mana hal ini berarti bahwa tidak ada algortima lain yang
menerapkan metode heuristic yang sama akan mendapatkan node yang
lebih sedikit dari A*, kecuali ketika terdapat beberapa solusi parsial di
mana h secara tepat memperkirakan nilai cost dari jalur optimal.
A* dapat menerima dan dapat memperhitungkan node lebih
sedeikit bila dibandingkan dengan algoritma lainnya, karena A* mulai
bekerja dari estimasi cost yang “optimistic” dari jalur yang dia lalui –
optimistic di sini adalah nilai cost sebenarnya dari jalur yang dilalui untuk
menuju node tujuan akan maksimal sama besar dengan nilai estimasi
yang dihasilkan. Akan tetapi, secara kritis, selama hasil pencarian metode
A* diperoleh, nilai estimasi “optimistic” tersebut mungkin akan dapat
diperoleh.
Ketika A* berhenti melakukan pencarian, dapat diartikan bahwa
A*
menemukan
sebuah jalur
di
mana
nilai
cost yang sebenarnya lebih
kecil
dari
nilai
estimasi
cost
dari
jalur
lainnya
yang
melalui
open
node
manapun.
Tetapi
sejak
estimasi
tersebut “optimistic”, A* bisa
mengabaikan secara aman node-node tersebut. Dengan kata lain, A* tidak
akan
pernah
melewatkan
kemungkinan
adanya
jalur
dengan
nilai
cost
yang rendah dan oleh karena itu hasilnya dapat diterima.
Asumsikan sekarang ada sebuah algoritma
lain pencarian
lainnya
A, menghentikan pencariannya dengan hasil jalur di mana nilai cost
 |