Saya punya masalah dengan algoritma bintang jatuh. Ini tugas akhir saya dan saya butuh bantuan.
Pertanyaan saya adalah bagaimana saya bisa menghitung algoritma bintang jatuh heuristik? Saya dapat menggunakan bintang jatuh pgrouting , tapi saya tidak mengerti bagaimana menghitung bintang jatuh heuristik.
Saya telah mencari bintang jatuh heuristik menghitung di buku internet tapi saya tidak dapat menemukannya sekarang.
Bisakah Anda ceritakan tentang algoritma bintang jatuh, bukan hanya kode sumber, Tn. Mario?
pgrouting
routing
shooting-star
donni
sumber
sumber
Saya mendapatkan yang ini dari milis. Pemotretan * berbasiskan tepi, jadi ia berpindah dari tepi ke tepi sementara A * dan Dijkstra beralih dari titik ke titik. Dengan demikian Anda memerlukan struktur data yang menjaga semua tepi yang berdekatan untuk setiap tepi grafik Anda. Ini juga dapat dilakukan dengan membuat grafik garis (http://en.wikipedia.org/wiki/Line_graph) dari jaringan jalan asli Anda. Dan kemudian Anda dapat menetapkan biaya bagian ujung ke ujung (sebagai atribut khusus dari struktur tepi yang berdekatan atau sebagai biaya grafik garis) yang sebenarnya mewakili segala jenis batasan atau penalti untuk berpindah dari satu sisi ke sisi lainnya - seperti sebagai pembatasan belokan dalam kasus belokan atau jenis pembatasan lainnya seperti lampu lalu lintas. Dengan ini, Anda dapat menggunakan A * atau algoritma jalur terpendek lainnya menggunakan tepi sebagai simpul.
Jadi, itulah ide di balik Penembakan *.
Dan saya mendapatkan yang ini dari Anton Patrushev: http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/276.html . Anda menulis seperti ini: Di A * kami menggunakan sesuatu yang mirip dengan fungsi Manhattan (| Dx | + | Dy |) / 2 http://pgrouting.postlbs.org/browser/trunk/core/src/astar_boost_wrapper.cpp#L75 Di sana Anda akan melihat upaya lain dikomentari. Kami mencoba fungsi berbeda OK. Mungkin, itu alasan historis. fungsi heuristik dan untuk beberapa alasan (saya tidak ingat sekarang) memutuskan bahwa untuk jaringan jalan umum ini Dalam Pemotretan * kami menggunakan jarak Euclidian. http://pgrouting.postlbs.org/browser/trunk/core/src/shooting_star_boost_wrapper.cpp#L100 .
Rumus lain: - Jarak Euclidean> Sqrt (Dx² + Dy² + Dz²); - Manhattan jarak> | Dx | + | Dy | + | Dz | ; - Jarak maksimum> Max (| Dx |, | Dy |, | Dz |).
Saya masih tidak mengerti tentang semua. Teman, Bisakah Anda ceritakan secara singkat dan detail tentang proses pengambilan gambar algoritma bintang?
sumber