Permutationen einer Tour rekursiv

[prha]

Hey,
das Problem, welches es zu lösen gilt ist folgendes.
Gegeben ist ein vollständiger Graph mit n Knoten, und einer zufällig gewählten Kantenbewertung von 0-10.
Nun soll die kürzeste Tour(=Weg bei dem alle Knoten einmal besucht werden, und Anfangs- und Startknoten der Tour gleich sind) heraus gefunden werden. Und zwar durch eine rekursive Permutation aller Möglichkeiten.

Bis jetzt bin ich soweit gekommen:

Die Idee ist: ich teste ob es schon eine Tour ist, was übergeben wird. Wenn ja berechne ich die Länge, und vergleiche ob diese Tour die kürzeste Länge, aller bisher berechneten Touren hat. Wenn ja speichere ich die Länge und die Tour selbst.
Wenn nicht, möchte "Permutationen von Touren" erzeugen, und dann wieder "recursiveTsp" aufrufen. Wenn dies überhaupt möglich ist. Rekustion verstehe ich nämlich noch nicht 100%ig, was wohl offensichtlich ist .

Ich hoffe ihr könnt mir Denkanstöße geben, oder erklären was an meinem Gedanke falsch ist.

import java.io.*;

public class TSP{
		
	static int n; // number of nodes
	static double[][] D; // distance matrix

	public static double recursiveTsp(int fixed, int[] tour){
		int[] optour=new int[n+1];
		double dist = Double.POSITIVE_INFINITY;
		if(fixed == tour.length-1 ){ // if there aren't any nodes to visit
			double opdist = tourLength(D,tour); //calculates length of tour
			if (opdist<dist){ // checks if tour is shorter then every other tour
				dist=opdist;//saves length of best tour
				optour=tour;//saves best tour
			}
		}
		else{ //there are nodes, which have to be visited
			for (?????) {

                                                ?????????

			}
		}
	return dist;
	}
	
	/**
	* calculates the length of the tour
	* @param tour nodes of the tour
	* @param D distance matrix	
	*/
	public static double tourLength(double[][] distance, int[] tour){
		double dist=0;
		for (int i = 0; i<tour.length-1;i++){
			dist+= distance[tour[i]][tour[i+1]];		
		}	
		return dist;		
	}//end tourLength

 

[Guest]

Was ich gerade noch bemerkt habe:

optour=tour; //saves best tour

ist natürlich nicht Möglich, vom Sinn her. Weil Arrays ja Referenztypen sind.
Tut jedoch nichts zur Sache.

Vielen Dank schonmal

 

[function]

ist voraussetzung das alle punkte einmal besucht werden müßen? oder maximal einmal besucht werden dürfen?

 

[Guest]

alle punkte müssen genau einmal besucht werden.

 

[SlaterB]

ein guter Grundgedanke bei Rekursion allgemein und insbesondere
bei sehr hoher Rekursion (alle Permutationen = n! ?):

nur sehr wenig Objekte neu erzeugen in rekursiven aufrufen,
int[] optour=new int[n+1];
kann einfach nicht da drin stehen, da machst du dich 100x langsamer als nötig,

arbeite mit wenigen festen Objekten,
die du entweder in der Klasse definierst oder als Parameter übergibst,

wenn die ganze Klasse nur für diese eine Suche gedacht ist,
dann hast du es mit Exemplarvariablen/ statischen Variablen leichter,
besonders wenn du Hilfsoperationen definierst,

ob statisch oder nicht ist Geschmackssache, wenn statisch, dann musst du
eben aufpassen, dass nie zwei Suchen gleichzeitig ausgeführt werden,
was in einer Anwendung ohne mehrere Threads leicht ist

----------

so, du brauchst EIN Array der Länge der Tour,
und richtig, in der Rekursion prüfst du als erstes, ob das voll ist,
aber nicht über die Länge, die Länge ist immer das Maximum n,
du schaust, ob alle Felder im Array belegt sind (-1 steht für leer),
diese Information (Rekursionstiefe) könnte auch in irgendeiner Variablen stehen,

wenn Maximallänge erreicht ist, dann Tour-Länge ausrechnen und die Tour wegspeichern,
wichtig: nicht das Array selber speichern, das wird noch gebraucht,
die Werte rauskopieren,

ansonsten:
das Array ist noch leer oder zum Teil befüllt, nun eine Schleife über die
restlichen zur Verfügung stehenden Knoten, einen Knoten in das Array setzen,
rekursiver Aufruf, danach Element wieder entfernen (-1 ins Array schreiben)

der 'ansonsten'-Fall klingt einfach, was? viel mehr ist das nicht womit du deinen PC stundenlang beschäftigen kannst,
etwas tricky ist noch, herauszufinden, welche Knoten noch offen sind, die die bisher nicht im Array verwendet wurden,
wichtig ist, nach dem Rekursionsaufruf das Element wieder zu entfernen, den vorherigen Zustand wiederherzustellen

-----------


Optimierungstipp für ganz später: schon beim Array-Aufbau immer die aktuelle
Länge mitzählen, wenn nach 3 Knoten der Weg schon länger ist als eine
früher gefundene optimale Tour, dann muss man gar nicht erst weitermachen

--------

wichtig zum Testen: klein anfangen, 3 bis 4 Knoten,

vorher auf Papier alle Kombinationen aufmalen und wie es der PC machen soll:
erst einen Knoten auswählen, dann einen nächsten usw.


im Programm alles mögliche mit System.out.println oder anders loggen,
welche Operation ausgeführt wird, welche Knoten ausgewählt werden,
wer wann was im Array ändert usw.

--------

eine sehr komplizierte Sache, nach deinem ersten Versuch und deinem bisherigen
Verständnis der Rekursion zu urteilen, viel zu hoch,

nicht verzweifeln wenn du das nicht hinkriegst
es gibt zig einfachere Rekursions-Aufgaben, die du vorher lösen solltest