Das Travelling-Salesman-Problem (TSP)

Gesucht wird in einem Graphen G über eine Menge V ein Algorithmus, der den kürzesten Weg errechnet, der von einem Knoten u zu einem Knoten v führt und alle anderen Knoten mindestens einmal besucht.
Der Name der Problemstellung bezieht sich auf die alltägliche Situation eines Handlungsreisenden, eine Reihe von Kunden besuchen zu müssen. Er stellt fest, in welchen Städten die Kunden zu besuchen sind und versucht eine Route zu finden, die möglichst kurz ist. Im Allgemeinem ist dieses Problem in allen ähnlichen Aufgabenstellungen enthalten, bei denen es um Tourenplanung geht; es wird also ständig von Handlungsreisenden, Speditionen, usw. zu lösen sein. Um so bedauernswerter ist es, daß wir keinen Algorithmus angeben können, der das Problem vollständig in polynominaler Zeit löst.
In der ursprünglichen Formulierung des TSPs sind Anfangs- und Endpunkt der Tour identisch, und es wird gefordert, jede Stadt auch nicht mehr als nur einmal zu besuchen. Dies ist eine Einschränkung, die dazu führt, daß es in vielen Fällen überhaupt keine Lösung gibt. Daher beschäftigen wir uns mit dem TSP in der oben angegebenen allgemeineren Formulierung.
In dem Beispiel gibt es zum Beispiel keine Lösung des TSP für eine gesuchte Tour von San Francisco nach Palo Alto, die alle Städte nur einmal besucht. Es gibt aber eine Lösung mit einem Zusatzbesuch von zum Beispiel San Francisco. Zur Lösung des TSPs generieren wir alle möglichen Wege von u nach v, die alle Städte besuchen und jede höchsten AriMax mal, also benutzen wir AriMax als Schranke für die Anzahl der Besuche einer Stadt. Zur Generierung aller Wege können wir einen Algorithmus verwenden, der Ähnlichkeit mit der Tiefensuche hat. Bei ihm kam es jedoch darauf an, daß alle Knoten aufgezählt werden, aber nicht entlang eines Weges, was aber beim TSP der Fall ist. Wir müssen die Knoten eines Graphen derart aufzählen, daß dabei ein Weg entsteht. Dies kann man durch Rücksetzen der gemachten Besuche erreichen, wenn man in eine Sackgasse gerät.
oben weiter

.
Algorithmus:

TSP(StartIndex, EndIndex: IndexType; var Distance :Real; AriMax: Integer);
var      Schranke, AktWegLaenge    :Real;
         WegeMax                   :IndexType;
type     TMinEntfs = array[KnotenAnzahl] of IndexType;
var      MinWeg                    :TMinEntf;

 Besuche(k: IndexType; var Weg :TMinEntfs; maxIndex: IndexType);
 var    BisherigeLaenge        :Real;
        Knoten                 :PKnoten;
        n                      :IndexType;
 begin
   inc(maxIndex)
   Weg[maxIndex] = k
   if erster Durchlauf then
     AktWegLaenge = 0
     BisherigeLaenge = 0
   else
     BisherigeLaenge = AktWegLaenge
     AktWegLaenge = AktWegLaenge + Kantenwert(k, Weg[maxIndex-1])
   end-if
   inc(Marke(k))
   if AktWegLaenge < Schranke then
     if ist_eine_TSP-Lösung then
       MinWeg = Weg
       Schranke = AktWegLaenge
     else
       for-each x in (Kante von Knoten(k)) do
         if Marke(Kante(k, x).ZielKnoten) < AriMax then
          Besuche(Kante(k, x).ZielKnoten, Weg, maxIndex)
         end-if
       end-for-each
     end-if
   end-if
   AktWegLaenge = BisherigeLaenge
   Weg[maxIndex] = 0
   dec(Marke(k))
 end


var      Weg                    :TMinEntfs;
         KnotenNr, WegIndex, n  :IndexType;
begin
  WegeMax = AriMax * FCount + 3
  KantenCount = 0
  Schranke = 0
  for-each x in Kanten do
    Schranke := Schranke + x.Wert
  end-for-each
  for n = 1 to KnotenAnzahl do
    Weg(n) = 0
    MinWeg(n) = 0
    Marken(n) = 0
  end-for
  Besuche(StartIndex, Weg, 0)
  Distance = Schranke
end
oben weiter

.
Das heißt:

