Ada karya-karya seperti Reach for A * dari para peneliti Microsoft dan Highway Hierarchies oleh Sanders dan Schtolz (jika saya mengeja namanya dengan benar) dari Karlsruhe Uni . Keduanya mengurangi urutan kalkulasi, dan mempercepat ribuan kali pada grafik besar (lihat hasilnya di dokumen yang ditautkan). Pekerjaan terakhir mengarah ke Open Source Routing Machine , yang sayangnya tidak cukup populer dan tidak diadaptasi (saya tidak bisa mengkompilasi walaupun berusaha keras).
Pada saat yang sama, dbs yang saya coba, Spatialite dan PgRouting, menurut dokumen mereka, hanya menawarkan algoritma Dijkstra dan A * . Saya bahkan belum pernah melihat pencarian dua arah yang disebutkan, yang menghemat waktu perhitungan dua kali dalam pengalaman saya.
Apakah ada algoritma yang lebih baik untuk database atau aplikasi lain?
sumber
Jawaban:
Yang benar adalah bahwa kebanyakan orang menggunakan variasi khusus dari algoritma A * . Anda akan melihat ini di sebagian besar "orang besar" (saya tidak bisa mengatakan siapa mereka di forum publik, tetapi saya dapat memberitahu Anda bahwa Anda mungkin menggunakan salah satu dari mereka - dijamin), di mana modifikasi heuristik adalah sangat tergantung pada dataset yang mereka gunakan.
Anda sudah menyebutkan pgrouting , yang saya anggap sebagai opsi "tradisional". Ini baik untuk melakukan algoritma perutean sederhana dan untuk sebagian besar masalah. Juga mudah digunakan dan menggunakan database tradisional di backend-nya.
Namun demikian, itu benar-benar tergantung pada skala dan jenis masalah yang Anda coba selesaikan dan perutean adalah masalah grafik .
Sekali lagi, "orang besar" biasanya memiliki banyak data yang dikaitkan dengan grafik mereka (misalnya, data lalu lintas, rute bus, jalur pejalan kaki) yang memengaruhi algoritma perutean. Ini dikenal sebagai perencana perjalanan multi-modal (di mana Anda juga memiliki pilihan untuk merencanakan "mode" - tidak ada jalur sepeda - hanya angkutan umum - hal semacam itu). Anda bisa memikirkan bagaimana perencanaan perjalanan juga menjadi isu sensitif waktu (yaitu jika Anda berjalan kembali beberapa tepi kembali, Anda akan dapat menangkap kereta bawah tanah yang akan membawa Anda ke tujuan Anda ke depan jauh lebih cepat daripada jika Anda hanya mencoba untuk menavigasi tepi depan menggunakan biaya terendah).
"Orang besar" tidak menyimpan data mereka dalam basis data tradisional, mereka menggunakan grafik yang sudah dihitung sebelumnya (selamat datang di cluster himpunan / mapreduce!). Seperti yang dapat Anda bayangkan, grafik ini menjadi sangat besar, sehingga mengetahui cara menghubungkan tepi grafik yang berdekatan dapat menjadi tantangan.
Bagaimanapun, saya akan merekomendasikan Anda melihat beberapa proyek grafik routing multi-modal:
Graphserver muncul di pikiran. Tidak banyak dokumentasi tetapi banyak kemahiran pengkodean murni (AFAIK, saya percaya MapQuest menggunakan variasi proyek ini untuk beberapa produk routing mereka).
Opsi lain adalah OpenTripPlanner yang memiliki banyak orang pintar di belakangnya (termasuk orang-orang dari graphserver).
sumber
Tidak yakin apakah itu lebih baru tetapi pgRouting memiliki algoritme Shooting-Star :
Ekstensi Analis Jaringan ESRI menggunakan pendekatan hierarkis yang Anda sebutkan untuk membatasi waktu penyelesaian:
Ada buku putih yang sangat rinci dengan contoh-contoh tentang pendekatan ini di situs ESRI - namun mengharuskan Anda untuk masuk untuk mengunduh (Rute Hierarkis Dalam Buku Putih Analis Jaringan ArcGIS).
sumber
Hierarki Kontraksi adalah algoritma yang sangat cepat:
Algoritma ini ramah RAM saat menjalankan kueri (untuk menahan grafik yang dikontrak, diperlukan lebih banyak RAM dan juga preprocessing masif)
Ada beberapa algoritma lain - termasuk yang memecahkan rute angkutan umum:
Microsoft juga melakukan beberapa penelitian:
(Yah, Daniel Delling juga dari Karlsruhe)
Anda bisa mendapatkan pengantar dan ikhtisar bagus dari algoritma yang tersedia:
Peringatan: kuliah bahasa Jerman (!). tetapi setidaknya tajuk dapat membantu Anda mendapatkan informasi lebih lanjut (ALT, Arc-Flags, CHASE, ...) atau literatur yang ditambahkan!
memperbarui
GraphHopper sekarang mengimplementasikan hierarki kontraksi dan juga algoritma lainnya, Anda juga dapat mencoba demo .
sumber