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.
Manhattan distance

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!

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?