Zur Lösung des TSPs generieren wir alle möglichen Wege von u nach v, die alle Städte besuchen und jede höchsten AriMax mal. Zum Generieren aller Wege verwenden wir einen Tiefensuchen-ähnlichen Algorithmus. Die Knoten müssen derart aufgezählt werden, daß dabei ein Weg entsteht. Dies kann man durch Rücksetzen der gemachten Besuche erreichen, wenn man in eine Sackgasse gerät. Der kürzeste Weg wird gespeichert und nach durchlaufen aller möglichen Wege steht der kürzeste Weg im Speicher zur Verfügung.
oben weiter

.
Beispielrealisierung (in gekürzter Fassung):

Die Implementation basiert auf diesen Definitionen. 
function TGraph.TravellingSalesmanProblem(StartIndex, EndIndex: IndexType;
    var KantenCount: IndexType; var Distance :Real; AriMax: Integer): Boolean;
var      Schranke             :Real;
         HatWeg               :Boolean;
         WegeMax              :IndexType;
         AktWegLaenge         :Real;
type     TMinEntfs = array[1..1] of IndexType;
var      MinWeg               :^TMinEntfs;

 function TesteWeg(var Weg :TMinEntfs; maxIndex: IndexType): Boolean;
 var      k       :IndexType;
 begin                // über alle Knoten den Zielknoten erreicht?
  Result := (Weg[maxIndex] = EndIndex) and (maxIndex > FCount-1);
  k := 1;
  while (k <= FCount) and Result do
   begin
    Result := PointItem(k).Marke <> 0;
    inc(k);
   end;
 end;

 procedure Besuche(k: IndexType; var Weg :TMinEntfs; maxIndex: IndexType);
 var       BisherigeLaenge     :Real;
           Knoten              :PKnoten;
           n                   :IndexType;
 begin
  inc(maxIndex);
  if maxIndex >= WegeMax-2 then
   raise Exception.Create('Der Weg wurde zu lang ...');
  Weg[maxIndex] := k;
  if maxIndex = 1 then // allererster Aufruf?
   begin
    AktWegLaenge := 0;
    BisherigeLaenge := 0;
   end
  else
   begin
    BisherigeLaenge := AktWegLaenge;
    Knoten := PointItem(Weg[maxIndex-1]);
    if Knoten.KantenCount > 0 then // inc(AktWegLaenge, Kantenwert)
     for n := 0 to Knoten.KantenCount-1 do
      if Knoten.Kanten[n].DestKnoten = k then
       AktWegLaenge := AktWegLaenge + Knoten.Kanten[n].Value;
   end;

  Knoten := PointItem(k);
  inc(Knoten.Marke);
  if AktWegLaenge < Schranke then // bereits gegangener Weg innerhalb Grenze?
   if TesteWeg(Weg, maxIndex) then // Ziel bereits erreicht?
    begin                         // Aktuellen Weg umkopieren
     Move(Weg, MinWeg^, (maxIndex+1) * SizeOf(Weg[1]));
     Schranke := AktWegLaenge;
     HatWeg := True;
    end
   else                             // Besuche jeden Nachbarknoten
    if Knoten.KantenCount > 0 then
     for n := 0 to Knoten.KantenCount-1 do
      if PointItem(Knoten.Kanten[n].DestKnoten).Marke < AriMax then
       Besuche(Knoten.Kanten[n].DestKnoten, Weg, maxIndex);
  AktWegLaenge := BisherigeLaenge;     // die Rekursion rückgängig machen
  Weg[maxIndex] := 0;
  dec(PointItem(k).Marke);
 end;

 procedure CalculateSchranke;
 var       Counter, n     :IndexType;
 begin            // Summe der Gewichtung sämtlicher Kanten
  Schranke := 0;
  if FStart <> nil then
   for Counter := 1 to FCount do
    with PointItem(i)^ do
     if KantenCount > 0 then
      for n := 0 to KantenCount - 1 do
       Schranke := Schranke + Kanten[n].Value;
end;

var      Weg                      :^TMinEntfs;
         KnotenNr, WegIndex, n    :IndexType;
         Knoten                   :PKnoten;
