Möglichkeiten zur Verbindung von Punkten berechnen

Computer: Software & Programmierung Java
#1

Hallo,

ich möchte eine Art „Routenplaner“ schreiben. Dazu hab ich ein GUI mit Canvas auf dem einige Punkte eingezeichnet werden können:
http://www.bilder-space.de/show_img.php?img=c01f62-1…
Mein Programm soll jetzt vom ersten Punkt den kürzesten Weg über alle Punkte und zurück zum Startpunkt berechnen. Dazu brauch ich aber eine Liste mit den Möglichen Wegen.

Beispiel mit 4 Punkten (A, B, C und D):
A-B-C-D, A-B-D-C, A-C-B-D
(Das sind alle Möglichkeiten, da der Weg nur in eine Richtung berechnet werden muss, nicht rückwärts)

Beispiel mit 5 Punkten (A, B, C, D und E):
A-B-C-D-E, A-B-C-E-D, A-B-D-C-E, A-B-D-E-C,
A-C-B-D-E, A-C-B-E-D, A-C-D-B-E, A-C-D-E-B,
A-D-B-C-E, A-D-B-E-C, A-D-C-B-E, A-D-C-E-B

Für die Anzahl der Möglichkeiten ergibt sich mit n Punkten die Formel (n-1)!/2

Ich hoffe, jemand von euch hat eine Idee, wie man eine Funktion schreiben könnte, die für n Punkte die Möglichkeiten wiedergibt.
(Also eine Liste mit int-Arrays mit Zahlen von 0 bis n, statt Buchstaben)

LG Keks

#2

Hallo

Das was du machen willst ist auch bekannt als Traveling Salesman Problem.

Dazu brauch ich aber eine Liste mit den Möglichen Wegen.

Das ist sicherlich eine Möglichkeit wie man das Problem exakt lösen kann, allerdings nur wenn die Anzahl der Punkte klein bleibt, da sonst der Aufwand zu groß wird. Schon ab n = 20 müsstest du wahrscheinlich mehrere Jahre auf das Ergebnis warten.

Ich hoffe, jemand von euch hat eine Idee, wie man eine
Funktion schreiben könnte, die für n Punkte die Möglichkeiten
wiedergibt.

Du könntest z.B. erst alle Möglichkeiten erzeugen und dann jeweils einen der doppelten wieder löschen.

Vielleicht hilft dir das ein bisschen weiter:

http://www.oberstufeninformatik.de/info12/Permutatio…

Grüße

Michael

#3

Vielen Dank,

du hast mir damit sehr geholfen :smile:

#4

ich hat ein ähnliche aufgabe im Studium gehabt, schau dir mal das hier an:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus

#5

wow, ganz schön kompliziert.
Danke für den Link :smile:

#6

Sieht eigentlich schwerer aus, als es ist. Die mathematischen Herleitungen und Beweise, können schon Verwirren. Letztlich läuft alles auf eine Tabelle, mit verschieden Berechnungsschritten hinaus und am Ende gibt es ein Ergebnis in der Art: Route A-C-D-B ist die kürzeste oder A-B-C-D ist die längste Route.