This homework is to be completed on paper using pen/pencil and demonstrating all steps of the search process. This is not a programming assignment. You should upload a pdf file containing the scanned version of your solutions. Consider the Traveling Salesperson Problem for the following cities (nodes) and distances of roads (edges) connecting them. Our goal is to find a tour through all the cities starting from city ' A ' and ending at any other city. The salesperson does not need to return to A at the end of the trip. We want to find the optimal tour by using the A search algorithm. We formulate our search problem as follows: - A State is represented by a partial tour of the cities that starts from city A. For example, the start state is (A). By expanding the start state, we get two possible states (AB) and (AH). And when we expand the state (AB), we get the states (ABA), ( ABC),(ABH), and ( ABJ). Any tour in which a city is repeated is an invalid state (partial tour) and must be excluded from the search. So, (ABA) is not a valid state because is repeats the city A. - The cost of arriving at a state n,(g(n)), is the cost of traversing the partial tour in ' n '. So, g(A) is 0;g(AB) is 16,g(AH) is 18 , and g(ABC) is 26. - All successors of states (children nodes in the search tree) are those states that can be formed by adding one more city at the end of the tour that is directly reachable from the last city mentioned in the parent state's tour. - Heuristic function h1(n) is computed as follows: Take all the cities that are not included in the state at node n and include all the edges that connect these remaining cities. Find the minimum cost spanning tree (MCST) of this graph and then find the total cost of the edges included in the MCST. This total is the estimated cost of the reaching the goal state from the state at node n. - Heuristic function h2(n) is computed as follows: Take all the cities that are not included in the state at node n and include all the edges that connect these remaining cities. Find the minimum edge cost in this remaining graph, and multiply it with (k1) where k is the number of cities in this remaining tree. - The goal state is the tour that includes all the nine cities. 1. (15) Perform uniform cost search for the above problem formulation. Show the Open List until a node containing a four city partial tour is pulled out of the Open List. Each entry in the Open list contains the partial tour and its g(n) value. 2. (15) Perform A search for the above problem formulation using h1(n) as the heuristic function. Show the Open List until a node containing a four-city partial tour is pulled out from the Open List. Each entry in the Open list contains the partial tour and its f(n),g(n), and h1(n) values. Only for the two states of ' AB and ' AH show the remaining graph and its MCST. 3. (15) Perform A search for the above problem formulation using h2(n) as the heuristic function. Show the Open List until a node containing a four city partial tour is pulled out from the Open List. Each entry in the Open list contains the partial tour and its f(n),g(n), and h2(n) values. 4. (5) Are h1(n) and h2(n) admissible heuristic functions? Give reasons to justify your answers