14
node.
Koneksi-koneksi
tersebut
kemudian
dibalikkan
kembali
untuk
membentuk
path
yang benar.
2.1.3. Memilih Fungsi Heuristik
Semakin
akurat
heuristik
yang
digunakan,
semakin
sedikit
fill yang
akan
dialami
oleh
A*,
dan
semakin
cepat
dijalankan.
Jika heuristik
yang
sempurna
digunakan
(yang
selalu
mengembalikan
jarak
path
minimum antara
2 node
yang
sangat
tepat),
A*
akan
langsung
mengarah
pada
jawaban
yang
tepat:
algoritma
akan
menjadi O(p),
di
mana
p
adalah jumlah langkah dalam path (Millington dan Funge, 2009, p215).
Sayangnya,
untuk
menemukan
jarak
yang
tepat
antara
dua nodes,
biasanya
rute
terpendek
di
antara
kedua node
tersebut
harus
ditemukan,
yang
mungkin
berarti
menyelesaikan permasalahan pathfinding.
Untuk heuristik yang tidak sempurna, A* berlaku sedikit berbeda tergantung pada
apakah heuristik tersebut terlalu rendah atau terlalu tinggi, berikut adalah penjelasannya:
a. Heuristik yang Terlalu Rendah
Jika heuristik terlalu rendah, maka A* memerkirakan terlalu rendah panjang
path
aktual, A*
membutuhkan waktu
lebih
lama
untuk dijalankan. Perkiraan total cost
akan
condong ke arah cost sejauh
ini (karena
nilai
heuristik
terlalu kecil dari kenyataan). Jadi
A*
lebih
memilih
untuk
memeriksa node
yang
lebih dekat ke start node, daripada
yang
lebih dekat ke tujuan. Ini akan meningkatkan waktu yang diperlukan untuk menemukan
rute menuju tujuan.
Jika
heuristik
terlalu
rendah,
maka
hasil
yang
dihasilkan
A*
akan
menjadi
path
terbaik
yang
memungkinkan,
dan
akan
menjadi
path
yang
benar-benar
sama
dengan
 |