Assume that a salesperson wants to visit 30 cities while minimizing the
total number of miles she must travel. She decides to design an algorithm to find
the optimal order in which cities must be visited to
• Minimize the number of kilometers traveled and
• Visit each city only once.
Assume that the computer has access to all the intercity distances, and that it can
calculate the total distance for an all-city route at the rate of 10,000,000 a second.
a) How long will it take to calculate the cost of all such routes and give the
best one? Give your answer in large units like weeks, months or years. I’ll
post some hints on this one and/or mention it in class.
b) If it does not seem like a feasible solution, suggest an alternative way of
coming up with a reasonable algorithm to find a good (not necessarily
optimal) route
Show your calculations!