31
suatu himpunan tertutup digunakan, maka h juga harus monoton (atau konsisten )
untuk A* menjadi optimal. Ini berarti bahwa untuk setiap pasangan node yang
berdekatan x dan y , di mana d (x, y) menunjukkan panjang tepi antara mereka, kita
harus memiliki:
Hal ini memastikan bahwa untuk setiap jalur X dari node awal untuk x :
di mana L adalah fungsi yang menunjukkan panjang jalan, dan Y adalah
jalur X diperluas untuk mencakup y . Dengan kata lain, tidak mungkin untuk
mengurangi (jarak total sejauh + perkiraan jarak yang tersisa) dengan memperluas
jalan untuk memasukkan node tetangga. (Hal ini analog dengan pembatasan bobot
tepi nonnegatif dalam algoritma Dijkstra .) monotonicity
menyiratkan diterimanya
ketika perkiraan heuristik pada setiap node tujuan itu sendiri adalah nol, karena
(membiarkan P = (f, v 1 , v 2 , ..., v n , g) menjadi jalan terpendek dari node f untuk
tujuan terdekat g ):
A * juga efisien secara optimal untuk setiap heuristik h , yang berarti bahwa
tidak ada algoritma yang optimal mempekerjakan heuristik yang sama akan
memperluas node kurang dari A *, kecuali ketika ada beberapa solusi parsial di
mana h tepatnya memprediksi biaya jalur yang optimal. Bahkan dalam kasus ini,
untuk setiap grafik ada ada beberapa urutan memutuskan hubungan dalam antrian
prioritas seperti bahwa A * memeriksa paling sedikit mungkin node.
Sedangkan kriteria diterimanya menjamin jalur solusi optimal, itu juga
berarti bahwa A* harus memeriksa semua jalan
sama berjasa untuk
menemukan jalur yang optimal. Hal ini dimungkinkan untuk mempercepat
pencarian dengan mengorbankan optimalitas dengan relaksasi kriteria
 |