Question 1

SEARCH\ The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.\ The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.\ Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties. Figure from the passage in the original paper SEARCH\ The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.\ The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.\ Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.\ Emulate A\*, WA\* and Branch-and-Bound on the given map, then answer the given subquestions. In the map, S is the first node to be refined, determine the next 4 nodes from the 2nd to 5th node refined by A\*. Enter the nodes in the order they are refined.\ Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: W,X,Y,Z SEARCH\ The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.\ The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.\ Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties. Figure from the passage in the original paper SEARCH\ The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.\ The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.\ Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.\ Emulate A\*, WA\* and Branch-and-Bound on the given map, then answer the given subquestions. For the 4 nodes listed in the **previous question**, list the f-values of those nodes as a comma separated list. Use the same node order used in the previous question.\ Enter a comma separated list of natural numbers. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 2,7,1,8 SEARCH\ The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.\ The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.\ Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties. Figure from the passage in the original paper SEARCH\ The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two way edges (roads), where each edge has a cost that is the same in both directions. Observe that the edge costs are not necessarily proportional to the coordinate based distance estimates.\ The start node is S and the goal node is G, the MoveGen function returns neighbours in alphabetical order. Use Manhattan distance as the heuristic function.\ Tie-breaker: when several nodes have the same best cost, use alphabetical order to break ties.\ Emulate A\*, WA\* and Branch-and-Bound on the given map, then answer the given subquestions. What is the path found by A\*?\ Enter the path as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: S,X,Y,Z,G