Question 1

SEARCH\ A MoveGen for a state space where S is the start node and G is the goal node is shown in the table. The MoveGen function returns nodes in the order as shown in the table. Use DFS and BFS to find a path from S to G. Note: DFS and BFS inspect only new nodes. Figure from the original question paper SEARCH\ A MoveGen for a state space where S is the start node and G is the goal node is shown in the table. The MoveGen function returns nodes in the order as shown in the table. Use DFS and BFS to find a path from S to G. Note: DFS and BFS inspect only new nodes.\ What is the path found by DFS? Enter the path as a comma separated list.\ NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: S,X,Y,Z TSP BnB\ TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below.\ Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties. When required, use reference numbers in short answers.\ What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree. Figure from the passage in the original paper TSP BnB\ TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below.\ Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties. When required, use reference numbers in short answers.\ What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree. Determine the number of cities in the TSP instance. Enter the number of cities in the text box, or enter NIL if it is not possible to determine the number of cities.\ Enter an integer. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42 TSP BnB\ TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below.\ Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties. When required, use reference numbers in short answers.\ What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree. Figure from the passage in the original paper TSP BnB\ TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below.\ Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties. When required, use reference numbers in short answers.\ What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree. Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes (2nd to 5th node) that are refined by the TSP BnB algorithm. Enter the nodes (node reference numbers) in the order they are refined.\ Enter a comma separated list of node reference numbers. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: a9,b9,c9,d9