> This also helps me remember whether the estimate must over- or under-estimate: Since Dijkstra is making the estimate "0", clearly the "admissible heuristic" criteria must be an under-estimation.
You're thinking too hard. :-) Just think of a map the same way a 10-year-old would.
Straight-line (Euclidean) distance is the most obvious heuristic on a map for estimating distance, and it's admissible.
Straight lines minimize distances i.e. they never overestimate. Which is enough to remind you that you want an underestimate.
> the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue
A much less obvious but much more fascinating (IMO) way to look at A* is that A* is actually Dijkstra but with a modified graph, where you adjust the heuristic delta between each edge's vertices to the edge's weight.
To remember the sign of the adjustment with this method, just imagine the next vertex getting super close to the destination, and then work out whether the weight needs to increase or decrease significantly in that case. (It needs to decrease, given you're getting closer to the destination.)
You're thinking too hard. :-) Just think of a map the same way a 10-year-old would.
Straight-line (Euclidean) distance is the most obvious heuristic on a map for estimating distance, and it's admissible.
Straight lines minimize distances i.e. they never overestimate. Which is enough to remind you that you want an underestimate.
> the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue
A much less obvious but much more fascinating (IMO) way to look at A* is that A* is actually Dijkstra but with a modified graph, where you adjust the heuristic delta between each edge's vertices to the edge's weight.
To remember the sign of the adjustment with this method, just imagine the next vertex getting super close to the destination, and then work out whether the weight needs to increase or decrease significantly in that case. (It needs to decrease, given you're getting closer to the destination.)