TSP mit dynamischer Programmierung lösen

[metzgore]

Hallo an alle,

ich stehe momentan etwas auf dem Schlauch. Ich bin dabei, das TSP mit dynamischer Progrmmierung zu lösen. Ich habe mich dabei an Pseudocodes orientiert. Der Code sieht wie folgt aus...

private static int computeShortestPath(int currentCity, LinkedList<Integer> cities, int[][] distMatrix) {
		if (cities.isEmpty()) {
			return distMatrix[currentCity][start];
		} else {
			int way = Integer.MAX_VALUE;
			for (int z = 0; z < cities.size(); z++) {
				int j = cities.get(z);
				LinkedList<Integer> citiesCopy = (LinkedList<Integer>) cities.clone();
				citiesCopy.remove(z);
				int temp = distMatrix[currentCity][j] + computeShortestPath(j, citiesCopy, distMatrix);
				way = Math.min(way, temp);
			}
		return way;
	}
}

Der Code funktioniert soweit.

Wie könnte man am einfachsten die dazugehörige Reihenfolge der besuchten Städte bestimmen? Momentan wird mir ja nur die Gesamtstrecke der kürzesten Rundreise zurückgegeben, aber soviel bringt mir das nun auch wieder nicht.

Vielleicht hat ja jemand von euch die passende Idee.

Grüße

 

[maxwell-cs]

anstatt die funktion die länge eines weges zurückgeben zu lassen, kannst du sie einen weg zurückgeben lassen.

erstelle einfach eine klasse weg, die aus einem int für die länge und einer liste für die besuchten knoten besteht.

wenn du im fall cities.isEmpty() bist, brauchst du als einzigen knoten currentCity anzugeben und die länge wie bisher zu berechnen.

ansonsten merkst du dir anstelle der länge einer bisher optimalen lösung eben einen bisher optimalen weg in der schleife und fügst am ende zur optimallösung currentCity dazu und passt die länge an.


eine anmerkung von mir: meiner meinung nach ist das keine implementierung des dynamischen programms für TSP, da du dir die teillösungen nicht speicherst, was eine zentrale idee in der dynamischen programmierung ist. durch das speichern der teilösungen kannst du dir redundante berechnungen sparen.
auf der anderen seite kostet es natürlich mehr speicher. falls der speicher nicht reicht, kann man aber immernoch lösungen für teilinstanzen mit begrenzter anzahl städten speichern.

 

[metzgore]

Hm, ja stimmt, da fehlt doch noch was. Hab ich da die Erklärung hier falsch verstanden? Da wird zwar auch davon geschrieben, dass man Teilprobleme in einer Tabelle speichert, aber im Pseudocode wird dann keine Extra-Tabelle benutzt, sondern nur die eine Tabelle für die Distanzen (es sei denn L(i, A) soll diese Extra-Tabelle darstellen).

Habe da noch eine Frage. Wir sollen das TSP für 16 Städte lösen. Ist die im Link angegebene Zeit von knapp 5 Stunden überhaupt realistisch? Ich habe hier eine Lösung mit dynamischen Programmieren, die löst mir das in ca. 2 Sekunden.

 

[maxwell-cs]

genau. L(i, A) ist eine tabelle.

ein problem, das sich dabei auftut, ist die verwendung einer menge als index in einer tabelle (= array).

du kannst dir ja mal dazu gedanken machen, wie man das effizient löst.
wenn du die lösung nicht findest, kann ichs dir ja immer noch verraten

ansonsten zu den laufzeiten: die angegebenen laufzeiten (oder wohl eher: obere schranken für die laufzeit) sollen ja primär den vorteil von 2^n * n gegenüber (n-1)! aufzeigen. die tatsächliche laufzeit hängt dann von der effizienz der implementierung, der geschwindigkeit der cpu, dem schwierigkeitsgrad der instanz und so weiter ab. da würde ich nicht zu viel drauf geben.

wichtiger: wie verhält sich die laufzeit, wenn die instanz größer wird (also städte dazukommen)? das sagt mehr aus.

 

[metzgore]

So richtig habe ich keine Idee. Eine Lösung, die ich von jemandem bekommen habe, nutzt ein BitSet zur Repräsentation und Indexierung. Wäre das in meinem Fall hier auch günstig?

Edit: Jo, ich glaub ich werd ein BitSet dafür nehmen, das macht genau das, was ich will.

 

[maxwell-cs]

genau das ist die lösung. nen unsigned int als bitset auffassen und schon hat man seine repräsentation der menge als index.
das kann man übrigens auch weiter treiben und die mengen nur so kodieren, also gänzlich auf listen verzichten.