Consider the following directed graph where S is the start and G is the goal, transition costs are on arcs, and h is the heuristic estimate of distance to the goal.

 

Apply Greedy Best First Search to find a path from S to G. Fill out the following table, showing the full contents of the priority queue at the start of each step (before a node is popped from the queue). Show the final path and cost in the last line of the table. Write the entries in this form: 

 

Apply A* to find a path from the S to G. For each step of the search, fill out the table as above. Identify the final path and cost in the last line of the table. 

 

h=1 D h = 2 5 5 h=8 B h = 0 G 5 7 5 A 3 h = 5 h=3