Travelling Salesman Problem

Imagine a salesman must start in Paris, and fly to 4 cities ( London, Berlin, Rome, and Athens). 
What is the shortest route he can take?  This is a famous problem which cannot be solved efficiently. 
The straightforward method is to examine all possible route, calculate the length of each trip,
and choose the smallest.  Here is the list of all of the 24 possible trips (he always starts and finishes in Paris):

P-L-B-R-A-P P-L-B-A-R-P P-L-R-A-B-P P-L-R-B-A-P P-L-A-R-B-P P-L-A-B-R-P

P-B-L-R-A-P P-B-L-A-R-P P-B-A-L-R-P P-B-A-R-L-P P-B-R-L-A-P P-B-R-A-L-P

P-R-A-L-B-P P-R-A-B-L-P P-R-B-L-A-P P-R-B-A-L-P P-R-L-B-A-P P-R-L-A-B-P

P-A-B-L-R-P P-A-B-R-L-P P-A-R-L-B-P P-A-R-B-L-P P-A-L-R-B-P P-A-L-B-R-P

Why are there 24 possibilities?  There are 4 choices for the first city, then 3 choices for the next,
then 2 choices for the next, then 1 choice left for the last city.  (The P's at beginning and end are fixed.)
So the number of possible trips is 4*3*2*1 = 4! (factorial) = 24

If the salesmen must visit 10 cities, there are 10! = 3,628,800 - over 3 million trips to examine.

The number of trips grows very fast as the number of cities grows.  

    The efficiency of the Travelling Salesman algorithm is  O( N ! )

The Travelling Salesman problem is an example of a problem desperately in need of a more efficient algorithm.
Although some clever programs have been written for this problem, the programs only guarantee
to get a good result, not necessarily the best result.  This remains an unsolved problem in Computer Science.

The following program prints all the trips for 5 cities (as shown above).

//=======================================================================\\

public class TravellingSalesman
{
   public TravellingSalesman()
   {
     String[] cities = {"Paris","London","Berlin","Rome","Athens"};
     int max = cities.length;
     int count = 0;
    
     for(int a = 1; a < max; a = a+1)
     {
       for(int b = 1; b < max; b = b+1)
       {
         for(int c = 1; c < max; c = c+1)
         {
           for(int d = 1; d < max; d = d+1)
           {
             if(a!=b && a!=c && a!=d && b!=c && b!=d && c!=d)
             {
               System.out.println(cities[0] + "-" + cities[a] + "-" + cities[b] + "-"
                         + cities[c] + "-" + cities[d] + "-" + cities[0]);
               count = count + 1;     
             }
           }
         }
       }
     }
     System.out.println(count + " different trips");
     double next = 10000000.0;
     double total = 0;
     for(double x=0; x < 10000000000.0; x=x+1)
     {
       total = total + x;
       if(x > next)
       { System.out.println(x);
         next = next + 10000000.0;
       }
     }
     System.out.println(total);
   }
  
   public static void main(String[] args)
   {  new TravellingSalesman(); }
}


/**********************************************************\

(1) Add one more city to the list, add one more loop,
    and change the if.. command so that the program
    prints all the trips for Paris+5 cities.
    This should print 120 different trips.
   
(2) Explain why it is basically impossible to SCALE
    this program to do 50 or 100 cities.
   
(3) Printing n! trips isn't even the worst part.
    The loops above require n^n iterations.
    So 10+1 cities require 10^10 iterations -
    that is 10 billion iterations.
    Write a simple loop that adds up the numbers
    1+2+3+...+10 billion.  You should use "double"
    variables for this program. How long does this
    program take to finish executing?
   
(4) Make a chart showing execution times from various numbers:

     N          N^N     Time counting to N^N
    ---   ----------  -----------------------
     1            1
     2            4
     3           27
     4          256
     5         3125
     6        46656
     7       823543
     8     16777216
     9    387420489
    10  10000000000
   
   Using this chart, and a calculator, make an ESTIMATE
   of how long it would take to count up to 20^20.  

\***********************************************************/