A salesperson wants to visit 25 cities while minimizing the total number of mile

Question

A salesperson wants to visit 25 cities while minimizing the total number of miles she has to drive. Because she has studied computer science, she decides to design an algorithm to determine the optimal order in which to visit the cities to (1) keep her driving distance to a minimum, and (2) visit each city exactly once. The algorithm that she has devised is the following:

The computer first lists all the possible ways to visit the 25 cities and then, for each one, determines the total mileage associated with that particular ordering. (Assume that the computer has access to a road map that provides the distances between all cities). After determining the total mileage for each possible trip, the computer searches for the ordering with the minimum mileage and prints out the list of cities on that optimal route, that is, the order in which the salesperson should visit her destinations.

If a computer could analyze 10,000,000 separate paths per second, how long would it take to determine the optimal route for visiting these 25 cities? On the basis of your answer, do you think that this is a feasible algorithm? If it is not, can you think of a way to obtain a reasonable solution to this problem? (Please remember to also answer the bolded question.)

**I KNOW THE ANSWER IS 1.551 x 1018 SECONDS, WHICH IS NOT FEASIBLE, SO I'M ONLY LOOKING FOR THE ANSWER TO THE BOLDED QUESTION!

Explanation / Answer

This problem is an instance of the "travelling salesman" problem. Since we know travelling salesman problem is NP-Hard, hence no polynomial time algorithm exists to solve it. In order to get a solution in feasible time, we need to find an approximate solution. One such method is mentioned below.

1. Mark any city as the starting city.
2. Construct a minimum spanning tree using the marked city as root. You can use prim's algorithm for this step.
3. Perform a preorder walk of the generated tree.

This method guarantees that the cost of the output produced is less than twice the best possible solution.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.