28
Open list adalah tempat menyimpan data simpul yang mungkin diakses dari
starting point maupun simpul yang sedang dijalankan.
Closed list
adalah tempat menyimpan data simpul sebelum A yang juga
merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
Harga (F) adalah nilai yang diperoleh dari penjumlahan nilai G, jumlah nilai
tiap simpul dalam jalur terpendek dari starting point ke A, dan H, jumlah nilai
perkiraan dari sebuah simpul ke simpul tujuan.
Simpul tujuan yaitu simpul yang dituju.
Rintangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak
dapat dilalui oleh A.
Algoritma A* dapat dijelaskan dengan pseudocode dibawah ini :
1.
Masukan node awal ke open list
2.
Loop Langkah – langkah di bawah ini :
a.
Cari node n dengan nilai f(n)
yang paling rendah dalam open list.
Node ini sekarang menjadi current node.
b.
Keluarkan current node dari open list dan masukan ke close list.
c.
Untuk setiap tetangga dari current node lakukan berikut :
Jika tidak dapat dilalui atau sudah ada dalam close list,
abaikan.
Jika belum ada di open list. Buat current node parent dari
node tetangga ini. Simpan nilai f, g, dan h dari node ini.
Jika sudah ada di open list, cek bila node tetangga ini lebih
baik, menggunakan nilai g sebagai ukuran. Jika lebih baik
ganti parent
dari node
ini di open
list
menjadi current
node, lalu kalkulasi ulang nilai g dan f dari node ini.
 |