Algoritma A*
Pada
? Bagaimana cara mengetahui apakah suatu kemungkinan menjanjikan?
- Melalui fungsi f (x) = g (x) + h (x)
- Yang merupakan fungsi heuristik
- g (x) adalah biaya untuk, dari asal, mencapai node x
- h (x) adalah fungsi heuristik untuk memperkirakan biaya node berikutnya
- Kami selalu melihat kemungkinan memperluas pohon dan menghitung nilai f (x)
- Kami menambahkan simpul yang memiliki f (x) terkecil di antara yang kami temukan
- OA* adalah algoritma yang paling efisien untuk cara minimum dalam grafik
- Namun, itu keterbatasan yang parah
- Perlu untuk mendefinisikan h (x) yang dapat diterima: ia tidak akan pernah mengembalikan nilai yang lebih besar dari jarak aktual dari x ke y
- Jika H (x) dapat diterima, tetapi terlalu meremehkan jarak yang sebenarnya, algoritma ini sangat tidak efisien. Jika h (x) tidak dapat diterima, algoritma mungkin tidak menemukan cara minimum
? Kompleksitas
- Kompleksitas tergantung langsung pada fungsi h (x) yang digunakan.
- Dalam kasus terburuk, jumlah node yang dieksplorasi bersifat eksponensial dalam ukuran jalur terkecil, tetapi memiliki kompleksitas polinomial jika h ∗ (x) −h (x) ≤o (logh ∗ (x)).
? Kapan bagus untuk digunakan?
- Grafik di mana seseorang dapat meremehkan jarak antara dua simpul, seperti pada peta
- Jarak terpendek antara dua titik adalah garis, tetapi mungkin jarak sebenarnya akan lebih besar dari itu
? Apa cara minimum dalam kasus ini?
Jalankan proyek
Hasil
Penulis
Lisensi
Proyek ini berada di bawah MIT. Lihat di sini untuk informasi lebih lanjut.
