The Simple, Elegant Algorithm That Makes Google Maps Possible
Motherboard has a great piece on the math behind Google maps.
Algorithms are a science of cleverness. A natural manifestation of logical reasoning— mathematical induction, in particular—a good algorithm is like a fleeting, damning snapshot into the very soul of a problem. A jungle of properties and relationships becomes a simple recurrence relation, a single-line recursive step producing boundless chaos and complexity. And to see through deep complexity, it takes cleverness.
It was the programming pioneer Edsger W. Dijkstra that really figured this out, and his namesake algorithm remains one of the cleverest things in computer science. A relentless advocate of simplicity and elegance in mathematics, he more or less believed that every complicated problem had an accessible ground floor, a way in, and math was a tool to find it and exploit it.
In 1956, Dijkstra was working on the ARMAC, a parallel computing machine based at the Netherlands’ Mathematical Center. It was a successor to the ARRA and ARRA II machines, which had been essentially the country’s first computers. His job was programming the thing, and once ARMAC was ready for its first public unveiling—after two years of concerted effort—Dijkstra needed a problem to solve.
“For a demonstration for noncomputing people you have to have a problem statement that non-mathematicians can understand,” Dijkstra recalled in an interview not long before his 2002 death. “They even have to understand the answer. So I designed a program that would find the shortest route between two cities in the Netherlands, using a somewhat reduced road-map of the Netherlands, on which I had selected 64 cities.”
“What’s the shortest way to travel from Rotterdam to Groningen?,” Dijkstra said. “It is the algorithm for the shortest path, which I designed in about 20 minutes.”
Google Maps does this for us now and we don’t even really think about what a complex task it could be. Shortest path problems, a key feature of graph theory with a whole lot of pretty obvious real-world applications, get insanely deep very fast. The result is known (informally) as a combinatorial explosion, which is where the number of different combinations that must be explored in a given problem grows exponentially.
The result of such an explosion is that problems, like shortest path problems, grow so quickly as to become practically incomputable, taking a practically infinite amount of time to solve. It only takes a handful of nodes in a given map or graph for the number of possible combinations to push into the billions, requiring vast and unreasonable amounts of time.
The easiest way to explain Dijkstra’s algorithm is probably with an example. Take the graph below, where the numbers given are the weights of each connection. (A weight could be a simple distance or really any relative cost associated with traversing a particular connection that we’re seeking to minimize.) To start, we assign s, our starting position, the value 0. It takes 0 miles (or whatever) to get here because it’s the beginning position. Next, we look at the neighboring nodes of s, which we can imagine as a sort of frontier to be explored.
We are angry, frustrated, and in pain because of the violence and murder of Black people by the police because of racism. We are in the fight AGAINST RACISM. George Floyd was murdered, his life stolen. The Adafruit teams have specific actions we’ve done, are doing, and will do together as a company and culture. We are asking the Adafruit community to get involved and share what you are doing. The Adafruit teams will not settle for a hash tag, a Tweet, or an icon change. We will work on real change, and that requires real action and real work together. That is what we will do each day, each month, each year – we will hold ourselves accountable and publish our collective efforts, partnerships, activism, donations, openly and publicly. Our blog and social media platforms will be utilized in actionable ways. Join us and the anti-racist efforts working to end police brutality, reform the criminal justice system, and dismantle the many other forms of systemic racism at work in this country, read more @ adafruit.com/blacklivesmatter
Stop breadboarding and soldering – start making immediately! Adafruit’s Circuit Playground is jam-packed with LEDs, sensors, buttons, alligator clip pads and more. Build projects with Circuit Playground in a few minutes with the drag-and-drop MakeCode programming site, learn computer science using the CS Discoveries class on code.org, jump into CircuitPython to learn Python and hardware together, TinyGO, or even use the Arduino IDE. Circuit Playground Express is the newest and best Circuit Playground board, with support for CircuitPython, MakeCode, and Arduino. It has a powerful processor, 10 NeoPixels, mini speaker, InfraRed receive and transmit, two buttons, a switch, 14 alligator clip pads, and lots of sensors: capacitive touch, IR proximity, temperature, light, motion and sound. A whole wide world of electronics and coding is waiting for you, and it fits in the palm of your hand.