A salesperson wants to visit 25 cities while minimizing the total number of
miles she must 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 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 data that gives 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 this is a feasible algorithm? If it is
not, can you think of a way to obtain a reasonable solution to this problem?