Algorithms For Dummies

  Considering Heuristics 

     387

print ('\nBest path is:', reconstruct_path(

        path, start, goal))

print ('Length of path: %i' % compute_path_dist(

        reconstruct_path(path, start, goal), graph))

Processing vertex A, discovered ['F', 'G']

Processing vertex F, discovered ['B', 'K']

Processing vertex G, discovered  ['H']

Processing vertex K, discovered  ['Q', 'P']

Processing vertex H, discovered  ['D']

Processing vertex B, discovered  ['C']

Processing vertex P, discovered  ['L', 'U', 'V']

Processing vertex Q, discovered  ['M', 'W']

Processing vertex C, getting back to open list

Processing vertex U, getting back to open list

Processing vertex D, discovered  ['E', 'J']

Processing vertex V, getting back to open list

Processing vertex L, getting back to open list

Processing vertex W, discovered  ['X']

Processing vertex E, getting back to open list

Processing vertex M, discovered  ['R']

Processing vertex J, discovered  ['O', 'I', 'N']

Processing vertex X, discovered ['T', 'Y']

Processing vertex R, getting back to open list

Processing vertex O, getting back to open list

Processing vertex I, getting back to open list

Arrived at final vertex Y

Unvisited vertices: 3

Best path is: ['A', 'F', 'K', 'Q', 'W', 'X', 'Y']

Length of path: 14

When  the  A*  has  completed  analyzing  the  maze,  it  outputs  a  best  path  that’s 

much shorter than the BFS solution. This solution comes at a cost: A* explores 

almost all the present vertexes, leaving just three vertexes unconsidered. As with 

Dijkstra, its worst running time is O(v

2

), where v is the number of vertexes in the 

graph;  or  O(e  +  v*log(v)),  where  e  is  the  number  of  edges,  when  using  min- 

priority queues, an efficient data structure when you need to obtain the minimum 

value for a long list. The A* algorithm is not different in its worst running time 

than Dijkstra’s, though on average, it performs better on large graphs because it 

first finds the target vertex when correctly guided by the heuristic measurement 

(in the case of a routing robot, the Manhattan distance).

---

---