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.)

Explanation / Answer

As per given tere are 25 cities whoch are need to be visited,So that we have 25! possible paths need to be considered.
25! = 1.551121 x 1025 paths.
And also given that computer can analyze 10,000,000 (107) paths per second.
Hence it will take 1.551121 x 1025/107
= 1.551121 x 1018 seconds.
Almost 50 billion years. So that any algorithem is not feasible for this much time.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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