The Traveling Salesman Problem (TSP). All traveling sales- people start from their home, travel to several cities to sell their goods, and complete the day by returning home. To minimize their costs, traveling salespeople should visit all of the cities using the shortest total travel distance. This amounts to finding an order of all of the cities that minimizes the sum of the distances traveled when moving from one city to another. The following figure illustrates a small TSP and a feasible solution to that problem. The cities are labeled from 0 to 4. x2,y2=0.0,1.0 2 X3,Y3=1.0,1.0 3 2 3 x1,y1=0.0,0.5 1 1 cost = 5.2 xo-Yo=0.0,0.0 0 x4Y4=1.0,0.0 4 0 4 2 Assignment Write an algorithm to solve the knapsack problem. The problem is mathematically for- mulated in the following way. Given a list of locations N = 0,,n-1 and coordinates for each location (x, y) i N, let v; be a variable denoting the visit ation order, and let dist (11, 12) be the Euclidean distance between two locations. Then the traveling salesman problem is formalized as the following optimization problem, Minimize: dist(v, V+1) + dist (vn, vo) i0...n-1 Subject to: v, are a permutation of N v, are a permutation of N