Google Maps' geheime Waffe: Wie Differential Heuristics die kürzeste Route in Echtzeit berechnen
2007 führte Google Maps eine revolutionäre Funktion ein: Das Ziehen von Start- und Zielpunkt berechnet die kürzeste Route in Echtzeit – dank einer damals wenig bekannten Optimierung des A*-Algorithmus. Red Blob Games erklärt in einem neuen interaktiven Leitfaden, wie Differential Heuristics funktionieren und warum sie die Karten-Exploration drastisch reduzieren. Nach über zehn Jahren Entwicklungszeit ist die Seite nun endlich veröffentlicht.
Ich brauchte es besser zu verstehen, also wechselte ich in den Lern- und Experimentiermodus.
- plomme
Sehr guter Artikel, wie immer, von Red Blob. Er hat meine Annahme auf hoher Ebene über die Wegesuche von Google Maps auf den Kopf gestellt. Ich dachte, in Erinnerung an den Algorithmus-Kurs, dass Google Maps so schnell arbeitet wegen der "optimalen Substruktur" der Suche nach dem kürzesten Weg. Das heißt, dass der kürzeste Weg von A nach C über B auch die kürzesten Wege von A nach B und B nach C erzeugt, und dass man für den Großteil eines gegebenen Weges durch eine Anzahl von vorberechneten "Zwischenpunkt"-Pfaden routen könnte. Das hier zu lesen stellt es in dem Sinne auf den Kopf, dass die Landmarken hinter dem Ziel liegen und nicht in der Mitte der Route! Sehr praktisches Werkzeug.
- simonw
Hier vor fünf Tagen diskutiert: https://news.ycombinator.com/item?id=49079995
(Ehrlich gesagt, das ist so ein cooles Stück Arbeit, dass es ein zweites Gespräch verdient, das dort hatte nur 40 Kommentare.)
- inigyou
Guter Artikel und gute Demonstrationen. Ich war ein wenig verwirrt über die Farben - zumindest einmal spricht der Text von blauen Kacheln, die diejenigen sind, die wegen der Landmarke nicht überprüft werden müssen, aber sie sind eigentlich grün, und die blauen sind diejenigen, die sowieso nicht überprüft wurden. Ich bin nicht farbenblind.
Viele deiner Karten bestehen aus Räumen, die an einigen Punkten verbunden sind. Hast du in Betracht gezogen, zuerst die Wegesuche durch den Graphen der Räume und dann durch jeden Raum einzeln durchzuführen? Man könnte sogar alle Pfade durch einen Raum von einem Portal zum anderen vorberechnen, aber das brauchst du wahrscheinlich nicht, aber du müsstest vorberechnen, wie kostspielig sie sind. Das ist wahrscheinlich ungefähr die gleichen Wegesuchkosten wie das Platzieren einer Landmarke in jedem Raum.