33
A
e
Memilih node dengan fungsi A f (n) + B h
F
(n) , di
mana A dan B adalah konstanta. Jika tidak ada node dapat dipilih, algoritma
akan mundur dengan fungsi C f (n) + D h
F
(n) , di mana C dan D adalah
konstanta.
A* upaya untuk mempromosikan eksploitasi mendalam-
pertama dengan memilih node baru ini diperluas. Alpha * menggunakan
fungsi biaya
f
a
(n) = (1 + w
a
(n)) f (n) , di
mana
, di mana ? dan ? adalah
konstanta dengan
,
p (n) adalah induk dari n, dan ñ adalah paling baru
memperluas simpul.
kompleksitas waktu dari A* tergantung pada heuristik. Dalam kasus
terburuk, jumlah node diperluas adalah eksponensial dalam panjang dari
solusi (jalan terpendek), tetapi polinomial ketika ruang pencarian adalah
pohon, ada negara tujuan tunggal, dan fungsi heuristik h memenuhi Kondisi
berikut:
di mana h
*
adalah heuristik
optimal, biaya yang tepat untuk mendapatkan dari x ke tujuan. Dengan kata
lain, kesalahan h tidak akan tumbuh lebih cepat daripada logaritma dari
"heuristik yang sempurna" h
*
yang mengembalikan jarak yang benar
dari x ke tujuan.
A* mempertahankan sebagian dari solusi, sebagai contoh jalur pada
graph dimulai dari node
awal, dan akan disimpan dalam sebuah queue
yang
 |