Verbinde Punkte von Set in den Liniensegmenten

Ich würde mit einer Delaunay-Triangulation des Punktsatzes beginnen. Dies sollte Ihnen bereits die nächsten Nachbarverbindungen von jedem Punkt ohne Überschneidungen geben. Im nächsten Schritt würde ich mir die Dreiecke ansehen, die sich aus der Triangulation ergeben. Die praktische Eigenschaft ist, dass Sie basierend auf Ihrem Regelwerk genau eine Seite aus jedem Dreieck auswählen und die restlichen zwei aus der Auswahl entfernen können.

Das Problem, das jetzt noch besteht, besteht darin, jene Kanten zu wählen, die Ihnen die kleinste Summe geben, die natürlich nicht immer die kleinste Seite ist, da diese bereits durch ein benachbartes Dreieck blockiert worden sein könnte. Ich würde mit einem gierigen Ansatz beginnen und immer die kleinste verbleibende Kante auswählen, die noch nicht von benachbarten Dreiecken blockiert wurde.

Bearbeiten: Im nächsten Schritt rufen Sie eine Liste aller Kanten in dieser Triangulation ab und sortieren sie nach Länge. Sie machen auch eine andere Liste, in der Sie die Anzahl der Verbindungen zählen, die jeder Punkt hat. Sie durchlaufen nun die Kantenliste von der längsten zur kürzesten Kante und überprüfen die beiden Punkte, die sie in der Verbindungszählungsliste verbindet: Wenn jeder der Punkte mehr als eine Verbindung hat, können Sie die Kante verwerfen und die Kante dekrementieren Verbindungsanzahl für die zwei beteiligten Punkte. Wenn mindestens einer der Punkte nur noch eine Verbindung hat, haben Sie sich eine der Kanten, die Sie suchen. Du wiederholst den Prozess, bis keine Kanten mehr übrig sind, und das sollte dir hoffentlich die kleinste mögliche Kantensumme geben.

Wenn ich mich nicht irre, ist dieses Problem mit dem Rucksackproblem verbunden, das NP-Hard ist, also bin ich mir nicht sicher, ob diese Lösung Ihnen wirklich das bestmögliche gibt.

Ich würde sagen, dass dies eine Erweiterung des bekannten traveling salesman problem ist.

Eine gute Technik (wenn auch etwas altmodisch) ist die Simulated Annealing Optimierungstechnik.

Sie müssen Anpassungen an der Kostenfunktion vornehmen (a.k.a. objective ), um Abschnitte des Pfades zu verpassen. Bei einem kontinuierlichen Kandidatenpfad ist es jedoch eher trivial, zu entscheiden, welche Abschnitte zu vernachlässigen sind, um die Länge zu minimieren. (Sie entfernen zuerst die längeren der Schnittlinien).

Wow, das ist eine schwierige Frage. Das sind viele Bedingungen, die erfüllt werden müssen.

Ich denke, vom Standpunkt der Programmierung aus könnte die "einfachste" Lösung tatsächlich darin bestehen, einfach alle Möglichkeiten zu durchlaufen, die die letzten 3 Bedingungen erfüllen, und die Gesamtlänge aufzuzeichnen, während man durchgeht die kürzeste Länge am Ende - Brute Force, rate-and-check. Ich denke, das ist das, worauf Sie in Ihrem OP hingewiesen haben, als Sie von einer "schwungvollen Linie und dem Aufbau eines Baumes aller Möglichkeiten" gesprochen haben. Dieser Ansatz ist sehr rechenintensiv, aber wenn der Code richtig geschrieben wird, sollte er immer am Ende funktionieren.

Wenn Sie die "beste" Lösung haben wollen, wo Sie nur für die einzelne endgültige Antwort sofort lösen möchten, fürchte ich, dass meine mathematischen Fähigkeiten dafür nicht stark genug sind - ich bin nicht einmal sicher, ob es dort ist jede einzelne analytische Lösung für dieses Problem für eine beliebige Sammlung von Punkten. Vielleicht versuchen Sie es mit den Leuten bei MathOverflow . Wenn jemand da drüben mit der Mathematik hinter dieser Berechnung erklären kann, und Sie dann immer noch Hilfe benötigen, um diese Mathematik in Code in einer bestimmten Programmiersprache zu konvertieren, aktualisieren Sie Ihre Frage hier (vielleicht mit einem Link zu der Antwort, die sie Ihnen zur Verfügung stellen) Ich bin mir sicher, dass Ihnen jemand von diesem Punkt aus helfen kann.

Eine der möglichen Lösungen ist die Graphentheorie.

Konstruiere einen zweiteiligen Graphen G, so dass jeder Punkt seine Kopie in beiden Teilen hat. Legen Sie nun die Kanten zwischen den Punkten i and j und weight = i == j ? infinity : distance[i][j] . Die minimale maximale Gewichtung in der Grafik entspricht der von Ihnen gewünschten Konfiguration.

Beachten Sie, dass sich die resultierenden "Kanten" der Übereinstimmung nicht schneiden, da sich diese auf einer euklidischen 2D-Ebene befinden. Nehmen wir an, die Kanten AB und XY schneiden sich für die Punkte A, B, X, Y . Dann ist die Anpassung nicht vom minimalen Gewicht, weil entweder AX, BY oder AY, BX ein kleineres Gesamtgewicht ohne einen Schnittpunkt erzeugen wird (dies kommt von der Dreiecksungleichung a + b & gt; c)