Czy algorytm Dijkstras jest stosowany w nowoczesnych systemach wyszukiwania tras?

10

Czy algorytm Dijkstry jest wykorzystywany w nowoczesnych systemach wyszukiwania tras, takich jak mapy Google czy satnav w samochodzie? Jeśli nie, to czym jest?

algorithms graphs shortest-path applied-theory chopper draw lion4
źródło
Wydaje mi się, że masz na myśli element trasy, który odnajdzie twoją drogę, gdy GPS, który jest przede wszystkim globalnym systemem pozycjonowania , ustali, gdzie jesteś . Kolejny przypadek ogona machającego psem.
babou
1
Nie mogę podać źródła tego, ale mój obecny wykładowca algorytmów pracuje w branży i tak mówi ZA∗jest często stosowany w praktyce, szczególnie w GPS. Jeśli używasz odległości euklidesowej jako heurystyki, masz tendencję do uzyskiwania ulepszeń w stosunku do Dijstry, ignorując ścieżki, które w życiu są nonsensowne. Być może już wiesz, ale Dijkstry można opisać jakoZA∗ z heurystyką h(x)=0.
jmite

Odpowiedzi:

8

Mapy Google w 2009 roku korzystały z hierarchii skurczów - zobacz ten wykład techniczny .

Od tego czasu odkryto pewne oszałamiające metody, zdolne do trasowania między krajami w ułamkach milisekund - tak zwane „wyrocznie z oznaczeniem dwóch przeskoków”. Zobacz tutaj lub wyszukaj „Etykietowanie piasty” lub „Najkrótsze ścieżki dla mas”. Chyba słyszałem, że Bing używa tego. Ma również zastosowania, takie jak możliwość znalezienia najbliższego interesującego miejsca (np. Najbliższej stacji benzynowej) o złożoności niezależnej od liczby stacji benzynowych.

jkff
źródło
2
To wydają się przydatne odniesienia. Czy możesz jednak: a) podać cytowane odniesienia i / lub b) namalować szeroki obraz tego, jak one działają? W szczególności, czy dokładnie rozwiązują problem?
Raphael