Algorithms For Dummies

Using distance measures as heuristics

When you can’t solve real-life problems in a precise algorithmic way because their 

input is confused, missing, or unstable, using heuristics can help. When perform-

ing path finding using coordinates in a Cartesian plane (flat maps that rely on a 

set of horizontal and vertical coordinates), two simple measures can provide the 

distances  between  two  points  in  that  plane:  the  Euclidean  distance  and  the 

 Manhattan distance.

People commonly use the Euclidean distance because it derives from the Pythago-

rean  Theorem  on  triangles.  If  you  want  to  know  the  distance  in  line  of  sight 

between two points in a plane, say, A and B, and you know their coordinates, you 

can pretend they’re the extremes of the hypotenuse (the longest side in a trian-

gle). As depicted in Figure 20-1, you calculate distance based on the length of the 

other two sides by creating a third point, C, whose horizontal coordinate is derived 

from B and whose vertical coordinate is from A.

FIGURE 20-1: 

A and B are 

points on a map’s 

coordinates.

---

CHAPTER 20