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’
x
positional values and between theiry
positional values. - Return the sum of the
x
distance andy
distance 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_distance
edge_weight
- an invocation of
heuristic()
withneighbor
andtarget
as arguments (this estimates the distance betweenneighbor
andtarget
)
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!