# Assignemnt 6

Due date: 2020-10-28, 23:59 IST.
The figure shows a map (repeated from Week 5) with several locations on a grid where each tile is 10km x 10 km in size. In this map, S is the start node and G is the goal node, the locations are connected by two-way edges (roads). Each edge has a cost and the cost is the same in both directions  For this map, MoveGen returns nodes in alphabetical order. When several nodes have the same cost, use alphabetical order to break ties. When the same node occurs multiple times with the same cost then use the open-sequence-number to break ties, i.e., pick up the node occurrence that is oldest (was placed earliest in time) in the OPEN list. Where needed, use Manhattan distance as the heuristic function. Simulate WA* with w=2, Breadth First Heuristic Search with U=312, Sparse-Memory Graph Search, and Beam Search with w=2 on the above map and answer the following questions BEGIN GROUP
1. For w=2, in f = g + w*h, simulate WA* algorithm on the given map. List the 3rd, 6th and 9th nodes inspected by the algorithm.

Enter node labels as a comma separated list. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc.
2. What are the f-values of the 3rd, 6th and 9th nodes listed in the previous question?

Enter the costs as a comma separated list of natural numbers. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc
3. For WA* with w=2,​ ​ what is the path found by the algorithm?

Enter the path (starting from S and ending in G) as a comma separated list of node labels. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc

4. What is the cost of the path found by WA* algorithm?

Enter a natural number
1 point