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

END GROUP

BEGIN GROUP

Simulate the Breadth First Heuristic Search (BFHS) with U=312 on the given map.
Remember that the MoveGen function generates nodes in alphabetic order and that
the algorithm does not add nodes that are in OPEN or CLOSED to OPEN.

Assume f = g + h, where g is the actual-cost of the path generated by BFHS (not by
A*), and h is the heuristic value. Prune the new nodes if f-value is greater than or
equal to U. Prune the nodes before placing them in OPEN list.

5. List the 5th, 8th, 11th and 14th nodes visited by BFHS.

Enter the node labels as a comma separated list. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc.

1 point

6. What are the costs of the 5th, 8th, 11th and 14th 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

1 point

END GROUP

BEGIN GROUP

For the following questions assume that the Sparse-Memory Graph Search (SMGS)
has enough memory to only hold 4 nodes in Kernel. We will not count S to be part of
the Kernel (because it is never deleted).

In this group, enter ALL node-lists in ALPHABETIC order.

7. List the nodes in OPEN after SMGS has inspected 4 nodes starting with S,
where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

1 point

8. List the nodes in the BOUNDARY after SMGS has inspected 4 nodes starting
with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

1 point

9. List the nodes in the KERNEL after SMGS has inspected 4 nodes starting
with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc.

1 point

10. List the nodes in OPEN after SMGS has inspected 8 nodes starting with S,
where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc.

1 point

11. List the nodes in the BOUNDARY after SMGS has inspected 8 nodes starting
with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

1 point

12. List the nodes in the KERNEL after SMGS has inspected 8 nodes starting
with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

1 point

13. List the nodes in OPEN after SMGS has inspected 12 nodes starting with S,
where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

1 point

14. List the nodes in the BOUNDARY after SMGS has inspected 12 nodes
starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

1 point

15. List the nodes in the KERNEL after SMGS has inspected 12 nodes starting
with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a
comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

1 point

END GROUP

BEGIN GROUP

Simulate the Beam Search (with f-values) with beam width w=2. This means the best
two nodes are retained at each level irrespective of whether they are better than their
parents or not.

16 What is the path found by Beam Search?

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

1 point

17. What is the cost of the path found in the previous question?

Enter a natural number.

1 point

18. What is the other node in the beam (apart from G) at the point when the
algorithm terminates?

1 point

19. What is the cost of the node found in the previous question?

Enter a natural number.

1 point

END GROUP

1 point

20. When the Monotone Condition is satisfied we sometimes force the search to
“never leak” back because

You may submit any number of times before the due date. The final submission will be considered for grading.