nicht schneidende Liniensegmente, während die kumulative Länge

minimieren würde Ich mag einen besseren Algorithmus finden, das folgende Problem zu lösen:nicht schneidende Liniensegmente, während die kumulative Länge

Es gibt N Ausgangspunkte (lila) und N Zielpunkte (grün) in 2D. Ich möchte einen Algorithmus, der Startpunkte mit Zielpunkten durch ein Liniensegment (braun) verbindet, ohne dass eines dieser Segmente sich schneidet (rot), und gleichzeitig die kumulative Länge aller Segmente minimiert.

Mein erster Versuch in C++ war, alle möglichen Zustände zu permutieren, schnittstellenfreie Zustände zu finden und unter diesen den Zustand mit minimaler Gesamtsegmentlänge O (n!). Aber ich denke, dass es einen besseren Weg geben muss.

enter image description here

Jede Idee? Oder gute Keywords für die Suche?

Quelle

2012-03-25 deepmax

Vielleicht eine Art topologische Sortierung? –

Ich kenne die Antwort auch nicht, aber ich würde jede Lösung erstellen (Konflikte ignorieren) und dann den Konflikt einzeln lösen: Wenn zwei Zeilen kollidieren, scheint es, dass das Umschalten eines Paares von Endpunkten den Konflikt löst. Ich bin mir jedoch nicht sicher, wie ich den Fortschritt garantieren kann. –

@ DietmarKühl: Durch das Wechseln von Endpunkten kann ein anderer Konflikt angezeigt werden. –

Dies ist Minimum Euclidean Matching in 2D. Der Link enthält eine Bibliografie dessen, was über dieses Problem bekannt ist. Angesichts der Tatsache, dass Sie die Gesamtlänge minimieren möchten, ist die Non-Intersection-Einschränkung redundant, da die Länge eines Paars von Segmenten, die sich kreuzen, reduziert werden kann, indem sie nicht gekreuzt werden.

Quelle

2012-03-25 19:37:23 qq3

@ Walkerneo, es ist nicht über die Beine, weil der Abstand zwischen Ihren Füßen und der Abstand zwischen Ihren Hüften ist kürzer als die Länge Ihrer Beine. – zzzzBov

@ qq3: Streng genommen denke ich, dass dies * Bipartite * Minimum Euclidian Matching ist, eine Teilmenge in Ihrem Link erwähnt. – RBarryYoung

@dmckee: qq3 sagte, dass die nicht-schneidende Regel unter der minimalen Gesamtlängenbeschränkung * redundant war, nicht "in Konflikt" mit ihr (mathematisch sind das * sehr * verschiedene Dinge). Und für * Bipartite * -Probleme (die diese sind) sind lokal trennbare Verbesserungen auch immer global gültige Verbesserungen, so dass die lokale Längenüberschneidungsregel auch global gilt. (Ich bin mir nicht sicher, ob dies für die nicht-bipartiten Fälle gilt, Bipartite ist viel einfacher). – RBarryYoung

Sieht aus wie Sie könnten einen BSP-type Algorithmus verwenden.

Quelle

2012-03-25 19:11:50 Krumelur

Sie können zufällige Verbindung auswählen, dann jedes Mal ein Kreuz löschen (tatsächlich die Verbindung ihrer Endpunkte ändern), Dieser Algorithmus funktioniert und endet in endlichen Schritten. Sie können sagen, dass das Wechseln von Kreuzen zu einem neuen Kreuz führt, egal, jedes Mal, wenn Sie ein Kreuz wechseln, werden Sie die Gesamtlänge Ihrer Antwort minimieren und diese Art kann nicht unendlich sein (weil die Gesamtlänge der Linien endlich ist). Wirklich funktioniert in O (F * n^2) wo F= sum of all line segments * power of 10 (um es ganzzahlig zu machen). Dieses O ist sehr optimistisch, ich denke, wenn Sie diesen einfachen Algorithmus ausprobieren, wird es gut funktionieren. Sicher ist es sehr viel besser als rohe Gewalt im Allgemeinen.

Quelle

2012-03-25 22:14:42

@MasoudM. Ich bin mir 100% sicher, dass das Wechseln der Kreuze endlich aufhören wird (die Gesamtlänge nimmt ab). Wenn Sie sich um die Zeit kümmern (wie oft Sie das tun sollten), weil Ihr Programm auf endlichen Rechnern (PCs) läuft, haben sie nicht so etwas wie Epsilon (das sehr klein sein kann), ihre Genauigkeit ist vordefiniert (zum Beispiel) 30 Bit), so dass es bald abgeschlossen werden kann. Auch können Sie in jedem Schritt einige Heuristiken hinzufügen, um eine bessere Auswahl bei Änderungen zu haben. Ich schlage vor, Sie implementieren dies (Sie brauchen einige Basen in allen anderen Algorithmen wie das Finden von Kreuzungen und das Ändern einiger von ihnen sind in allen Algorithmen notwendig). –

Die Gesamtlänge nimmt ab, ist aber endlich, weil sie mindestens Null ist. –

@MasoudM. Eine nützliche Heuristik ist es, alle Konflikte in jedem Schritt zu finden und sie zu lösen, und dann erneut nach Konflikten zu suchen. Auch wenn Sie qq3's empfohlene Artikel lesen, werden Sie natürlich eine bessere Antwort erhalten. –

Verwenden dieses Algorithmus mit um O (n 3 ):

Hungarian algorithm sind ein kombinatorischer Optimierungsalgorithmus, den das das Zuordnungsproblem in polynomialer Zeit löst.

Wie kann es helfen? Nun, es wird nur minimale kumulative Länge finden. Aber ...

WENN DIE GESAMTLÄNGE MINIMAL IST, GIBT ES KEINE INTERSECTION.

So, wie @ QQ3 wobei der Schnittpunkt constraint redundant ist und nach dem Entfernen dieser Einschränkung kann die Reihenfolge von OS verringern (n!) zu O (n 3 ).

Quelle

2013-03-19 17:13:24 deepmax

nicht schneidende Liniensegmente, während die kumulative Länge

Antwort

Verwandte Themen