+16 A computer program takes 0.0085 seconds to calculate the best route between seven cities using a brute-force approach to the traveling salesman problem. How long, to the nearest second, will it take to calculate the best route for eleven cities?
+298 hint: brute force means every possible route was calculated. So, figure out how many routes are possible with seven cities, divide the time by that, and that gives you how much time it takes to calculate a single route with 7 cities.
divide the time for an individual route by 7 and that tells you how much time it takes to evaluate an individual route per 1 city.
Multiply that by 11, you get the time it takes to measure an 11 city route.
With that, all you need is the number of routes in 11 cities, multiply that by the time to calculate each route, and you're good.
+2440 Solution:
The Traveling Salesman Problem (TSP) is not NP-complete. It is not solvable, nor is its solution verifiable in polynomial time. The time complexity for brute force analysis is O(n!).
\({}\)
For this question, a close approximation for brute force analysis time is \( \dfrac {(11-1)!} { (7-1)!}* (8.5E-3) = 42.85 \text { seconds.} \)
For comparison, if there were (21) cities then the computation time would exceed (910,761) years.
Here is an animated graphic giving a visual representation for the analysis of a seven-city TSP.
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computing_a_solution
The Wiki article also gives a comprehensive overview for the Traveling Salesman Problem.
GA
