There are several kinds of heuristics out there that you can use to estimate distance, but we’ll start with the Manhattan heuristic. This heuristic is only considered admissible — meaning that it never overestimates the distance in reaching the target — in a grid system in which the search can only move up, down, left, or right.
To get the heuristic estimate, we need to:
- Measure the distance between the two vertices’
xpositional values and between theirypositional values. - Return the sum of the
xdistance andydistance together.
Instructions
Define a function heuristic() with two parameters: start and target.
In the function body, create a variable x_distance and set it equal to the absolute value of the target’s x value subtracted from start‘s x value.
Create a variable y_distance in the same way.
Return the sum of x_distance and y_distance from the function.
Time to add the heuristic into a_star() so that distance is factored in!
Go to the line of a_star() where new_distance is defined. Set new_distance equal to the sum of:
current_distanceedge_weight- an invocation of
heuristic()withneighborandtargetas arguments (this estimates the distance betweenneighborandtarget)
Congrats! You’ve implemented A* using the Manhattan heuristic.
Try calling the function on the graph provided find the best path from Penn Station to Grand Central Station in Manhattan!