15
yang dihasilkan oleh Dijkstra. Hal ini menghindarkan masalah mengenai path sub-
optimal. Jika heuristik terlalu tinggi, jaminan ini akan hilang.
Dalam aplikasi-aplikasi
dimana
akurasi
lebih
penting
daripada
performa,
sangat
penting untuk memastikan bahwa heuristik yang digunakan rendah. Saat menghadapi
permasalahan
mengenai path planning di permasalahan komersial dan akademis, akurasi
seringkali lebih penting, maka heuristik yang terlalu rendah dibatasi.
b. Heuristik yang Terlalu Tinggi
Jika
heuristik
terlalu
tinggi,
maka
diperkirakan
panjang
path
aktual
terlalu
panjang, A* mungkin tidak
menghasilkan path terbaik. A* akan cenderung
menghasilkan path dengan nodes yang lebih sedikit, bahkan jika koneksi di antara nodes
terlalu tinggi.
Nilai perkiraan total cost akan membias kepada heuristik. Algoritma A* akan lebih
tidak
memerhatikan
secara
proporsional cost
sejauh
ini
dan
akan
cenderung
lebih
menyukai
nodes
yang
memiliki
sisa
jarak
yang
lebih
kecil.
Hal
ini
akan
menggeser
fokus pencarian ke tujuan lebih cepat, namun dengan risiko kehilangan rute terbaik.
Ini
berarti
bahwa
panjang
total
dari
path
mungkin
lebih
besar
dari
panjang
total
dari
path
terbaik.
Untungnya,
tidak
berarti
bahwa
akan
langsung
didapat
path
yang
buruk. Dapat ditunjukan bahwa jika heuristik memandang terlalu tinggi oleh sebagian
besar x (yakni x adalah pandangan terlalu tinggi terbesar untuk setiap node dalam
graph), dan final path tidak akan lebih dari x lagi.
Heuristik yang memandang terlalu tinggi terkadang disebut "heuristik yang tidak
dapat
diterima."
Ini
bukan
berarti
heuristik tersebut
tidak dapat
digunakan;
ini
merujuk
pada fakta bahwa algoritma A* tidak lagi menghasilkan path terpendek.
 |