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 their
- Return the sum of the
Define a function
heuristic() with two parameters:
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
Create a variable
y_distance in the same way.
Return the sum of
y_distance from the function.
Time to add the heuristic into
a_star() so that distance is factored in!
Go to the line of
new_distance is defined. Set
new_distance equal to the sum of:
- an invocation of
targetas arguments (this estimates the distance between
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!