looking for detailed version of traveling salesman problem

[conan19870619]

it's classic traveling salesman problem using dynamic programming.
the peseudocode is given :
Inputs: a weighted, directed graph, and n, the number of vertices in the graph. The graph is represented by a two-dimensional array W, which has both its rows and columns indexed from 1 to n, where W [j] is the weight on the edge from ith vertex to the jth vertex.

Outputs: a variable minlength, whose value is the length of an optimal tour, and a two-dimensional array P from which an optimal tour can be constructed. P has its rows indexed from 1 to n and its columns indexed by all subsets of V − {v1}. P [A] is the index of the first vertex after vi on a shortest path from vi to v1 that passes through all the vertices in A exactly once.

void travel (int n,
                           const number W [] [],
                           index P [] [],
                           number & minlength)
{
   index i, j, k;
   number D [1 .. n] [subset of V - {v1}];

   for (i = 2; i <= n; i++)
          D [i] [⊘] = W[i] [1];
   for (k = 1; k <= n - 2; k++)
                for (all subsets A ⊆ V - {v1} containing k vertices)
                          for (i such that i ≠ 1 and vi is not in A){
                            D [i] [A] = minimum (W [i] [j] + D [j] [A - {vj}]);
                                      j: [vj ∊ A
                            P[i] [A] = value of j that gave the minimum;
          }
     D [1] [V - {v1}] = minimum (W[1] [j] + D[j] [V - {v1, vj}]);
                   2 ≤ j ≤ n
    P[1] [V - {v1}] = value of j that gave the minimum;
    minlength = D[1] [V - {v1}];
}

i've been thinking lots of ways of implementing this code. turnes out they r just not working.
specially the part of using A to express the subsets and put it into D[A].
it's been bothering me for quite a few days and i'll so appreciate if anyone can help.

[WaltP]

The statement "they r just not working" tells us nothing. You need to tell us what the code is doing, and what it is supposed to be doing instead, as the post titled Read Me: Read This Before Posting suggests.

It's obvious the code you posted does not compile, it's undoubtedly psuedo-code. Is there something wrong with that algorithm?

[conan19870619]

specially the part of using A to express the subsets and put it into D[A].

want a hint to make this happen.

[baxter_1]

I'm looking for a solution the the traveling salesman problem as well but more specifically something called the greedy hueristic. Here are the instructions for the part I'm working on:

Write a function

void GreedyHeuristic()

that implements the greedy heuristic applied to TSP. A reasonable interpretation of “greedy heuristic” in this context is as follows. At the outset only city[0] is “visited”. At some intermediate step, suppose city[0] to city have been visited; find the unvisited city nearest to city, swap it into location city, and regard it as visited. Repeat until all cities are visited. (In other words, at each step the salesman visits the nearest unvisited city from his current location. Test your new function. How well does the greedy heuristic perform? Run the greedy heuristic on the 50-city data file and record the result in the file results.

I'm writing the code in Basic C. If everyone has any suggestions I'd really appreciate it!!

[hacker-page]

I've found this post over google, because I was so deeply in need of a solution, and still there isn't one out there.
So I got some RL sources and created my algorithm. It probably isn't the nicest and fastes but it does work pretty good! =)

Code: http://codepad.org/vxdGzCdu

#include <iostream>
#include <cmath>

using namespace std;

int** C; // Optimums-Matrix
int** d; // Distanzen zwischen den Städten
int iN;  // Anzahl Städte

int NumberOfSetBits(int i); // Zählt die gesetzten Bits in einem Integer

int main()
{
   /** Anzahl Städte einlesen **/
   scanf("%i",&iN);

   /** Initialisieren **/
   C = new int*[iN+1];         // n Zahlen ohne 0 -> iN+1
   for(int i=1; i <= iN; i++)  // Bis und mit iN ohne 0
      C[i] = new int[(1<<iN)]; // 2^iN ohne 0, jedoch ist 2^iN bereits der komplette Weg (7 = 111 oder 15 = 1111); 1<<x = 2^x

   d = new int*[iN+1];        // n Zahlen ohne 0
   for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0
      d[i] = new int[iN+1];   // n Zahlen ohne 0

   /** Eingabe **/
   for(int i=1; i <= iN; i++)    // Bis und mit iN ohne 0
      for(int j=1; j <= iN; j++) // Bis und mit iN ohne 0
      {
         scanf("%i", &d[i][j]);   // Distanzen einlesen
      }

   /*********************************************
    *                Algorithmus                *
    *********************************************/

   /** Initialisiere alle mit Mächtigkeitszahl 2 in C **/
   for(int k=2; k <= iN; k++) // Ohne 0 & 1 für k, bis und mit iN
   {
      for(int c=2; c <= iN; c++)
         C[c][1+(1<<(k-1))] = d[1][k]; // Stadt 1 + Stadt k
   }

   /** Berechne die überigen Mächtigkeitszahlen in C **/
   for(int s=3; s <= iN; s++)                 // Mächtigkeitszahl erhöhen, ohne 0,1,2
   {
      for(int S=(1<<(s-2)); S < (1<<iN); S++) // Beginne bei 2^(s-2), ende bei 2^iN
         if(NumberOfSetBits(S) == s)          // Menge mit der Mächtigkeitszahl s
            for(int k=2; k <= iN; k++)        // Alle Städte durchgehen
               if((S&(1<<(k-1))) > 0)         // Wenn Stadt k in Menge S vorkommt... && S >= (1<<(k-1))
               {
                  C[k][S]=9999999;
                  for(int m=2; m <= iN; m++)  // Zweite Verbindungsstadt finden
                  {
                     if(m == k || (S&(1<<(m-1))) == 0) // m darf nicht gleich k sein & m muss in der Menge S vorhanden sein
                        continue;
                      C[k][S] = min(C[m][S-(1<<(k-1))]+d[m][k], C[k][S]); // Was ist kleiner der "neue" Wert oder der Ursprungswert?
                      break;
                  }
               }
   }

   /** Optimum berechnen **/
   int opt = 9999999;
   for(int k=2; k <= iN; k++)
   {
      opt = min(C[k][(1<<(iN))-1]+d[1][k], opt);
   }

   printf("%i\n",opt);

   // Pausieren
   //system("pause");

   /** // Auskommentieren um die Optimums-Matrix auszugeben
   for(int i=1; i <= iN; i++)
   {
      for(int j=1; j < (1<<iN); j++)
      {
         printf("%i ",(C[i][j]<0?0:C[i][j]));
      }
      printf("\n\n");
   }**/

   return 0;
}

/** Bit-Zähler nach dem 'parallel'-Algorithmus (oder 'variable-precision SWAR'-Algorithmus) **/
int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Have fun with it!

@post-starter: I used an array like [integer][bitset as integer] for the D!

[hacker-page]

Hmmm, the code above is a bit buggy, and does give you a result, but not the optimum...

So here you go with the one that works fine:

http://codepad.org/uwqjDDCM

#include <iostream>
#include <cmath>

using namespace std;

#define INF 9999999

int** C; // Optimums-Matrix
int** d; // Distanzen zwischen den Städten
int iN;  // Anzahl Städte

int NumberOfSetBits(int i); // Zählt die gesetzten Bits in einem Integer

int main()
{
   /** Anzahl Städte einlesen **/
   scanf("%i",&iN);

   /** Initialisieren **/
   C = new int*[iN+1];         // n Zahlen ohne 0 -> iN+1
   for(int i=2; i <= iN; i++)  // Bis und mit iN ohne 0
      C[i] = new int[(1<<iN)]; // 2^iN ohne 0, jedoch ist 2^iN bereits der komplette Weg (7 = 111 oder 15 = 1111); 1<<x = 2^x

   d = new int*[iN+1];        // n Zahlen ohne 0
   for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0
      d[i] = new int[iN+1];   // n Zahlen ohne 0

   /** Eingabe **/
   for(int i=1; i <= iN; i++)    // Bis und mit iN ohne 0
      for(int j=1; j <= iN; j++) // Bis und mit iN ohne 0
      {
         scanf("%i", &d[i][j]);   // Distanzen einlesen
      }

   /*********************************************
    *                Algorithmus                *
    *********************************************/

   /** Initialisiere alle mit Mächtigkeitszahl 2 in C **/
   for(int k=2; k <= iN; k++) // Ohne 0 & 1 für k, bis und mit iN
   {
         C[k][1^(1<<(k-1))] = d[k][1]; // Stadt 1 + Stadt k
   }

   /** Berechne die überigen Mächtigkeitszahlen in C **/
   for(int s=3; s <= iN; s++)                 // Mächtigkeitszahl erhöhen, ohne 0,1,2
   {
      for(int S=(1<<(s-2)); S < (1<<iN); S++) // Beginne bei 2^(s-2), ende bei 2^iN
         if(NumberOfSetBits(S) == s)          // Menge mit der Mächtigkeitszahl s
            for(int k=2; k <= iN; k++)        // Alle Städte durchgehen
               if((S&(1<<(k-1))) > 0)         // Wenn Stadt k in Menge S vorkommt... && S >= (1<<(k-1))
               {
                  C[k][S] = INF;
                  for(int m=2; m <= iN; m++)  // Zweite Verbindungsstadt finden
                  {
                     if(m == k || (S&(1<<(m-1))) == 0) // m darf nicht gleich k sein & m muss in der Menge S vorhanden sein
                        continue;
                     C[k][S] = min(C[m][S^(1<<(k-1))]+d[m][k], C[k][S]); // Was ist kleiner der "neue" Wert oder der Ursprungswert?
                  }
               }
   }

   /** Optimum berechnen **/
   int opt = INF;
   for(int k=2; k <= iN; k++)
   {
      opt = min(C[k][(1<<(iN))-1]+d[1][k], opt);
   }

   printf("%i\n",opt);
   
   /*// Auskommentieren um die Optimums-Matrix auszugeben
   for(int i=2; i <= iN; i++)
   {
      for(int j=3; j < (1<<iN); j++)
      {
         printf("%i ",(C[i][j]<0?0:C[i][j]));
      }
      printf("\n\n");
   }*/

   // Pausieren
   //system("pause");

   return 0;
}

/** Bit-Zähler nach dem 'parallel'-Algorithmus (oder 'variable-precision SWAR'-Algorithmus) **/
int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

or a version which is a bit diffrent, but works a bit fast:

http://codepad.org/reLya2ui

#include <iostream>
#include <stdio.h>
#include <cmath>

using namespace std;

#define INF 9999999

int** C; // Optimums-Matrix
int** d; // Distanzen zwischen den Städten
int iN;  // Anzahl Städte

int main()
{
   /** Anzahl Städte einlesen **/
   scanf("%i",&iN);

   /** Initialisieren **/
   C = new int*[iN];         // n Zahlen ohne 0 -> iN+1
   for(int i=1; i <= iN; i++)  // Bis und mit iN ohne 0
      C[i-1] = new int[(1<<iN)]; // 2^iN ohne 0, jedoch ist 2^iN bereits der komplette Weg (7 = 111 oder 15 = 1111); 1<<x = 2^x

   d = new int*[iN+1];        // n Zahlen ohne 0
   for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0
      d[i] = new int[iN+1];   // n Zahlen ohne 0

   /** Eingabe **/
   for(int i=1; i <= iN; i++)    // Bis und mit iN ohne 0
      for(int j=1; j <= iN; j++) // Bis und mit iN ohne 0
      {
         scanf("%i", &d[i][j]);   // Distanzen einlesen
      }

   /*********************************************
    *                Algorithmus                *
    *********************************************/

   /** Initialisiere alle mit Mächtigkeitszahl 2 in C **/
   for(int k=2; k <= iN; k++) // Ohne 0 & 1 für k, bis und mit iN
   {
      C[k-1][1^(1<<(k-1))] = d[k][1]; // Stadt 1 + Stadt k
   }

   /** Berechne die überigen Mächtigkeitszahlen in C **/
   for(int s=3; s <= iN; s++)                 // Mächtigkeitszahl erhöhen, ohne 0,1,2
   {
       int *comb = new int[s-1];             // Menge mit der Mächtigkeitszahl s
       for(int i=0; i<s-1; i++)
           comb[i] = i;
           
    while(true)
    {          
        int S = 1;
        for(int i=0; i < s-1; i++)
            S = S^(1<<(comb[i]+1));
         
         for(int i=0; i < s-1; i++) //Alle Städte in S (comb) durchgehen
         {
               int k = comb[i]+2;
          C[k-1][S] = INF;
          for(int j=0; j < s-1; j++)  // Zweite Verbindungsstadt finden
          {
             int m = comb[j]+2;
             if(m == k) // m != k
            continue;
              C[k-1][S] = min(C[m-1][S^(1<<(k-1))]+d[m][k], C[k-1][S]); 
          }
             }
             
             //Compute next Combination
             int i = (s-1) - 1;
         ++comb[i];
         while ((i > 0) && (comb[i] >= iN-1 - (s-1) + 1 + i)) {
        --i;
        ++comb[i];
         }
         if (comb[0] > (iN-1) - (s-1))
        break;         //Last combination computed, now break
         for (i = i + 1; i < (s-1); ++i)
        comb[i] = comb[i - 1] + 1;
    }
   }

   /** Optimum berechnen **/
   int opt = INF;
   for(int k=2; k <= iN; k++)
   {
      opt = min(C[k-1][(1<<(iN))-1]+d[1][k], opt);
   }

   printf("%i\n",opt);

   /* // Auskommentieren um die Optimums-Matrix auszugeben
   for(int i=1; i <= iN; i++)
   {
      for(int j=1; j < (1<<iN); j++)
      {
         printf("%i ",(C[i-1][j]<0?0:C[i-1][j]));
      }
      printf("\n\n");
   } */
   
   // Pausieren
   //system("pause");

   return 0;
}

[XDenasdc]

Hello. I've been looking for this for long time. My problems is related with TSP, but at the same time it's really doesn't. Would it be able to set the number of cities that has to be visited out of all cities. For example : We have 80 cities spreaded around. Out of all 80 we have to connect only 40 towns. Also the task is to join them as so that between each citie there is 40 km or units (units would be used if we do not know exact lenght between cities and when we use (x,y) for city location.

If you know how to make that, I would be very pleased.