Apakah algoritma Dijkstras digunakan dalam sistem pencarian rute modern?

10

Apakah algoritma Dijkstra digunakan dalam sistem pencarian rute modern seperti Google maps atau satnav di mobil Anda? Jika tidak, lalu apa?

algorithms graphs shortest-path applied-theory chopper draw lion4
sumber
Saya kira maksud Anda adalah komponen perutean yang menemukan jalan Anda, begitu GPS, yang terutama merupakan Global Positionning Syatem telah menentukan di mana Anda berada . Kasus lain dari ekor yang mengibas-ngibaskan anjing.
babou
1
Saya tidak bisa memberikan sumber untuk ini, tetapi dosen Algoritma saya saat ini bekerja di industri, dan mengatakan bahwa A∗ banyak digunakan dalam praktik, terutama untuk GPS. Jika Anda menggunakan Euclidean Distance sebagai heuristik, Anda cenderung untuk mendapatkan perbaikan atas Dijstra dengan mengabaikan jalur yang tidak masuk akal dalam kehidupan nyata. Anda mungkin sudah tahu, tetapi Dijkstra dapat digambarkan sebagai A∗ dengan heuristik h(x)=0 .
jmite

Jawaban:

8

Google Maps pada tahun 2009 menggunakan Hirarki Kontraksi - lihat pembicaraan teknologi ini .

Sejak itu, beberapa metode yang mengejutkan telah ditemukan, mampu melakukan rute lintas negara dalam milidetik pecahan - yang disebut "oracle jarak label dua-hop". Lihat di sini , atau cari "Pelabelan hub" atau "Jalur terpendek untuk massa". Saya pikir saya mendengar Bing menggunakan yang ini. Ini juga memiliki aplikasi seperti kemampuan untuk menemukan tempat menarik terdekat (misalnya pompa bensin terdekat) dengan kompleksitas independen pada jumlah pompa bensin.

Jkff
sumber
2
Ini sepertinya menjadi referensi yang bermanfaat. Namun, dapatkah Anda a) memberikan referensi yang dapat dicoba dan / atau b) melukis gambaran luas tentang cara kerjanya? Secara khusus, apakah mereka menyelesaikan masalah dengan tepat?
Raphael