19
dengan menggunakan metode ini dan dengan heuristic yang tepat menghasilkan
sebuah hasil yang optimal, yaitu A*. Secara umum, Depth-first search (DFS)
dan breadth-first search (BFS) adalah dua kasus special dari metode A*.
Algoritma Dijkstra's merupakan kasus yang paling special dari A* , di mana h(x)
= 0 , untuk semua x.
Dalam masalah pencarian rute di mana metode A* sering digunakan, A*
secara bertahap membangun semua rute yang mengarah mulai dari titik awal
sampai akhirnya mencapai titik akhir. Metode A* hanya membangung 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, di mana biasanya merupakan
perkiraan dari jarak jalan.
2.4.1.1
Fungsi A* Heuristic
fungsi adalah aturan yang menugaskan sebuah output untuk
tiap-tiap input yang diberikan. Aturan mendefinisikan suatu fungsi dapat
dispesifikasi oleh suatu formula, relasi, atau
tabel
yang
mendaftar output
terhadap
input.
Pola
terpenting
dari suatu fungsi adalah ia bersifat
deterministik,
yakni
selalu
menghasilkan
output
yang
sama
dari
input
yang sama. Input sering disebut argumen fungsi, dan output disebut nilai
fungsi
A*
mempertahankan
sebagian
dari
solusi, sebagai contoh jalur
pada
graph
dimulai
dari
node
awal,
akan
disimpan
dalam
sebuah
queue
 |