Traveling Salesman Problem - Lösungsansätze

Branch and Bound ist ein relativ einfacher Algorithmus. Im wesentlichen ist es ein Suchen und Vergleichen aller Möglichkeiten. Um es aber nicht ausufern zu lassen, werden gewisse Einschränkungen vorgenommen.

Eine neue Tour wird gebildet, indem jeweils eine neue Stadt in eine schon bestehenden Tour eingefügt wird. Eine Tour der Größe m hat m Verbindungen (Kanten). Eine neue Stadt kann also an m verschiedenen Stellen eingefügt werden.

Der Algorithmus 'merkt' sich diese Möglichkeiten, ordnet sie nach einem Kriterium, z.B. der Größe und arbeitet sie einzeln ab. Dazu wird die nächste Stadt in die Tour eingefügt etc.

Die Beschränkung besteht nun darin, daß nur die Touren verfolgt werden, deren Kosten noch unterhalb eines Schwellwertes liegen. Sollte eine Tour gefunden werden, in der alle Städte eingetragen sind und deren Kosten unterhalb der Schwelle liegen, wird sie als bisher beste Tour gespeichert und ihre Kosten bestimmen die neue Schwelle.

Auf diese Art und Weise kann ein Großteil der Zweige abgeschnitten werden. Das sollte aber nicht darüber hinwegtäuschen, daß die Zeitkomplexität noch immer exponentiell von der Problemgröße abhängt. Sie ist lediglich nicht mehr ganz so hoch.

Die Leistungsfähigkeit des Algorithmus kann hier getestet werden.