Algorithms For Dummies

 

»

Find the shortest path solution every time: The algorithm can do this if 

such a path exists and if A* is properly informed by the heuristic estimate.  

A* is powered by the Dijkstra algorithm, which guarantees always finding the 

best solution.

 

»

Find the solution faster than any other algorithm: A* can do this if given 

access to a fair heuristic — one that provides the right directions to reach the 

target proximity in a similar, though even smarter, way as BFS.

 

»

Computes weights when traversing edges: Weights account for the cost of 

moving in a certain direction. For example, turning may take longer than going 

straight, as in the case of Shakey the robot.

A  proper,  fair,  admissible  heuristic  provides  useful  information  to  A*  about  the 

distance to the target by never overestimating the cost of reaching it. Moreover, 

A* makes greater use of its heuristic than BFS, therefore the heuristic must per-

form calculations quickly or the overall processing time will be too long.

The Python implementation in this example uses the same code and data struc-

tures used for BFS, but there are differences between them. The main differences 

are that as the algorithm proceeds, it updates the cost of reaching from the start 

vertex to each of the explored vertexes. In addition, when it decides on a route, A* 

considers the shortest path from the start to the target, passing by the current 

vertex, because it sums the estimate from the heuristic with the cost of the path 

computed  to  the  current  vertex.  This  process  allows  the  algorithm  to  perform 

more computations than BFS when the heuristic is a proper estimate and to deter-

mine the best path possible.

Finding  the  shortest  path  possible  in  cost  terms  is  the  core  Dijkstra  algorithm 

function. A* is simply a Dijkstra algorithm in which the cost of reaching a vertex 

is  enhanced  by  the  heuristic  of  the  expected  distance  to  the  target.  Chapter  9 

describes the Dijkstra algorithm in detail. Revisiting the Chapter 9 discussion will 

help you better understand how A* operates in leveraging heuristics.

---

386

 

   

  PART 5