The Concert Tour Problem - to find the
shortest route through each of "n" cities...
a.k.a. The Traveling Salesman Problem
The Exhaustive Search (probably 1000 times too conservative)
| Computational Effort | 30 Cities | 50 Cities | 75 Cities |
| (n-1)! / 2 paths | 4.42 e+30 paths | 3.04 e+62 paths | 1.65 e+107 paths |
| /
2 e+9 paths/second/one 2GHz desktop |
2.21 e+21 seconds | 1.52 e+53 seconds | 8.26 e+97 seconds |
| /
60 seconds/minute |
3.68 e+19 minutes | 2.53 e+51 minutes | 1.37 e+96 minutes |
| /
60 minutes/hour |
6.14 e+17 hours | 4.22 e+49 hours | 2.29 e+94 hours |
| /
24 hours/day |
2.55 e+16 days | 1.7 e+48 days | 9.57 e+92 days |
| /
365 days/year |
7.00 e+13 years | 4.82 e+45 years | 2.62 e+90 years |
| /
4.5 e+9 years/age-of-the-earth |
1.55 e+4 ages of the earth | 1.07 e+36 ages of the earth | 5.82 e+80 ages of the earth |
| /
2.55 e+0 age-of-the-(earth/universe) |
6.10 e+3 ages of the universe | 4.20 e+35 ages of the universe | 2.28 e+80 ages of the universe |
|
/ 10 e+30 |
4.20 e+5 sun's volume of computers, each computer one square inch for the age of the universe |
||
| /
10 e+78 atoms/universe |
22.85 e+0 universes with 1 computer per atom in the universe for the age of the universe | ||
| In "plain" English | It would take one 2GHz desktop computer 6,000 times the age of the Universe in order to consider each possible path. | It would take enough 2GHz desktop computers, each one cubic inch in volume, to fill 42,000 Suns, the age of the Universe in order to consider each possible path. | It would take 23 Universes full of 2GHz desktop computers, each the size of one atom, the age of the Universe in order to consider each possible path. |
Traveling Salesman Problem using Genetic
Algorithms
http://www.lalena.com/ai/tsp/