Hallo!
Ich beschäftige mich seid geraumer Zeit mit TSP(wem das nichts sagt HIER klicken), erst auf Grund der Schule und jetzt privat (habe mit einem Freund einen kleine Wettbewerb am laufen, wer die beste/schnellste Methode zur Wegbestimmung schreiben kann.).

Hier mal ein kleines Bild, das helfen soll den Algorithmus zu verstehen. Bei Fragen stehe ich immer gerne zu Verfügung.


Wie oben schon gesagt, das Problem ist(sind) die Überkreuzungen, denn die machen den ganzen, doch recht nah am Optimun gelegenen Weg kaputt. Hier bräuchte ich eure Hilfe, ich will nämlich eine Optimierungsfunktion einbauen, die folgendes macht.

1) Nach Überkreuzungen von Kanten suchen. Und diese durch Tauschen der Knoten zu elimienieren. Ich hatte mir hier überlegt, das man aus jeweils 2 (verbundenen) Punkten eine Gerade erstellt, dann überprüft ob diese eine andere Grade schneidet und ob diese sich überhaut in dem gültigen Intervall schneiden (damit ist gemeint ob ein Schnittpunkt zwischen den beiden Knoten vorliegt.

2)Ist mir entfallen, ich editier wenns mir einfällt

Ich hoffe das mir einer einen Ansatz für meine Idee geben kann, bin nämlich im Moment ein wenig am verzweifeln, da ich keine gute Idee hab wie ich das umsetzen soll.

Vielen Dank im Vorraus.

Dragonclaw