9
Jika
heuristik
selalu
menghasilkan
0,
maka
perkiraan
total cost
selalu
akan
sama
dengan cost sejauh
ini. Saat
A*
memilih node dengan perkiraan total cost terkecil, node
dengan cost sejauh ini terkecil dipilih. Hal ini sangat mirip dengan Dijkstra. A* dengan
heuristik 0 adalah versi pathfinding dari Dijkstra.
2.1.1. Sejarah Algoritma A*
Algoritma
A*
yang
menggabungkan
cost
path
saat
ini
dengan
heuristic search,
dikembangkan oleh Hart, Nilsson, dan Raphael, dengan beberapa koreksi lanjutan (Hart
et al., 1972). Dechter dan Pearl mendemonstrasikan efisiensi secara optimal dari A*.
Tulisan mengenai A* yang asli memperkenalkan kondisi konsistensi pada fungsi
heuristik. Kondisi monoton diperkenalkan
oleh Pohl sebagai pengganti yang lebih
sederhana, namun Pearl menunjukkan bahwa keduanya ekuivalen (Pearl, 1984, p83-85).
Pohl memelopori pembelajaran tentang hubungan antara galat (error) dalam
fungsi heuristik dengan kompleksitas waktu dari A*. Hasil dasar yang diperoleh untuk
tree
search
dengan
unit
steps
costs
dan
node
tujuan
tunggal
(Pohl,
1977;
Gasching,
1979;
Huyn
et
al.,
1980;
Pearl,
1984)
serta
dengan
node
tujuan
jamak
(Dinh
et
al.,
2007).
"Effective
branching
factor" diusulkan oleh Nilsson
sebagai
pengukuran
empiris
dari
efisiensi;
ekuivalen
dengan
mengasumsikan
time
cost dari
O((b)
d
). Karena
tree
search
diaplikasikan
pada
graph,
Korf
et
al.
menentang
bahwa
time
cost
lebih baik
dimodelkan
sebagai
O(b
d-k
), dimana
k
bergantung
pada
akurasi
heuristik;
sehingga
analisis
ini
mengasilkan beberapa kontroversi. Untuk graph search,
Helmert dan
Röger
mencatat
beberapa
permasalahan yang
terkenal
yang
mengandung
banyak
node
secara
eksponen dalam path solution optimal,
menyiratkan kompleksitas waktu eksponen
untuk
A* bahkan dengan galat mutlak konstan pada h.
 |