Algorithms For Dummies

  Considering Heuristics 

     377

This process translates into taking the difference between the horizontal and ver-

tical coordinates of your two points, squaring both the differences (so that they 

both become positive), sum them, and finally taking the square root of the result. 

In this example, going from A to B uses coordinates of (1,2) and (3,3):

sqrt((1-3)

2

 

+ (2-3)

2

) = sqrt(2

2

+1

2

) = sqrt(5) = 2.236

The Manhattan distance works differently. You begin by summing the lengths of 

the sides B and C, which equates summing the absolute value of the differences 

between the horizontal and vertical coordinates of the points A and B.

|(1-3)| 

+ |(2-3)| = 2 + 1 = 3

The  Euclidean  distance  marks  the  shortest  route,  and  the  Manhattan  distance 

provides the longest yet most plausible route if you expect obstacles when taking 

a direct route. In fact, the movement represents the trajectory of a taxi in Manhat-

tan (hence the name), moving along a city block to reach its destination (taking 

the  short  route  through  buildings  would  never  work).  Other  names  for  this 

approach are the city block distance or the taxicab distance. Consequently, if you 

have  to  move  from  A  to  B  but  you  don’t  know  whether  you’ll  find  obstacles 

between them, taking a detour through point C is a good heuristic because that’s 

the distance you expect at worst.