Навигацийн аппликейшн нь олон сая огтлолцол бүхий замын сүлжээнд хамгийн богино замыг хэдхэн микросекундэд тооцоолдог технологийн шийдлийг ашигладаг.
Google Maps-ийн маршрут тогтоох суурь нь 1956 онд Нидерландын компьютерийн эрдэмтэн Эдсгер Дийкстрагийн боловсруулсан алгоритм юм. Энэхүү математик аргачлал нь эхлэх цэгээс очих цэг хүртэлх замын өртгийг тооцоолж, хамгийн бага зардалтай хувилбарыг сонгодог зарчмаар ажилладаг. Гэсэн хэдий ч орчин үеийн замын сүлжээний нарийн төвөгтэй байдал, олон сая хэрэглэгчийн хүсэлтийг боловсруулахад энэхүү хуучны алгоритм дангаараа хангалтгүй болжээ.
Үр ашгийг нэмэгдүүлэхийн тулд A* алгоритм зэрэг дэвшилтэт аргуудыг ашигладаг бөгөөд энэ нь очих цэгийн чиглэлийг баримжаалан хайлтын талбарыг хязгаарладаг. Мөн замын сүлжээний шатлалыг ашиглан чухал зангилаануудыг математик товчлолоор холбох “Customizable Contraction Hierarchy” техникийг хэрэглэдэг. Энэхүү арга нь шаардлагагүй жижиг замуудыг алгасан, гол магистраль замуудад анхаарлаа төвлөрүүлснээр маршрут тооцоолох хурдыг 35,000 дахин нэмэгдүүлж, 200 микросекундэд хариу өгөх боломжтой болжээ.
Хэдийгээр Google Maps-ийн ашигладаг ягштай технологийн нууц олон нийтэд нээлттэй биш ч, эдгээр математик шийдлүүд нь навигацийн аппликейшний арын албанд хэрхэн хэрэгжиж байгааг илтгэдэг. Энэ нь хэрэглэгчдийн гар утсан дээр харагдах энгийн цэнхэр зураасны цаана олон арван жилийн компьютерийн шинжлэх ухааны дэвшилтэт тооцоолол явагддагийг харуулж байна.
Дэлгэрэнгүйг эх сурвалжаас харах
↓Эх сурвалжийг нээх ↓
Have you ever wondered how Google Maps’ algorithm finds you the fastest route in just seconds?
There are more than 64 million intersections across North America’s road network, creating an almost unfathomable number of possible routes.
Checking every single one would take longer than you could possibly imagine, yet navigation apps can calculate a route almost instantly.
The secret comes down to decades-old math, clever shortcuts, and some seriously smart algorithms.
Google Maps’ algorithm started with a 20-minute idea
The car navigation app story starts in 1956 with Dutch computer scientist Edsger Dijkstra, who was looking for a mathematical way to demonstrate the power of an early computer called ARMAC.
During a shopping trip in Amsterdam, Dijkstra came up with a problem that ordinary people could understand: finding the shortest route between Rotterdam and Groningen.
His solution became known as Dijkstra’s algorithm, and the basic concept was remarkably straightforward.
Rather than checking every possible journey, the mathematical algorithm assigned a cost to each location based on the shortest route discovered so far.
It started with a cost of zero at the starting point and then explored nearby locations, always moving to the one with the lowest known cost, and if it found a shorter way to reach somewhere, it updated the cost and continued.
This guaranteed that it would eventually find the shortest route without having to test every possible combination.
The algorithm was reportedly designed in around 20 minutes and went on to become one of the most important algorithms in computer science.
But there was a problem, but while Dijkstra’s algorithm was incredibly fast for its time, it wasn’t fast enough to deal with modern road networks and millions of simultaneous navigation requests.
The fastest route comes from making the map smaller
One improvement is A*, which adds a clever shortcut that estimates how close each location is to the destination.
Instead of spreading out in every direction, the algorithm can prioritize locations that appear to be heading toward the target, which dramatically reduces the amount of the map it needs to explore.
But road networks have another major advantage: they have a natural hierarchy.
If you’re driving across the country, whether you use Google Maps or not, you’re probably going to use small roads to reach a major highway, stay on that highway for most of the journey and then return to local roads near your destination.
A technique called a customizable contraction hierarchy takes advantage of exactly this.
The system ranks intersections according to how important they are to the wider network like a major interchange connecting multiple highways is extremely important, while an intersection at the end of a quiet cul-de-sac isn’t.
It can then create mathematical ‘shortcuts’ between important points because these aren’t real roads, but they allow the algorithm to skip over huge sections of the network while still preserving the information needed to find the correct route.
In a test featured in this video by Veritasium, this approach calculated a route across North America in around 200 microseconds, or just 0.0002 seconds.
That’s around 35,000 times faster than Dijkstra’s algorithm in the same experiment, while examining roughly 1,450 nodes instead of potentially millions.
The exact technology used by Google Maps isn’t public, so there’s no guarantee it uses this precise algorithm, but we can be pretty sure.
But the demonstration gives an inside glimpse at what’s happening behind that little blue line on your phone when you look up where the closest Walmart is.
What looks like a simple route is actually decades of computer science, enormous amounts of processing and some shortcuts – all happening before you’ve even had time to wonder why Google wants you to take that weird back road behind the deli.
Dig deeper into the Google Maps vs. Waze vs. Apple Maps debate
These three related stories take a closer look at the features and real-world differences between Google Maps, Waze, and Apple Maps — helping you decide which navigation app deserves a place on your phone.
A journalistspent an entire month using both navigation apps across his daily commute and weekend road trips, putting them through traffic, unfamiliar roads and plenty of tricky turns.
In yet another addition to the ongoing navigation app rivalry saga, Google Maps has brought in a huge update that’s apparently blown its competition out of the water.
This software writer drew direct comparisons between thetwo navigation apps, trying to keep things as ‘scientific’ as possible.
