Möglichkeiten zur Verbindung von Punkten berechnen

C

Cymatoxa

Mitglied
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-1281896806.png&size=original
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:
1,2,3,4
1,2,4,3
1,3,2,4
(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):
1,2,3,4,5
1,2,3,5,4
1,2,4,3,5
1,2,4,5,3
1,2,5,3,4
1,2,5,4,3

1,3,2,4,5
1,3,2,5,4
1,3,4,2,5
1,3,5,2,4

1,4,2,3,5
1,4,3,2,5

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. (Als int-Arrays in einer Liste)

LG Cymatoxa
 
Sieh dir mal die Algorithmen von Kruskal und Prim an.

Diese Algorithmen dienen zur Suche von kürzesten Wegen in einem Graphen.


Das einzige Problem daran ist, dass die Wege von Knoten zu Knoten bewertet werden müssen, aber ich denke das kannst du dir aus den koordinaten errechnen. Kenne deine Anforderungen jetzt nicht genau.
 
Hi,

grundsätzlich gibt es für so ein Problem verschiedene Lösungmöglichkeiten. Da gibt es verschiedene Algorithmen, die die kürzesten Verbindungen in Graphen suchen, für Rundreise Probleme, also wo du am Ende wieder deinen ersten Knoten besuchen willst gibt es Branch-And-Bound Ansätze etc. Grundsätzlich sind die meist aber sehr rechenaufwendig, so dass du für größere Probleme schnell zu heuristischen Ansätzen greifen musst, die eventuell nicht immer den kürzesten Weg sondern nur eine Annäherung finden.

Gruß
Der Wolf
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück