Algoritma apa yang menghitung arah dari titik A ke titik B pada peta?

543

Bagaimana penyedia peta (seperti Google atau Yahoo Maps) menyarankan arah?

Maksud saya, mereka mungkin memiliki data dunia nyata dalam beberapa bentuk, tentu saja termasuk jarak tetapi juga mungkin hal-hal seperti kecepatan mengemudi, keberadaan trotoar, jadwal kereta api, dll. Tetapi anggaplah data itu dalam format yang lebih sederhana, katakanlah grafik yang diarahkan sangat besar dengan bobot tepi mencerminkan jarak. Saya ingin dapat dengan cepat menghitung arah dari satu titik arbitrer ke titik lainnya. Kadang-kadang titik-titik ini akan berdekatan (dalam satu kota) sementara kadang-kadang mereka jauh (lintas negara)

Algoritma grafik seperti algoritma Dijkstra tidak akan berfungsi karena grafiknya sangat besar. Untungnya, algoritma heuristik seperti A * mungkin akan berfungsi. Namun, data kami sangat terstruktur, dan mungkin semacam pendekatan berjenjang mungkin berhasil? (Misalnya, simpan arah yang telah dikomputasi antara titik "kunci" tertentu berjauhan, serta beberapa arah lokal. Lalu arah untuk dua titik jauh akan melibatkan arah lokal ke titik kunci, arah global ke titik kunci lain, dan kemudian lokal arah lagi.)

Algoritma apa yang sebenarnya digunakan dalam praktik?

PS. Pertanyaan ini dimotivasi dengan menemukan kebiasaan dalam arah pemetaan online. Berlawanan dengan ketimpangan segitiga, terkadang Google Maps berpikir bahwa XZ membutuhkan waktu lebih lama dan lebih jauh daripada menggunakan titik perantara seperti di XYZ . Tapi mungkin arahan jalan kaki mereka juga mengoptimalkan parameter lain?

PPS. Berikut ini pelanggaran lain atas ketimpangan segitiga yang menunjukkan (kepada saya) bahwa mereka menggunakan semacam pendekatan berjenjang: XZ versus XYZ . Yang pertama tampaknya menggunakan Boulevard de Sebastopol yang terkenal meskipun itu sedikit keluar dari jalan.

Sunting : Tak satu pun dari contoh ini yang tampaknya berfungsi lagi, tetapi keduanya berhasil pada saat posting asli.

A. Rex
sumber
3
BTW, Algoritma A * "adalah generalisasi dari algoritma Dijkstra yang mengurangi ukuran subgraph yang harus dieksplorasi, jika informasi tambahan tersedia yang memberikan batas bawah pada" jarak "ke target"
Mitch Wheat
Re A *: ya, memang. Untungnya, dalam kasus kami, "informasi tambahan" ini tersedia misalnya dengan menggunakan jarak garis lurus. Ketika saya mengatakan "Dijkstra" di atas, maksud saya vanilla Dijkstra.
A. Rex
Petunjuk arah berjalan? Entah tentang tempat lain, tetapi di sekitar sini (Hampshire, Inggris), big G tidak memiliki data pejalan kaki - ini mengarahkan saya di sepanjang jalan di sekitar kawasan pejalan kaki dll. Satu-satunya hal yang baik adalah mengubah perkiraan waktu yang diambil untuk rute :)
jTresidder
Saya tidak terlalu peduli jika arah untuk mengemudi atau berjalan. Saya hanya ingin tahu cara kerjanya! Alasan saya memiliki tautan berjalan karena saya menghitung cara berjalan di sekitar Paris dan melihat semua 66 air mancur Wallace. (Titik akhir dari peta-peta itu seharusnya adalah air mancur Wallace.)
A. Rex
Karunia pada pertanyaan ini adalah untuk mendorong lebih banyak dan lebih baik jawaban, terutama dari orang-orang yang bekerja di salah satu penyedia utama. Komentar tentang struktur data, algoritma, berapa banyak yang dihitung, dll., Semuanya dihargai.
A. Rex

Jawaban:

526

Berbicara sebagai seseorang yang menghabiskan 18 bulan bekerja di sebuah perusahaan pemetaan, yang termasuk mengerjakan algoritma routing ... ya, Dijkstra's berfungsi, dengan beberapa modifikasi:

  • Alih-alih melakukan Dijkstra sekali dari sumber ke dest, Anda mulai di setiap ujung, dan memperluas kedua belah pihak sampai mereka bertemu di tengah. Ini menghilangkan sekitar setengah pekerjaan (2 * pi * (r / 2) ^ 2 vs pi * r ^ 2).
  • Untuk menghindari menjelajahi lorong belakang setiap kota antara sumber dan tujuan Anda, Anda dapat memiliki beberapa lapisan data peta: Lapisan 'jalan raya' yang hanya berisi jalan raya, lapisan 'sekunder' yang hanya berisi jalan-jalan sekunder, dan sebagainya. Kemudian, Anda menjelajahi hanya bagian yang lebih kecil dari lapisan yang lebih terperinci, berkembang seperlunya. Jelas deskripsi ini menyisakan banyak detail, tetapi Anda mendapatkan idenya.

Dengan modifikasi di sepanjang jalur itu, Anda bahkan dapat melakukan perutean lintas negara dalam jangka waktu yang sangat wajar.

Nick Johnson
sumber
29
Seseorang yang mengerjakan ini di dunia nyata, luar biasa! Apakah Anda tahu seberapa besar kemungkinan untuk melakukan precompute, seperti dalam artikel tentang Google yang disebutkan dalam komentar lain?
A. Rex
10
Kami tidak melakukan preprocessing dari sifat itu, tetapi tentu saja tampaknya seperti optimasi yang menarik.
Nick Johnson
29
"itu hanya dijamin untuk menghasilkan solusi, belum tentu yang paling efisien" Ini tidak benar; selama heuristik yang digunakan dapat diterima, algoritma A * menghasilkan jalur paling murah. Admissible berarti bahwa biayanya tidak pernah di atas perkiraan, tetapi mungkin diremehkan (tetapi estimasi yang buruk akan memperlambat algoritme). Menggunakan data dari pra-pemrosesan cenderung membantu membuat heuristik yang lebih baik, dan karenanya membuat A * bekerja lebih cepat.
a1kmm
6
Sebenarnya, dengan pertimbangan lebih lanjut, Anda sepenuhnya benar. Anda bisa meningkatkan algoritme yang ada untuk memanfaatkan ini dengan hanya menambahkan Great Circle Distance antara node target dan tujuan ke biaya tepi yang dievaluasi. Saya sebenarnya tidak yakin apakah algoritma kami melakukan itu - tetapi ini adalah optimasi yang sangat masuk akal.
Nick Johnson
11
A *, dalam kasus terburuk (heuristik yang mengatakan semua jalur setara), persis sama dengan Djikstra.
Tordek
111

Pertanyaan ini telah menjadi bidang penelitian aktif dalam beberapa tahun terakhir. Gagasan utamanya adalah melakukan preprocessing pada grafik satu kali , untuk mempercepat semua pertanyaan berikut . Dengan informasi tambahan ini, rencana perjalanan dapat dihitung dengan sangat cepat. Namun, Algoritma Dijkstra adalah dasar untuk semua optimisasi.

Arachnid menggambarkan penggunaan pencarian dua arah dan pemangkasan tepi berdasarkan informasi hierarkis. Teknik percepatan ini bekerja dengan sangat baik, tetapi algoritma terbaru mengungguli teknik ini dengan segala cara. Dengan algoritma saat ini, jalur terpendek dapat dihitung dalam waktu kurang dari satu milidetik pada jaringan jalan kontinental. Implementasi cepat dari algoritma Dijkstra yang tidak dimodifikasi membutuhkan sekitar 10 detik .

Artikel Rekayasa Algoritma Perencanaan Rute Cepat memberikan gambaran tentang kemajuan penelitian di bidang itu. Lihat referensi makalah itu untuk informasi lebih lanjut.

Algoritma yang paling cepat diketahui tidak menggunakan informasi tentang status hierarkis jalan dalam data, yaitu jika itu adalah jalan raya atau jalan lokal. Sebagai gantinya, mereka menghitung dalam langkah preprocess sebuah hierarki sendiri yang dioptimalkan untuk mempercepat perencanaan rute. Precomputation ini kemudian dapat digunakan untuk memangkas pencarian: Jauh dari awal dan jalan lambat tujuan tidak perlu dipertimbangkan selama Algoritma Dijkstra. Manfaatnya adalah kinerja yang sangat baik dan jaminan kebenaran untuk hasilnya.

Algoritma perencanaan rute yang dioptimalkan pertama hanya berurusan dengan jaringan jalan statis, yang berarti tepi dalam grafik memiliki nilai biaya tetap. Ini tidak benar dalam praktiknya, karena kami ingin mempertimbangkan informasi dinamis seperti kemacetan lalu lintas atau pembatasan kendaraan. Algoritma terbaru juga dapat menangani masalah seperti itu, tetapi masih ada masalah yang harus dipecahkan dan penelitian sedang berlangsung.

Jika Anda memerlukan jarak jalur terpendek untuk menghitung solusi untuk TSP , maka Anda mungkin tertarik pada matriks yang berisi semua jarak antara sumber dan tujuan Anda. Untuk ini, Anda bisa mempertimbangkan Menghitung Banyak-ke-Banyak Jalur Terpendek Menggunakan Hirarki Jalan Raya . Perhatikan, bahwa ini telah ditingkatkan dengan pendekatan yang lebih baru dalam 2 tahun terakhir.

SebastianK
sumber
1
Benar-benar mencerahkan. Apa pendekatan baru yang Anda sebutkan?
Tomas Pajonk
1
Dalam Hierarki Kontraksi tertentu. Anda dapat menemukannya lebih lanjut di sini: algo2.iti.kit.edu/routeplanning.php . Ada juga pembicaraan teknologi google tentang hal itu: youtube.com/watch?v=-0ErpE8tQbw
SebastianK
19

Hanya menangani pelanggaran ketimpangan segitiga, semoga faktor tambahan yang mereka optimalkan adalah akal sehat. Anda tidak perlu menginginkan rute terpendek atau tercepat, karena dapat menyebabkan kekacauan dan kehancuran . Jika Anda ingin arahan Anda lebih memilih rute utama yang ramah truk dan dapat mengatasi setiap pengemudi yang mengikuti sat-nav mengirimkannya, Anda dengan cepat membuang ketidaksetaraan segitiga [1].

Jika Y adalah jalan perumahan sempit antara X dan Z, Anda mungkin hanya ingin menggunakan pintasan melalui Y jika pengguna secara eksplisit meminta XYZ. Jika mereka meminta XZ, mereka harus tetap berpegang pada jalan utama bahkan jika itu sedikit lebih jauh dan memakan waktu sedikit lebih lama. Ini mirip dengan paradoks Braess - jika semua orang mencoba mengambil rute terpendek dan tercepat, kemacetan yang dihasilkan berarti bahwa itu bukan rute tercepat untuk siapa pun lagi. Dari sini kita menyimpang dari teori grafik ke teori permainan.

[1] Faktanya, harapan apa pun bahwa jarak yang dihasilkan akan menjadi fungsi jarak dalam arti matematis mati ketika Anda mengizinkan jalan satu arah dan kehilangan persyaratan simetri. Kehilangan ketimpangan segitiga juga hanya menggosok garam di luka.

stevemegson
sumber
14

Berikut algoritma routing tercepat di dunia yang dibandingkan dan terbukti kebenarannya:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

Berikut ini pembicaraan teknologi google tentang hal ini:

http://www.youtube.com/watch?v=-0ErpE8tQbw

Berikut ini adalah implementasi dari algoritma hierarki jalan raya sebagaimana dibahas oleh schultes (saat ini hanya di berlin, saya sedang menulis antarmuka dan versi mobile juga sedang dikembangkan):

http://tom.mapsforge.org/

Eikes
sumber
9

Saya belum pernah bekerja di Google atau Microsoft atau Yahoo Maps sebelumnya, jadi saya tidak bisa memberi tahu Anda cara kerjanya.

Namun, saya melakukan arsitek sistem optimasi rantai pasokan kustom untuk perusahaan energi yang mencakup aplikasi penjadwalan dan perutean untuk armada truk mereka. Namun, kriteria kami pada perutean jauh lebih spesifik untuk bisnis daripada di mana konstruksi atau lalu lintas melambat atau penutupan jalur.

Kami menggunakan teknik yang disebut ACO (Ant colony optimization) untuk menjadwalkan dan mengarahkan truk. Teknik ini adalah teknik AI yang diterapkan pada masalah salesman keliling untuk menyelesaikan masalah routing. Trik dengan ACO adalah membangun perhitungan kesalahan berdasarkan fakta-fakta perutean yang diketahui sehingga model penyelesaian grafik tahu kapan harus berhenti (kapan kesalahannya cukup kecil).

Anda dapat google ACO atau TSP untuk menemukan lebih banyak tentang teknik ini. Saya belum menggunakan salah satu alat AI open-source untuk ini, jadi tidak bisa menyarankan satu (meskipun saya mendengar SWARM cukup komprehensif).

Tagihan
sumber
4
routing! = tsp. di tsp Anda tahu semua jarak dan Anda mengoptimalkan stop order - ini bukan point to point algo.
Karussell
8

Algoritma grafik seperti algoritma Dijkstra tidak akan berfungsi karena grafiknya sangat besar.

Argumen ini tidak selalu berlaku karena Dijkstra biasanya tidak akan melihat grafik yang lengkap tetapi hanya subset yang sangat kecil (semakin baik grafik yang saling berhubungan, semakin kecil subset ini).

Dijkstra mungkin benar-benar berkinerja cukup baik untuk grafik yang berperilaku baik. Di sisi lain, dengan parametrization yang cermat A * akan selalu tampil sama baiknya, atau lebih baik. Sudahkah Anda mencoba bagaimana kinerjanya pada data Anda?

Karena itu, saya juga sangat tertarik untuk mendengar tentang pengalaman orang lain. Tentu saja, contoh penting seperti pencarian Google Map sangat menarik. Saya bisa membayangkan sesuatu seperti heuristik tetangga terdekat yang terdekat.

Konrad Rudolph
sumber
2
Misalkan Anda mencoba menemukan arah dari titik A ke B, jarak optimal untuk yang d. Algoritma Dijkstra akan, paling tidak, memeriksa semua titik paling jauh dari A. Jika A adalah San Francisco dan B adalah Boston, ini berarti ia memeriksa sebagian besar AS. N'est-ce pas?
A. Rex
2
Ya itu. Yang ingin saya dapatkan adalah bahwa A * dapat digunakan sebagai gantinya dan selalu menemukan solusi optimal (meskipun menggunakan heuristik)!
Konrad Rudolph
Ya tentu saja. Setelah saya menulis posting asli saya, saya berpikir tentang kata "heuristik" yang saya gunakan. Agak tidak akurat di sini, karena tidak menemukan solusi optimal.
A. Rex
2
Nah, intinya adalah bahwa A * menggunakan heuristik (sebagai lawan menjadi satu) untuk menentukan langkah berikutnya. Keputusan yang satu ini memang bisa menjadi suboptimal. Tapi itu hanya mempengaruhi runtime, bukan hasilnya, karena itu hanya menentukan seberapa jauh lebih baik daripada yang diperkirakan Dijstra.
Konrad Rudolph
8

Keadaan saat ini dalam hal waktu kueri untuk jaringan jalan statis adalah algoritma pelabelan Hub yang diusulkan oleh Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Survei lapangan melalui dan ditulis dengan sangat baik baru-baru ini diterbitkan sebagai laporan teknis Microsoft http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

Versi singkatnya adalah ...

Algoritma pelabelan Hub menyediakan kueri tercepat untuk jaringan jalan statis tetapi membutuhkan banyak ram untuk dijalankan (18 GiB).

Routing node transit sedikit lebih lambat, meskipun, hanya membutuhkan sekitar 2 GiB memori dan memiliki waktu preprocessing yang lebih cepat.

Hierarki Kontraksi memberikan trade off yang bagus antara waktu preprocessing cepat, persyaratan ruang rendah (0,4 GiB) dan waktu kueri cepat.

Tidak ada satu pun algoritma yang sepenuhnya mendominasi ...

Pembicaraan teknologi Google ini oleh Peter Sanders mungkin menarik

https://www.youtube.com/watch?v=-0ErpE8tQbw

Pembicaraan ini juga dilakukan oleh Andrew Goldberg

https://www.youtube.com/watch?v=WPrkc78XLhw

Implementasi open source dari hierarki kontraksi tersedia dari situs web grup riset Peter Sanders di KIT. http://algo2.iti.kit.edu/english/routeplanning.php

Juga posting blog yang mudah diakses yang ditulis oleh Microsoft tentang penggunaan algoritma CRP di sana ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

Barnaby Hussey-Yeo
sumber
7

Saya sedikit terkejut tidak melihat algoritma Floyd Warshall yang disebutkan di sini. Algoritma ini bekerja sangat mirip dengan Dijkstra. Ini juga memiliki satu fitur yang sangat bagus yang memungkinkan Anda untuk menghitung selama Anda ingin terus mengizinkan lebih banyak simpul menengah. Jadi secara alami akan menemukan rute yang menggunakan antar negara bagian atau jalan raya cukup cepat.

dennisjtaylor
sumber
6

Saya sudah melakukan ini cukup banyak, sebenarnya, mencoba beberapa metode berbeda. Bergantung pada ukuran (geografis) peta, Anda mungkin ingin mempertimbangkan untuk menggunakan fungsi haversine sebagai heuristik.

Solusi terbaik yang saya buat adalah menggunakan A * dengan jarak garis lurus sebagai fungsi heuristik. Tetapi kemudian Anda membutuhkan semacam koordinat untuk setiap titik (persimpangan atau titik) pada peta. Anda juga dapat mencoba bobot yang berbeda untuk fungsi heuristik, yaitu

f(n) = k*h(n) + g(n)

di mana k adalah konstanta lebih besar dari 0.

Pål GD
sumber
4

Mungkin mirip dengan jawaban pada rute yang telah dihitung sebelumnya antara lokasi utama dan peta berlapis, tetapi pemahaman saya adalah bahwa dalam permainan, untuk mempercepat A *, Anda memiliki peta yang sangat kasar untuk navigasi makro, dan peta berbutir halus untuk navigasi ke batas arah makro. Jadi Anda memiliki 2 jalur kecil untuk dihitung, dan karenanya ruang pencarian Anda jauh lebih kecil daripada hanya melakukan satu jalur ke tujuan. Dan jika Anda dalam bisnis melakukan ini banyak, Anda akan memiliki banyak data yang pra-komputasi sehingga setidaknya bagian dari pencarian adalah pencarian untuk data yang dihitung sebelumnya, daripada pencarian jalur.

Marcin
sumber
3

Ini adalah spekulasi murni di pihak saya, tapi saya kira mereka mungkin menggunakan struktur data peta pengaruh yang menutupi peta yang diarahkan untuk mempersempit domain pencarian. Ini akan memungkinkan algoritma pencarian untuk mengarahkan jalur ke rute utama ketika perjalanan yang diinginkan panjang.

Mengingat ini adalah aplikasi Google, masuk akal juga untuk menganggap bahwa banyak keajaiban dilakukan melalui caching yang luas. :) Saya tidak akan terkejut jika caching 5% permintaan rute Google Map paling umum diizinkan untuk sebagian besar (20%? 50%?) Permintaan dijawab oleh pencarian sederhana.

Parappa
sumber
Apakah Anda memiliki referensi yang baik untuk "struktur data peta pengaruh"? Terima kasih!
A. Rex
3

Saya punya beberapa pemikiran tentang ini:

1) Ingat bahwa peta mewakili organisasi fisik. Simpan lintang / bujur dari setiap persimpangan. Anda tidak perlu memeriksa banyak hal di luar titik yang terletak pada arah target Anda. Hanya jika Anda menemukan diri Anda diblokir, Anda perlu melampaui ini. Jika Anda menyimpan overlay koneksi superior, Anda dapat membatasi lebih banyak lagi - Anda biasanya tidak akan pernah menemukan satu pun dari mereka dengan cara yang jauh dari tujuan akhir Anda.

2) Membagi dunia menjadi sejumlah besar zona yang ditentukan oleh konektivitas terbatas, menentukan semua titik konektivitas antara zona. Temukan zona di mana sumber dan target Anda berada, untuk rute awal dan akhir zona dari lokasi Anda ke setiap titik koneksi, untuk zona antara hanya memetakan antara titik koneksi. (Saya menduga banyak yang terakhir sudah dihitung sebelumnya.)

Perhatikan bahwa zona bisa lebih kecil dari area metropolitan. Setiap kota dengan fitur medan yang membaginya (katakanlah, sungai) akan menjadi beberapa zona.

Loren Pechtel
sumber
3

Saya sangat ingin tahu tentang heuristik yang digunakan, ketika beberapa waktu lalu kami mendapat rute dari lokasi awal yang sama di dekat Santa Rosa, ke dua perkemahan berbeda di Taman Nasional Yosemite. Destinasi yang berbeda ini menghasilkan rute yang sangat berbeda (via I-580 atau CA-12) meskipun kedua rute tersebut bertemu untuk 100 mil terakhir (sepanjang CA-120) sebelum menyimpang lagi beberapa mil di ujungnya. Ini cukup berulang. Dua rute terpisah hingga 50 mil untuk sekitar 100 mil, tetapi jarak / waktu yang cukup dekat satu sama lain seperti yang Anda harapkan.

Sayangnya saya tidak dapat mereproduksi itu - algoritme pasti telah berubah. Tapi itu membuat saya penasaran dengan algoritma. Yang dapat saya berspekulasi adalah bahwa ada beberapa pemangkasan terarah yang kebetulan sangat sensitif terhadap perbedaan sudut kecil antara tujuan yang terlihat dari jauh, atau ada segmen precomputed berbeda yang dipilih oleh pilihan tujuan akhir.

Zhahai
sumber
3

Berbicara tentang GraphHopper , perencana rute Open Source cepat berdasarkan OpenStreetMap, saya telah membaca sedikit literatur dan mengimplementasikan beberapa metode. Solusi paling sederhana adalah Dijkstra dan peningkatan sederhana adalah Dijkstra dua arah yang mengeksplorasi kira-kira hanya setengah dari simpul. Dengan Dijkstra dua arah rute melalui seluruh Jerman sudah 1sec (untuk mode mobil), di C mungkin hanya 0,5s atau lebih;)

Saya telah membuat gif animasi pencarian jalur sungguhan dengan Dijkstra dua arah di sini . Juga ada beberapa ide untuk membuat Dijkstra lebih cepat seperti melakukan A *, yang merupakan "Dijkstra yang berorientasi pada tujuan". Saya juga sudah membuat animasi gif untuknya.

Tapi bagaimana cara melakukannya (banyak) lebih cepat?

Masalahnya adalah bahwa untuk pencarian jalur semua node antara lokasi harus dieksplorasi dan ini benar-benar mahal karena sudah di Jerman ada beberapa juta dari mereka. Tetapi titik sakit tambahan Dijkstra dll adalah bahwa pencarian tersebut menggunakan banyak RAM.

Ada solusi heuristik tetapi juga solusi tepat yang mengatur grafik (jaringan jalan) dalam lapisan hierarkis, keduanya memiliki pro & kontra dan terutama memecahkan masalah kecepatan dan RAM. Saya telah mendaftarkan beberapa dari mereka dalam jawaban ini .

Untuk GraphHopper saya memutuskan untuk menggunakan Hierarki Kontraksi karena relatif 'mudah' untuk diterapkan dan tidak memakan waktu lama untuk persiapan grafik. Itu masih menghasilkan waktu respons yang sangat cepat seperti Anda dapat menguji di GraphHopper Maps contoh online kami . Misalnya dari Afrika Selatan ke Cina Timur yang menghasilkan jarak 23.000 km dan hampir 14 hari waktu mengemudi untuk mobil dan hanya mengambil 0,1 detik di server.

Karussell
sumber
Bidirectional Dijkstra menggunakan Landmark untuk melakukan pencarian yang diarahkan pada tujuan lebih efisien daripada Bidirectional Dijkstra saja. Lihat www14.informatik.tu-muenchen.de/lehre/2010SS/sarntal/... Namun makalah ini tidak cukup detail untuk menghitung fungsi potensial, yang sedikit rumit, atau pilih tengara.
Paul Chernoch
2

