Learn

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 their y positional values.
• Return the sum of the x distance and y distance together. ### Instructions

1.

Define a function heuristic() with two parameters: start and target.

2.

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.

3.

Return the sum of x_distance and y_distance from the function.

4.

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() with neighbor and target as arguments (this estimates the distance between neighbor and target)
5.

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!