18
solusi
terbaik,
tetapi
algoritma
ini
tetap
disebut
heuristic
hingga
solusi
terbaik itu terbukti untuk menjadi yang terbaik.
2.4.1
Metode A* Heuristic
Metode
A*
tanpa
fungsi heuristic
yang baik
akan
memperlambat
pencarian
dan
dapat
menghasilkan
rute
yang
tidak
tepat.
Fungsi
heuristic
yang
sempurna
akan
membuat
metode
A* langsung
menuju
final
node
tanpa
harus
mencari-cari kearah lain. Sehingga jika fungsi heuristicnya terlalu underestimate
akan menyebabkan algoritma ini beranggapan bahwa ada rute lain yang lebih
baik.
Untuk
fungsi
heursitic
yang
underestimate,
bila
nilainya
terlalu
rendah
akan
menyebabkan
algoritma
ini
seperti
algortima
Dijkstra's
yang mencari
kesegala
arah
yang
mungkin.
Hal
ini
dikarenakan tidak ada cukup informasi
mengenai masalah yang dihadapi, sehingga menyebabkan metode A* melakukan
pencarian lebih banyak dan lebih lama.
Dalam ilmu
computer,
A*
(
disebut
“A
star”)
adalah
sebuah
graph
atau
metode tree
search
yang digunakan
untuk
mencari
jalan dari sebuah
node awal
ke
node
tujuan
(goal
node) yang
telah
ditentukan,
metode
ini
menggunakan
“estimasi heuristic” h(x) pada setiap node untuk me-ranking setiap node x
berdasarkan
estimasi
rute
terbaik
yang
melalui
node
tersebut.
Dalam prosesnya
metode
ini
akan
mengunjungi
setiap
node
berdasarkan
urutan
yang
dihasilkan
dari estimasi heuristic
ini. Metode A* adalah salah satu contoh dari
metode best-
first search.
Metode A* dikembangkan oleh Peter Hart, Nils Nilsson, dan Bertram
Raphael, mereka juga menyebut metode tersebut dengan sebutan algoritma A,
 |