4. The traveling salesperson problem (TSP) can be solved by A* via the minimum spanning tree (MST) heuristic, which is used to estimate the cost of completing a tour given that a partial tour has already been constructed. The MST cost of a set of cities (the remaining/unvisited cities, plus the start-city, and the end-city of the partial tour) is the smallest sum of the link costs of any tree that connects all of these cities. a) (3 pts) What constraints of TSP have to be relaxed to derive the MST heuristic? b) (4 pts) Consider an alternative straight-line distance heuristic that simply connects back the end-city of the partial tour with the start-city via a straight line, leaving the remaining cities unvisited. Show that the MST heuristic dominates this straight-line distance heuristic