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.
Noch keine Stimmen abgegeben
Noch keine Kommentare

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:

  • greedy Algorithmus (greedy = gierig): An L und an jeder weiteren Station X soll nur diejenige Station angefahren werden, die dem aktuellen Standort möglichst nahe liegt.
  • greedy Algorithmus 2. Ordnung: An L und an jeder weiteren Station X sollen nur eine der beiden Stationen angefahren werden, die dem aktuellen Standort möglichst nahe liegen.

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:

  • N
  • zu einer Potenz p von N, also Np
  • zu eN (exponentielle AbhĂ€ngigkeit)?