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?
Decision tree
Can a tree decide the best path to take?
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?
Swipe through more Machine Learning concepts
Open Pocket Polymath