40
memandu
pencarian
rute
dalam
menentukan
arah
pencarian terbaik
tanpa
harus
mencari
ke segala
arah.
Bila
temyata arah
yang
diikuti tidak
dapat sampai ke
tujuan maka
algoritma ini
dapat
backtrack
untuk
mencari
rute
lain
yang
mempunyai
kemungkinan
mencapai
tujuan.
Algoritma
ini
akan
kembali
mencari
rute
dengan
biaya
terendah
dari
titik
awal
hingga
akhir.
2.4.2.
Heuristic
Menurut
Silitonga (1993b), Heuristic
adalah
suatu
aturan tentang perkiraan
secara
ilmiah
maupun
intuitif
untuk
mengurangi
atau
membatasi
wilayah
pencarian
yang
sulit
dilakukan.
Menurut
Luger
dan
Stubblefield
(1993c,
pll6),
heuristic
merupakan
aturan
aturan
untuk
memilih
cabang-cabang
yang
memiliki
kemungkinan mengarah
pada
pemecahan
masalah. Karena
heuristic
menggunakan
informasi
yang
terbatas,
maka
heuristic
jarang
dapat
memprediksi
perilaku
yang
tepat
dalam
suatu
pencarian.
Suatu
heuristic dapat berhasil
atau
gaga!memberikan petunjuk
untuk
suatu
algoritma.
Algoritma
A*
tanpa fungsi
heuristic
yang bagus akan
memperlambat
pencarian
dan
dapat
menghasilkan rute
yang
bukan
terpendek. Jika
algoritma ini
diharapkan
menghasilkan rute
yang
benar-benar terpendek, maka
fungsi heuristicnya harus
underestimate
terhadap biaya dari
suatu
titik
ke tuj uan. Fungsi
heuristic
yang
sempurna
akan
membuat a!goritma ini
langsung
menuju
titik
tujuan
tanpa
harus
mengecek
seluruh
node.
Sehingga bila
fungsi
heuristicnya terlalu underestimate
menyebabkan algoritma
ini
selalu
beranggapan bahwa
ada
rute
yang
lebih baik
dari
rute
yang
ada.
Untuk
fungsi
heuristic
yang underestimate
bila
nilainya
terlalu
rendah
akan
menyebabkan
algoritma
 |