Travelling Salesman Problem

An der Schule belege ich das Wahlkursfach Informatik. Kürzlich wählte/bekam ich den Auftrag einen Vortrag über einen Algorithmus für das “Travelling Salesman Problem” oder auf Deutsch “Problem des Handlungsreisenden” vorzustellen. Doch ich konnte nicht einfach einen “normalen” Brute-Force Algorithmus wählen sondern musste das Problem mit Hilfe Dynamischer Programmierung lösen, was die Aufgabe um einiges erschwerte. Denn als bald ich mich dann hinter das Problem machte, musste ich feststellen, dass ich das Dynamische Programmieren immer noch nicht wirklich beherrschte und auch kein fertiger Algorithmus ausser in Pseudocode im Internet zu finden ist.

Ich versuchte dann den folgenden Pseudocode zu interpretieren:

function algorithm TSP(G, n)
 for k := 2 to n do
  C({1, k}, k) := dk,1
 end for
 for s = 3 to n do
  for all S ⊆ {1, 2, . . . , n}||S|| = s do
   for all k ∈ S do
    {C(S, k) = minm≠k,m∈S[C(S - {k},m) + dm,k]}
   end for
  end for
 end for
 opt := mink≠1[C({1, 2, 3, . . . , n}, k) + d1,k
 return (opt)
end

Nach langem herum studieren kontaktierte ich dann verschiedene Personen und herhielt nach längere Pause zur grossen Überraschung eine Antwort, welche mich einen Schritt näher zur Lösung brachte.

Doch die Knacknuss konnte ich dann erst mit der Hilfe eines guten Freundes lösen. Denn bis anhin hatte ich grosse Probleme zu verstehen wie Funktion/Variable “C” aus dem Quellcode zu implementieren wäre und genau diesen Punkt bekam ich erklärt.

Obwohl mir nun eigentlich ziemlich klar war, wie der Algorithmus funktioniert, verwendet ich trotzdem noch ein paar Stunden für die Implementierung, welche sich dann beim “Korrekturlesen” meines Kollegen auch als teilweise fehlerhaft herausstellte.

Im Endeffekt muss ich jedoch zugeben, dass sich die Arbeit längstens gelohnt hat! Und da ich wie Anfangs beschrieben keine brauchbare Implementierung gefunden hatte, möchte ich dies nun ändern.

#include <iostream>
#include <cmath>

#define INF 9999999

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

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

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

   printf("%in",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("nn");
   }*/

   return 0;
}

/** Bit-Zähler nach dem 'parallel'/'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;
}

Der Quellcode enthält bereits recht viele Kommentare und trotzdem könnte man darüber noch viel erklären. Ich möchte mich jedoch nur auf ein paar Dinge beschränken.

Um den Algorithmus zu verstehen ist es notwendig zu wissen was genau “C” ist. Es gibt verschiedene Arten “C” zu implementieren doch die wohl effizienteste ist wohl ein zweidimensionales Array. Das spezielle daran ist nun, dass der erste Index normal von 1 bis n geht und damit angibt in welcher Stadt die Rundreise aufhören soll bevor man zur ersten Stadt zurückkehrt, der zweite Index jedoch einem Bitset entspricht. Jedes einzelne Bit des Integer entspricht einer Stadt beginnend auf der rechten Seite mit Stadt 1. Der Algorithmus untersucht dann anhand der gesetzten Bits, welche Städte für die gegeben Indizes gesucht werden.

An der Position C[4][1011] würde dann also der kürzeste Weg gespeichert werden, welcher bei der Stadt 1 beginnt, durch Stadt 2 geht und in Stadt 4 endet. Dezimal gesehen wäre der Zugriff dann natürlich C[4][11], da (1011)2 = (11)10 gilt. C[3][1111] entspräche dann dem kürzesten Weg von 1 über 2 und 4 bis zur Stadt 3, usw.

Da wir es hier mit einem Bitset aller Städte zutun haben, wird auch schnell die Schwäche des Algorithmus klar, denn das zweidimensional Array braucht einen Speicher von n*2^n, was bei 30 Städten bereits 4GB an Speicher entspricht…

Wenn man den Aufbau betrachtet kann man drei Abschnitte erkennen:

1. Initialisierung & Eingabe: Zu Beginn wird die Arrays (d = Distanzen & c) initialisiert und d wird mit den Eingaben gefüllt.
2. Auffüllen der Tabelle: Dann wir die Tabelle von Vorne nach Hinten mit den optimalen Wegen für die gegebenen Indizes aufgefüllt.
3. Optimums Berechnung & Ausgabe: Zum Schluss wird dann noch geschaut, welches der kürzstes Weg ist, in dem zu alle letzten Werte von c die Distanz, von der ersten Stadt bis zur letzten Stadt, welche durch den ersten Index angegeben wird, dazu addiert wird. Das Optimum wird dann ausgegeben.

Was der Algorithmus nun nicht abdeckt, ist die Rekonstruktion der kürzesten Rundreise, dies ist jedoch wieder ein einfacheres Problem, welches ich vielleicht später einmal noch lösen werde.

Die PowerPoint Präsentation meines Vortrages mit dem Algorithmus, einem Zufallsgenerator für Probleme und Beispiel Eingaben könnte ihr HIER herunterladen!

Viel Spass damit! 🙂