. Search 2 [23 Points]

Consider the following directed graph with edge costs as indicated next to the edge. There are three goal states G1, G2 and G3. In this part of the question, we will use A* search algorithm to find the optimal path from start State S to a Goal State. Note that A* works by creating a list called Frontier and selects the best possible node from Frontier to be moved to another list called Explored.

(a) A* Search [15 Points]

Fill out the table below to show the working of the algorithm, indicating, for each node in the Frontier list, a tuple [past cost, modified cost] where modified cost is used to justify the selection of node for Explored. In case two nodes have the same modified cost, choose the one that comes earlier in alphabetical order. Each Frontier row will be used for ONE node and the entry will look like say A(5, 7) where A is the node, 5 is the past cost and 7 is the modified cost. You may not need all the Frontier rows as there may not be as many nodes in the Frontier. Similarly, you may not need all the Rounds as the optimal path may be determined earlier.

The heuristic values for each node is given as follows: h(s)=5, h(A)=7, h(B)=3, h(C)=4, h(D)=6, h(E)=5, h(F)=6, h(G1) =h(G2)=h(G3)=0

Frontier (row 0) | S |Round 1|Round 2|Round 3|Round 4|Round 5|Round 6 | Round 7

Frontier (row 1) | | | | | | | |

Frontier (row 2) | | | | | | | |

Frontier (row 3) | | | | | | | |

Frontier (row 4) | | | | | | | |

Frontier (row 5) | | | | | | | |

Explored | | | | | | | |

(b) What is the optimal path from start State S to the selected Goal State? [2 points]

(c) What would be the BEST possible heuristic values of the nodes? Why? [3 points]

(d) If the heuristic value were chosen as in part (c), would the number of rounds in the example above be more or less or stay the same for the optimal path computation? Why? [3 points]

the optimal path may be determined earlier. 5 9 1 6 6 3 1 2 2 A B C D E 2 9 5 7 2 7 G1 G2 F G3 8 Frontier (row 0) | S Round 1 Round 2 Round 3 Round 4 Round 5 Round 6 Round 7 Frontier (row 1) || 1 1 1 1 Frontier (row 2) | | I | Frontier (row 3)|| 1 Frontier (row 4) | 1 I Frontier (row 5) | | 1 1 1 Explored 1 | the optimal path may be determined earlier. 5 9 1 6 6 3 1 2 2 A B C D E 2 9 5 7 2 7 G1 G2 F G3 8 Frontier (row 0) | S Round 1 Round 2 Round 3 Round 4 Round 5 Round 6 Round 7 Frontier (row 1) || 1 1 1 1 Frontier (row 2) | | I | Frontier (row 3)|| 1 Frontier (row 4) | 1 I Frontier (row 5) | | 1 1 1 Explored 1 |