For the following 4-city TSP problems assume that the initial BSSF is infinite and that the city cost/distance matrix is 12 14 6 o0 This is the same as the previous homework and the initial state should start with the same reduced cost matrix that you did for the previous homework for both problems below Question 1 (5 points): Use the partial path state search approach we discussed in class. This assumes the path starts at city 1, each node represents a city, and a link from a parent to a child node in the search space means a path between the cities. Expanding a node means generating a child state for each node to which the parent node has a path. The state for the root of the search tree is the answer to the last homework. Show the search tree that branch and bound would generate for this problem. Show each state including the reduced cost matrix and bound. Also show when BSSF is updated and use it for proper pruning, etc. Question 2 (5 points): This time use the include/exclude state search approach we discussed in class. This does not assume a particular start city, and at each branch chooses one edge to include/exclude from the solution. At each branch, choose the edge which maximizes bound(Sexcluded) bound(Sincluded Show the search tree that branch and bound would generate for this problem. Show each state including the reduced cost matrix and bound. Also show when BSSF is updated and use it for proper pruning, etc. For the following 4-city TSP problems assume that the initial BSSF is infinite and that the city cost/distance matrix is 12 14 6 o0 This is the same as the previous homework and the initial state should start with the same reduced cost matrix that you did for the previous homework for both problems below Question 1 (5 points): Use the partial path state search approach we discussed in class. This assumes the path starts at city 1, each node represents a city, and a link from a parent to a child node in the search space means a path between the cities. Expanding a node means generating a child state for each node to which the parent node has a path. The state for the root of the search tree is the answer to the last homework. Show the search tree that branch and bound would generate for this problem. Show each state including the reduced cost matrix and bound. Also show when BSSF is updated and use it for proper pruning, etc. Question 2 (5 points): This time use the include/exclude state search approach we discussed in class. This does not assume a particular start city, and at each branch chooses one edge to include/exclude from the solution. At each branch, choose the edge which maximizes bound(Sexcluded) bound(Sincluded Show the search tree that branch and bound would generate for this problem. Show each state including the reduced cost matrix and bound. Also show when BSSF is updated and use it for proper pruning, etc