C++ Programmieraufgabe: Das Travelling Salesman Problem (TSP)

Es wird das Travelling Salesman Problem vorgestellt, für das verschiedene Algorithmen entwickelt werden sollen. Zudem ist eine spezielle Anordnung der Stationen des Handlungsreisenden gegeben, auf die die Algorithmen angewendet werden sollen.

walter
brute force AlgorithmusTravelling Salesman Problemgreedy AlgorithmusC++Programmieraufgabe
Inhaltsverzeichnis

Einordnung des Artikels

Die Problemstellung

Ein Lieferant soll Waren ausliefern. Dazu startet er in L (seinem Warenlager), soll die Stationen A, B, C, D, E, F, G, H in beliebiger Reihenfolge anfahren und kehrt am Ende wieder nach L zurück. Eine Fahrt, die in L startet und endet und die alle Stationen einmal erreicht (also zum Beispiel LEFGHABCDL), wird im Folgenden als Tour bezeichnet. Die Entfernungen der Stationen sind der Karte zu entnehmen.

Das Warenlager L und die anzufahrenden Stationen A, B, C, D, E, F, G, H mit ihren gegenseitigen Entfernungen.Das Warenlager L und die anzufahrenden Stationen A, B, C, D, E, F, G, H mit ihren gegenseitigen Entfernungen.

Die konkreten Aufgaben

  1. Wieviele unterschiedliche Touren gibt es? Wie lautet die Formel allgemein für N Stationen?
  2. Führt man eine Restriktion der Art Nach Station X soll nicht die Station Y angefahren werden und umgekehrt. Wieviele Möglichkeiten gibt es jetzt, alle Stationen anzufahren? Wie lautet jetzt die Formel allgemein für N Stationen?

Programmieraufgaben

Mit den folgenden Programmen soll das oben formulierte Problem für die Stationen gemäß der Karte gelöst werden. Sämtliche Programme sollen aber so geschrieben werden, dass sie für eine beliebige Karte, also beliebiges N und beliebige Entfernungen, ausgeführt werden können.

1. Schreiben Sie eine Funktion, die alle Möglichkeiten sortiert auflistet, die sich dem Lieferanten bieten und die ausgibt, wieviele Möglichkeiten es sind. Hier heisst sortiert, dass die Tour mit der kürzesten Fahrtstrecke zuerst und die längste Tour zuletzt ausgegeben werden soll (gleichlange Touren sollen in alphabetischer Reihenfolge ausgegeben werden).

2. Schreiben Sie eine Funktion, die (zusätzlich zur vorhergehenden Aufgabe) eine oder mehrere Restriktionen der Art Nach Station X soll nicht die Station Y angefahren werden und umgekehrt berücksichtigt.

3. Die bisherigen Funktionen arbeiten nach dem Prinzip brute force: alle Touren werden untersucht und daraus kann die kürzeste Tour ausgewählt werden. Bei einer großen Anzahl N an Stationen wird der Algorithmus länger rechnen als der Lieferant für eine beliebige Tour benötigt.

Schreiben Sie verbesserte Algorithmen zur Suche der kürzesten Tour:

Geben Sie sämtliche Touren aus, die diese Algorithmen zulassen (wieder sortiert) sowie die Anzahl der zulässigen Touren.

4. Überlegen Sie sich einen weiteren Algorithmus, der zwar nicht alle Möglichkeiten berechnet, der aber dennoch in der Lage ist, der optimalen Lösung sehr nahe zu kommen.

5. Untersuchen Sie die Komplexität der Algorithmen: Versuchen Sie abzuschätzen, wie die Rechenzeit zunimmt, wenn die Anzahl der Stationen N erhöht wird. Welche der Algorithmen besitzen eine Rechenzeit T(N), die proportional ist zu: