W jaki sposób dostawcy map (tacy jak Google lub Yahoo! Maps) sugerują wskazówki dojazdu?
Mam na myśli, że prawdopodobnie mają rzeczywiste dane w jakiejś formie, z pewnością obejmujące odległości, ale może także takie rzeczy, jak prędkości jazdy, obecność chodników, rozkład jazdy pociągów itp. Załóżmy jednak, że dane były w prostszym formacie, powiedzmy na bardzo dużym ukierunkowanym wykresie z obciążnikami krawędzi odzwierciedlającymi odległości. Chcę być w stanie szybko obliczyć kierunki z jednego dowolnego punktu do drugiego. Czasami punkty te będą blisko siebie (w obrębie jednego miasta), a czasem będą daleko od siebie (biegowe).
Algorytmy wykresów, takie jak algorytm Dijkstry, nie będą działać, ponieważ wykres jest ogromny. Na szczęście algorytmy heurystyczne, takie jak A *, prawdopodobnie będą działać. Jednak nasze dane są bardzo ustrukturyzowane, a może może działać jakieś podejście warstwowe? (Na przykład przechowuj wstępnie obliczone kierunki między niektórymi „kluczowymi” punktami daleko od siebie, a także niektóre lokalne kierunki. Następnie wskazówki dla dwóch odległych punktów będą obejmować lokalne kierunki do kluczowych punktów, globalne kierunki do innego kluczowego punktu, a następnie lokalne wskazówki ponownie.)
Jakie algorytmy są faktycznie stosowane w praktyce?
PS. To pytanie było motywowane znalezieniem dziwactw w internetowych mapach. W przeciwieństwie do nierówności trójkąta, czasami Google Maps uważa, że XZ trwa dłużej i jest dalej niż przy użyciu punktu pośredniego, jak w XYZ . Ale może ich kierunki piesze zoptymalizują się również pod kątem innego parametru?
PPS. Oto kolejne naruszenie nierówności trójkąta, które sugeruje (dla mnie), że używają one pewnego rodzaju podejścia wielopoziomowego: XZ kontra XYZ . Ten pierwszy wydaje się wykorzystywać wybitny Boulevard de Sebastopol, chociaż jest nieco na uboczu.
Edycja : Żaden z tych przykładów nie wydaje się już działać, ale oba działały w momencie publikacji oryginalnego postu.