TSP Software 1: Unterschied zwischen den Versionen

Version vom 25. Juni 2013, 15:16 Uhr

NOCH IN BEARBEITUNG !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Theorie

Das 'Traveling Salesman Problem' (auch 'Problem des Handlungsreisenden') ist ein kombinatorisches Optimierungsproblem. Dabei besteht auf Aufgabe darin, eine optimale Reihenfolge für den Besuch von Knotenpunkten (z.B. Städte, Bohrungen ect.) zu finden. Das Kriterium, welches es dabei zu minimieren gilt, kann unterschiedlich sein; beispielweise kann es sinnvoll sein die Wegstrecke (Längeneinheiten), die Zeit (Zeiteinheiten) und/oder die Kosten (Geldeinheiten) oder eine Mischung aus diesen Kriterien heran zu ziehen.

Des Weiteren gibt es unterschiedliche Restriktionen für die TS-Problemantik:

Um das Beispiel so einfach wie möglich zu halten, minimieren wir die Wegstrecke und grenzen Kanten (z.B. Straßen) aus; jeder Punkt kann also frei mit jedem anderen Punkt verbunden werden.

Beispiel:

Um eine Städtereise zu planen bei denen 4 verschiedene Städte (A, B, C, D) angefahren werden sollen, gibt es (n - 1)! mögliche Routen: In diesem Fall also (4 - 1)! = 6.

Nach dieser Formel steigt die mögliche Lösungsmenge also mit jeder weiteren Stadt stark an (n-mal). Lässt man die Graphen (bzw. alle Kanten) ungerichtet - ist die Richtung, in der die Route abgefahren wird also irrelevant - so halbiert sich die Lösungsmenge - die neue Formel lautet demnach: (n - 1)! / 2

Trotz dieser Einsparung verhält sich die potenzielle Lösungsmenge wie folgt:

Städte:          mögliche Routen:        Laufzeit (3GHz Single Core):
      3                         1                   0,063 sec
      4                         3                   0,073 sec
      5                        12                   0,078 sec
      6                        60                   0,109 sec
      7                       360                   0,125 sec
      8                     2.520                   0,156 sec
      9                    2.0160                   0,187 sec
     10                   181.440                   0,265 sec
     11                 1.814.400                   1.279 sec 
     12                19.958.400                  12.293 sec (ca. Laufzeit von n=11 x 12)
     13               239.500.800                 143.474 sec (ca. Laufzeit von n=12 x 13)
     14             3.113.510.400                ~ 30.000 min (ca. Laufzeit von n=13 x 14)
     15            43.589.145.600                ~  7.400  h  (ca. Laufzeit von n=14 x 15)
     16           653.837.184.000                ~  5.000  d  (ca. Laufzeit von n=15 x 16)
     17        10.461.394.944.000                ~ 85.000  d  (ca. Laufzeit von n=16 x 17)
     18       177.843.714.048.000                ~  4.200  y  (ca. Laufzeit von n=17 x 18)
     19     3.201.186.852.864.000                ~ 80.000  y  (ca. Laufzeit von n=18 x 19)
     20    60.822.550.204.416.000                ~  1.600 ty  (ca. Laufzeit von n=19 x 20)

Typische Problemstellung

fewfwefwef

Lösungsansätze

Code Beispiel:

Hier folgt Code (Leerzeichen vorstellen)

// ------- calculation -------
private double getPointDistance(Point a, Point b){ 
	return 	Math.sqrt(	( a.getX() - b.getX() ) * ( a.getX() - b.getX() ) +
				( a.getY() - b.getY() )	* ( a.getY() - b.getY() ));		
	}

	public void setPathDistance(double bestdistance){
		double calc_distance = 0;
		
			for(int i=0; i<points.length-1; i++){
				calc_distance += getPointDistance(points[i], points[i+1]);
				if(calc_distance > bestdistance){ break; }
			}
			
		calc_distance += getPointDistance(points[points.length-1],points[0]);
		
		distance		= calc_distance;
		calc_done		= true;
		
		//System.out.println( calc_distance );
	}

Quellen

- Wikipedia Eintrag zum TSP ausführliche Informationen zum Traveling Salesman Problem

- Algorithmus der Woche TSP oder die optimale Tour für den Nikolaus

- Online Touren-Planer kostenloser TSP-Solver zur Routenoptimierung