Can we always find the shortest path visiting all cities?
Travelling salesman problem
Can we always find the shortest path visiting all cities?
Imagine planning a road trip to visit several friends spread across different cities. You want to minimize driving time by finding the shortest route that visits each friend once and returns home.
Even though finding the absolute shortest route is tough, we can use smart shortcuts to get close to it. These shortcuts are called approximation algorithms.
Example
If the shortest route is 300 miles, an approximation algorithm might find a route that's 270 miles, which is still pretty close.
Remember this
Approximation algorithms help us quickly find nearly the best routes without spending endless time on calculations.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
approximation algorithms guarantee: solution within factor α of optimal
Can we always find the best solution quickly?
Proximal gradient methods for learning
Why can't we always find the best path in a maze?
the A* algorithm does: BFS with heuristic f(n) = g(n) + h(n)
How do GPS systems find the best route when driving?
the curse of dimensionality makes nearest neighbor search unreliable
Why can't we find our friends easily as we move to a city with more and more neighborhoods?
non-convex loss landscapes are hard: many local minima and saddle points
Why do some hills have more tricky paths than others?
Convex optimization
Convex functions have only one global minimum
Swipe through 100 ML concepts daily
Open Pocket Polymath