A* search
Not met yet
A* is Dijkstra's algorithm with a sense of direction. Each waiting tile goes on the heap with the minutes spent reaching it, g, plus an estimate of the minutes still to go, h, so the search takes the tile with the smallest g + h and leans towards the goal. On a grid where no step costs less than 1, the Manhattan distance, rows apart plus columns apart, never overestimates, and an estimate that never overestimates means the first time A* settles the goal, it has the quickest route. Put h second in the tuple so ties go to the tile nearer the goal.
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks A* takes whichever waiting tile is nearest the goal, ignoring what it cost to reach it.
- Thinks A* takes whichever waiting tile was cheapest to reach, as Dijkstra does, ignoring the estimate of what's left.
- Thinks any guess at the distance left will do for A*, even one that can be bigger than the real cost.
- Thinks the Manhattan distance is the straight-line distance between two tiles, rather than rows apart plus columns apart.
- Thinks A* can settle for a slower route than Dijkstra because it looks at fewer tiles.