Saya telah bekerja pada perutean selama beberapa tahun, dengan ledakan aktivitas baru-baru ini didorong oleh kebutuhan klien saya, dan saya telah menemukan bahwa A * cukup mudah cepat; benar-benar tidak perlu mencari optimasi atau algoritma yang lebih kompleks. Routing melalui grafik yang sangat besar bukanlah masalah.

Tetapi kecepatan tergantung pada memiliki seluruh jaringan perutean, yang saya maksud adalah grafik arcs dan node yang masing-masing mewakili segmen rute dan persimpangan, dalam memori. Waktu overhead utama adalah waktu yang diperlukan untuk membuat jaringan ini. Beberapa angka kasar berdasarkan pada laptop biasa yang menjalankan Windows, dan perutean di seluruh Spanyol: waktu yang dibutuhkan untuk membuat jaringan: 10-15 detik; waktu yang dibutuhkan untuk menghitung rute: terlalu pendek untuk diukur.

Hal penting lainnya adalah untuk dapat menggunakan kembali jaringan untuk sebanyak mungkin perhitungan rute yang Anda inginkan. Jika algoritme Anda telah menandai beberapa titik dengan beberapa cara untuk merekam rute terbaik (total biaya ke simpul saat ini, dan yang terbaik ke sana) - sebagaimana harus dalam A * - Anda harus mengatur ulang atau menghapus informasi lama ini. Daripada melalui ratusan ribu node, lebih mudah untuk menggunakan sistem nomor generasi. Tandai setiap node dengan nomor generasi datanya; menambah nomor pembangkitan saat Anda menghitung rute baru; setiap node dengan nomor generasi yang lebih tua adalah basi dan informasinya dapat diabaikan.

Graham Asher
sumber
1

Saya melihat ada apa dengan peta di OP:

Lihatlah rute dengan titik tengah yang ditentukan: Rute ini sedikit mundur karena jalan yang tidak lurus.

Jika algoritma mereka tidak akan mundur, itu tidak akan melihat rute yang lebih pendek.

Loren Pechtel
sumber
Ide yang menarik. Saya telah menambahkan pelanggaran lain di PPS saya ke OP. Silakan lihat dan lihat apakah Anda dapat melihat penjelasan di sana.
A. Rex
Zoom CARA pada titik A - satu klik dari maks. Perhatikan bagaimana rute tiga titik menuju barat, selatan, timur. Saya pikir kita sedang melihat algoritma yang tidak suka mundur kecuali itu perlu melalui chokepoint.
Loren Pechtel
Dalam contoh PPS saya, ubah alamat awal menjadi "10 Avenue de Flandre, 75019 Paris". Ini menghapus backtrack kecil yang Anda bicarakan tetapi masalahnya masih ada. Saya pikir masalah utama adalah bahwa hal itu benar-benar ingin tetap di Blvd utama ...
A. Rex
1
Saya rasa saya menemukannya dalam kasus ini: Lakukan dengan mobil dan timingnya masuk akal. Mungkin melihat jalan besar lebih cepat dan rute berjalan tidak mencekiknya.
Loren Pechtel
1
PS: Masalah awal juga masuk akal dengan standar ini, mungkin bukan mundur yang menyebabkannya.
Loren Pechtel
0

Algoritma jalur terpendek semua-pasangan akan menghitung jalur terpendek antara semua simpul dalam grafik. Ini akan memungkinkan jalur yang akan dihitung sebelumnya alih-alih membutuhkan jalur yang akan dihitung setiap kali seseorang ingin menemukan jalur terpendek antara sumber dan tujuan. Algoritma Floyd-Warshall adalah algoritma jalur terpendek semua-pasangan.

J. Michael Wuerth
sumber
-4

Peta tidak pernah mempertimbangkan seluruh peta. Dugaan saya adalah: - 1. Menurut lokasi Anda, mereka memuat tempat dan landmark di tempat itu. 2. Ketika Anda mencari tujuan, saat itulah mereka memuat bagian lain dari peta dan membuat grafik dari dua tempat dan kemudian menerapkan algoritma jalur terpendek.

Juga, ada teknik penting pemrograman dinamis yang saya duga digunakan dalam perhitungan jalur terpendek. Anda dapat merujuknya juga.

Yogesh kumar
sumber