29
d.
Hentikan loop jika :
Node goal telah ditambahkan ke openlist, yang berarti
rute
telah ditemukan.
Belum menemukan node goal sementara open list kosong
atau berarti tidak ada rute.
3.
Simpan rute. Secara ‘backward’, urut mulai dari node goal ke parent-nya
terus sampai mencapai node
awal sambil menyimpan node
ke dalam
sebuah array.
Dalam masalah pencarian rute dimana metode A* sering digunakan, A*
secara bertahap membangun semua rute yang mengarah mulai dari titik awal
sampai akhirnya mencapai titik akhir. Metode A* hanya membangun rute yang
mungkin digunakan untuk mencapai tujuan. Untuk mengetahui rute mana yang
memungkinkan mengarah ke titik akhir, A* menggunakan estimasi heuristic jarak
dari sembarang node
ke node
tujuan. Dalam kasus pencarian rute, ini bisa jadi
sama dengan jarak lurus antara dua titik, dimana biasanya merupakan perkiraan
dari jarak jalan.
2.9.2
Fungsi A* Heuristic
Fungsi adalah aturan yang menugaskan sebuah output untuk tiap-tiap
input
yang diberikan. Aturan mendefinisikan suatu fungsi dapat
dispesifikasikan oleh suatu formula, relasi, atau tabel yang mendaftar output
terhadap input. Pola terpenting dari suatu fungsi adalah ia bersifat
deterministic, yakni selalu menghasikan output
yang sama dari input
yang
 |