begin
 WegeMax := AriMax * FCount + 3;
 KantenCount := 0;
 Distance := 0;
 GetMem(MinWeg, sizeof(MinWeg[1]) * WegeMax);
 try
   CalculateSchranke;
   GetMem(Weg, sizeof(Weg[1]) * WegeMax);
   try
     FillChar(Weg^, sizeof(Weg[1]) * WegeMax, 0);
     FillChar(MinWeg^, sizeof(MinWeg[1]) * WegeMax, 0);
     ZeroKnotenMarken;
     HatWeg := False;
     Besuche(StartIndex, Weg^, 0); // starten der Rekursion
     KantenCount := 0;
     ZeroKnotenMarken;
     ZeroKantenMarken;
     if HatWeg then // markieren des Weges
      begin
       KnotenNr := MinWeg[1];
       WegIndex := 2;
       Knoten := nil;
       while KnotenNr >= 1 do
        begin
         if assigned(Knoten) then
          begin
           if Knoten.KantenCount > 0 then
            for n := 0 to Knoten.KantenCount-1 do
             if Knoten.Kanten[n].DestKnoten = KnotenNr then
              inc(Knoten.Kanten[n].Marke);
           inc(Knoten.Marke);
          end;
         Knoten := PointItem(KnotenNr);
         KnotenNr := MinWeg[WegIndex];
         inc(WegIndex);
         inc(KantenCount);
        end;
       if assigned(Knoten) then
        inc(Knoten.Marke);
       Distance := Schranke;
      end;
   finally
    FreeMem(Weg, sizeof(Weg[1]) * WegeMax);
   end;
 finally
  FreeMem(MinWeg, sizeof(MinWeg[1]) * WegeMax);
 end;
 Result := HatWeg;
end;
oben weiter

.
Effizienzbetrachtung:

Die Suche nach einer Lösung des TSPs gelingt bei 15 Städten in rund 0,71 Sekunden wenn man nur ein Besuch pro Stadt zuläßt. Wenn wir zulassen, daß jede Stadt bis zu zweimal besucht werden darf, wächst der Rechenaufwand ganz erheblich auf 17,94 Sekunden. Bei gelichteten Graphen von nur zehn Städten, wie im Beispiel, braucht man bei einmaligen Besuch 0,31 Sekunden, beziehungsweise bei bis zu doppelten Besuchen 0,67 Sekunden. Die Zahl der generierten Wege bei 15 Städten und maximal einem Besuch liegt bei 483, bei bis zu zwei Besuchen sind jedoch 3.832.913 Wege erforderlich, was an der Vielzahl von unsinnigen Doppelbesuchen, die der Algorithmus nicht als solcher erkennt, liegt. Die oben genannten Anzahl der generierten Wege ergibt sich, wenn man die Schranke automatisch abschätzen läßt. Mit einer kleineren Schranke erniedrigt sich die Zahl der Wege erheblich.
Die Laufzeit L des Programms ist Proportional zu 2N, also gilt L = c * 2N mit einer geeigneten Konstante c. Bei 15 Städten und einer Laufzeit 0,71 Sekunden müßte c ungefähr bei 0,71s = c * 215 =>c = 0,71s / 215 = 0,71s / 32768 = 0,00002166... Bei einem Graphen mit 40 Knoten wäre so eine Laufzeit L von 0,00002166... * 240 = 23823646,72 s = 6617,6796444.... h = 275,73665185185... d, also über 9 Monate, zu erwarten. Mit jeder zusätzlicher Stadt verdoppelt sich die Laufzeit. Das bedeutet, daß auch bessere Computer oder gar der allgemeine Fortschritt in der Technik hier nicht großartig hilft. Man kann jedes Jahr ungefähr eine Stadt mehr in der gleichen Zeit berechnen.
In einem Graphen, bei dem von jedem Knoten genau zwei Kanten wegführen, gibt es offensichtlich genau 2N Wege der Länge N. In diesem Fall ist die Abschätzung der Laufzeit durch 2N leicht einzusehen. In anders strukturierten Graphen muß anders argumentiert werden, aber normalerweise wird sich jedesmal eine exponentiell wachsende Laufzeit ergeben.
oben weiter

.
Optimierungsvorschläge:

Man könnte dem Algorithmus mitteilen, welche Städte doppelt besucht werden könnten und bei welchen es sinnlos ist. So könnte man eine Menge sinnloser Wege sparen. Offensichtlich kann man sehr viel Laufzeit sparen, wenn man die Suche auf einfache Wege beschränkt. Trotzdem kann man nicht hoffen, umfangreiche TSPs mit diesem Programm berechnen zu können. Man kann das Programm sicherlich noch optimieren, was aber keinen nennenswerten Einfluß auf die Laufzeit haben wird, denn diese entsteht bei der Generierung aller möglichen Wege.
oben Beispiel