How do GPS systems find the best route when driving?
Image: NASA/Bill Stafford, James Blair, Regan Geeseman, Public domain, via Wikimedia Commons
the A* algorithm does: BFS with heuristic f(n) = g(n) + h(n)
How do GPS systems find the best route when driving?
Imagine you're stuck in traffic and need to get to work quickly. You want the fastest route, avoiding the congested roads.
Think of A* as a smart GPS that not only looks at the distance you've traveled (g(n)) but also estimates the distance to your destination (h(n)), combining them to find the quickest path.
Example
You drive 10 miles (g(n)) and there's a shortcut that saves 5 miles (h(n)), A* would choose it, saving you 5 miles in total.
Remember this
A* uses g(n) + h(n) to efficiently find the best route.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
Travelling salesman problem
Can we always find the shortest path visiting all cities?
BFS vs DFS: BFS finds shortest path in unweighted graphs, DFS uses less memory
BFS finds shortest path in unweighted graphs; DFS uses less memory
Dijkstra's algorithm
Dijkstra's algorithm time complexity: O((V+E) log V)
approximation algorithms guarantee: solution within factor α of optimal
Can we always find the best solution quickly?
Graph (abstract data type)
Time complexity of BFS and DFS: O(V + E)
Shor's algorithm
Shor's algorithm factors integers in polynomial time on a quantum computer
Swipe through 100 ML concepts daily
Open Pocket Polymath