In che modo Google calcola la distanza / ora di viaggio

Si inizia utilizzando A * con intersezioni come nodi. Le unità GPS negli anni '90 avevano abbastanza memoria e potenza di elaborazione per farlo. Non è necessario memorizzare la distanza da ogni intersezione a tutte le altre intersezioni. Solo all'incrocio successivo.

A * utilizza l'euristica per evitare la ricerca di possibilità che non si presenteranno sul percorso più breve. Se stai guidando da New York a Los Angeles, non cercherà strade che attraversano la Florida. Sareste sorpresi di quanto funzioni in modo efficiente sui dati del mondo reale, anche solo usando la distanza delle mosche gialle come euristica.

Google ha apportato numerose modifiche proprietarie per migliorare la sua euristica per favorire gli interstatali e le principali arterie, prendere in considerazione il traffico, non prendere strane deviazioni per le strade laterali, ecc. Probabilmente effettuano anche una ricerca gerarchica per viaggi davvero lunghi, utilizzando diverse euristiche per i viaggi locali e interstatali, utilizzando fondamentalmente una ricerca per raggiungere l'interstatale, un'altra per raggiungere la città di destinazione utilizzando un database con solo intersezioni principali, quindi una ricerca locale per raggiungere l'hotel, allo stesso modo in cui un essere umano pianificherebbe un viaggio.

Per i singoli indirizzi, si interpola. 200 E. Main si trova all'intersezione tra 2nd e Main. 300 E. Main è all'incrocio tra 3 ° e Main. Quindi sai 250 E. Main è a metà strada tra. Non devi memorizzare ogni singola famiglia.

TL; DR: Sì, c'è qualcosa che ti manca .

Google sembra calcolare un vero percorso del tempo minimo in base alla stima dei tempi di viaggio su ogni segmento stradale nell'area. Il tempo per calcolare un percorso perfettamente ottimale tra due punti in una rete è lineare nel numero di spigoli della rete, quindi anche attraverso una fitta rete stradale è possibile calcolare un percorso ottimale abbastanza rapidamente. Secondo la mia esperienza, Google lo fa molto bene: sembrano davvero prendere in considerazione tutti i possibili percorsi e, a volte, calcolare percorsi su strade di superficie che poche persone avrebbero considerato.

Semplice. Google utilizza tecniche di divisione e conquista. Se fai lunghi viaggi, quasi sicuramente usi l'interstatale. A causa del loro uso comune nell'esecuzione di calcoli, molti di questi calcoli sono semplicemente ricerche. Qual è la distanza tra il Tennessee e la Florida? Calcola il percorso interstatale e cerca la rispettiva distanza tra questi due punti sull'interstatale.

Qualsiasi altra cosa è semplicemente una questione di calcolo della distanza più breve dal punto di partenza verso l'interstatale e più tardi dall'interstatale alla destinazione finale, che riduce un calcolo del viaggio potenzialmente da mille miglia in due viaggi da 10 miglia e una ricerca da tavolo.