1. Here is a map of a walkway system. You want to use A* search to tell you the best route from block S to the nearest goal block (G1 or G2assume they are a couple of coffee shops or something). Each block has a single-letter name, and a heuristic distance given in parentheses. Fill out the following table, as for the in class exercise, showing the final route to the nearer of goal nodes G1 and G2, and showing all the items in the queue at each stage of the algorithm. The distance of each edge (walkway) is 1. When two nodes are an equal f-value from the nearest goal, expand the node whose name comes first in the alphabet.

Here is a map of a walkway system. You want to use A* search to tell you the best route from block S to the nearest goal block (G1 or G2...assume they are a couple of coffee shops or something). Each block has a single-letter name, and a heuristic distance given in parentheses. Fill out the following table, as for the in class exercise, showing the final route to the nearer of goal nodes G1 and G2, and showing all the items in the queue at each stage of the algorithm. The distance of each edge (walkway) is 1. When two nodes are an equal f-value from the nearest goal, expand the node whose name comes first in the alphabet. A(4) B(3) C(2) D(1) - G1 E(5) F(4) UNDER CONST. H(2) UNDER CONST. UNDER CONST. (2) 1 J(1) K(1) L(3) M(3) N(2) UNDER CONST. G2 Solution: (leftmost column is vertex being expanded) (I did the first two lines for you) (head of queue) Priority Queue After Expanding Node (except for head of queue, order is irrelevant) ver. nf via nf via nf vianp via nf via nf via s 14 SE: 6 S M 5 SL E 6 S - - - - - Here is a map of a walkway system. You want to use A* search to tell you the best route from block S to the nearest goal block (G1 or G2...assume they are a couple of coffee shops or something). Each block has a single-letter name, and a heuristic distance given in parentheses. Fill out the following table, as for the in class exercise, showing the final route to the nearer of goal nodes G1 and G2, and showing all the items in the queue at each stage of the algorithm. The distance of each edge (walkway) is 1. When two nodes are an equal f-value from the nearest goal, expand the node whose name comes first in the alphabet. A(4) B(3) C(2) D(1) - G1 E(5) F(4) UNDER CONST. H(2) UNDER CONST. UNDER CONST. (2) 1 J(1) K(1) L(3) M(3) N(2) UNDER CONST. G2 Solution: (leftmost column is vertex being expanded) (I did the first two lines for you) (head of queue) Priority Queue After Expanding Node (except for head of queue, order is irrelevant) ver. nf via nf via nf vianp via nf via nf via s 14 SE: 6 S M 5 SL E 6 S