Hallo zusammen,
wir müssen als Hausaufgabe 2 Varianten des Traveling-Salesman Problem programmieren. Es sind also beliebige Städte gegeben, die alle genau einmal besucht werden sollen (wobei der Start auch wieder das Ziel ist) mit minimalen Kosten. Die eine Variante ist einfach, man probiert alle Wege durch, dauert lange aber funktioniert. Die 2 Variante ist etwas komplexer:
Beipsiel mit 10 Städten:
Wir beginnen mit dem initialisieren der Kosten im Hashtable von 1-->2, 1-->3...1->10 und bauen darauf weitere Berechnungen auf:
Jetzt werden alle Teilmengen der Größe 3 über der Menge {1..10} gebildet und davon nochmal jeweils alle Permutationen beginnend mit der 1, also:
{1, 2, 3}
-> 1->2->3
-> 1->3->2
{1, 2, 4}
-> 1->2->4
-> 1->4->2
...
{1, 9, 10}
-> 1-> 9->10
-> 1->10->9
diese ganzen Permutationen ergeben nun alle möglichen Wege. Der Unterschied zur 1.Aufgabe ist, dass man aus der Teilmenge mit L Elementen die Strecke von 1 bis L-1 Elementen in einer Hashtabelle nachguckt da sie schon berechnet wurden und somit nichts doppelt berechnet. Dann wird der Weg von L-1 nach L hinzugefügt. Diese Kosten werden nun auch wieder in der Hashtable gespeichert um bei weiteren Berechnungen mit L+1 darauf zurückzugreifen zu können.
Dies wird nun über alle i-Elementigen Teilmengen mit i=2,..,10 durchgeführt.
Das Problem ist, dass wir nicht wissen, wie wir die Kosten aller Teilmengen und allen Permutationen sinnvoll speichern. ZZ.speichern wie die kürzesten Wege jeder Menge in einer Map, können dann aber nicht mehr auf die anderen Permutationen zurückgreifen, da der Hash für jede Stadt das passende Bit auf true setzt, also die Menge der Städte {1, 2, 5} ist 10011.
Ich hoffe, es ist einigermaßen verständlich, sonst fragt bitte nochmal nach.
Vielen Dank im Vorraus, Tobias
PS: wem der formale Weg mehr zusagt gucke bitte
hier 