10
2.1.2. Langkah–Langkah Algoritma A*
Algoritma ini bekerja dengan cara yang
mirip dengan Dijkstra. Daripada
mempertimbangkan
open
node
dengan
nilai
cost sejauh
ini
terendah,
node
yang
paling
mungkin
untuk
menuju
path
terpendek
secara
keseluruhan
dipilih,
yang
dikendalikan
oleh
heuristik. Jika
heuristik akurat,
maka algoritma tersebut akan efisien. Jika
heuristik
tidak
tepat,
maka
algoritma
akan
bekerja lebih
buruk
dari
Dijkstra.
Berikut
merupakan
langkah-langkah algoritma A* (Millington dan Funge, 2009, p206):
a. Memroses Current Node
Selama
iterasi,
A*
mempertimbangkan
setiap
koneksi
yang
keluar
dari current
node.
Untuk
setiap
koneksi,
A*
menemukan
end
node
dan
menyimpan
total
cost
dari
path sejauh ini dan koneksi yang sampai ke sana, sama seperti sebelumnya.
Sebagai
tambahan,
A*
menyimpan
satu
nilai
lagi:
perkiraan
dari
cost
total
untuk
sebuah path dari start node menuju current node dan menuju tujuan (selanjutnya disebut
perkiraan total cost). Perkiraan
ini
merupakan jumlah dari dua
nilai: cost sejauh
ini
dan
seberapa
jauh
dari
node
tersebut
hingga
tujuan.
Perkiraan
ini
dihasilkan dari
potongan
kode yang terpisah dan bukan bagian dari algoritma tersebut.
Perkiraan-perkiraan
ini disebut "nilai
heuristik" dari suatu node, dan
nilainya tidak
dapat negatif (karena cost dalam graph tidak negatif, dan tidak masuk akal jika
perkiraan
negatif).
Penggenerasian
dari
nilai heuristik adalah perhatian
utama
dalam
mengimplementasikan algoritma A*.
b. Node List
Seperti
sebelumnya,
algoritma
ini
menyimpan
daftar
dari open
node
yang
telah
dikunjungi
namun
belum
diproses
dan
closed
node
yang
telah
diproses.
Node
 |