Kürzester nicht schneidender Pfad für einen in eine euklidische Ebene eingebetteten Graphen (2D)

Welchen Algorithmus würden Sie verwenden, um den kürzesten Pfad eines Graphen zu finden, der in eine euklidische Ebene eingebettet ist, sodass der Pfad keine Selbstschnittpunkte enthalten sollte (in der Einbettung)?

In der folgenden Grafik möchten Sie beispielsweise von . Normalerweise würde ein Algorithmus wie der von Dijkstra eine Sequenz erzeugen wie:$(0,0) \rightarrow (-3,2)$

Vollständige Grafik:

Kürzester Weg:

Kürzester nicht kreuzender Weg:

Doch selbst dieser Weg kreuzt auf der euklidischen Ebene, also ich mag einen Algorithmus, den mir die kürzeste nicht schneidende Sequenz, in diesem Fall geben würde:

Dieser Pfad ist länger als der kürzeste Pfad, aber er ist der kürzeste nicht kreuzende Pfad.

Gibt es einen (effizienten) Algorithmus, der das kann?

TikZ-Quellen

• Vollständiges Diagramm .
• Kürzester Weg .
• Kürzester nicht kreuzender Pfad .

Es ist NP-vollständig, selbst zu entscheiden, ob ein Pfad existiert.

Es ist eindeutig möglich, zu überprüfen, ob ein bestimmter Pfad in der angegebenen Grafik gültig ist. Somit liegt das Problem der begrenzten Länge in NP, und ebenso die Teilmenge, das Any-Path-Problem.

Um nun die NP-Härte des Any-Path-Problems (und damit des Bounded-Length-Problems) zu beweisen, reduzieren wir SAT-CNF auf dieses Problem:

Die globale Struktur ist ein Gitter von Drahtstücken, an das eine Spalte von Satzstücken anschließt. Die Logikformel ist erfüllbar, wenn ein sich nicht schneidender Pfad durch das Diagramm vorhanden ist.

Es ist unmöglich, zwei Teile des Pfades zu kreuzen, es ist jedoch erforderlich, zwei Logikdrähte zu kreuzen. Vielmehr ist der Pfadfluss streng gegeben: Ein Drahtpunkt wird durch zwei Knoten gegeben. Die Reihenfolge der Drahtpunkte, durch die der Pfad verläuft, wird durch die Reduzierung erzwungen. Die Logik wird durch den ausgewählten Knoten dargestellt. Jeder Pfad kann ausgewählt werden, solange er alle Drahtpunkte durchläuft.

In diesem Diagramm wird der Pfad durch die rote Kurve und der logische Ablauf durch die schwarzen Drähte dargestellt:

Lassen Sie uns nun jede Komponente erstellen.

Bei der Verdrahtung werden drei Kacheln verwendet: die Kreuzung, der Verzweigungspunkt und der vertikale Draht. Beginnen wir mit dem schwierigsten:

Die Grundidee hinter der Kreuzung besteht darin, einen Pfad für jedes Paar von Drahtpunkten zu erstellen und die möglichen Pfade so weit zu biegen, dass sich alle Paare mit Ausnahme derjenigen, die dieselbe Logik (kompatible Pfade) codieren, kreuzen. Natürlich können wir nicht einfach sagen, dass sich zwei parallele Kanten schneiden, sondern wir können zusätzliche Knoten der Ordnung 2 einführen, damit sich zwei Pfade schneiden.

Angenommen, die Pfade kommen von Norden nach Westen und von Süden nach Osten, dann können wir: jeden Pfad von Norden mit seinem kompatiblen Pfad von Osten auf einer Linie zusammenfassen (einige inkompatible Pfade kreuzen sich); Kreuzen Sie jedes Paar miteinander, indem Sie die Reihenfolge der Paare umkehren. Verteilen Sie die Pfade auf ihre Süd- und Westendpunkte. Dies lässt sich am besten anhand eines Diagramms erklären. Hier repräsentiert jedes Knotenpaar einen Drahtpunkt. Pfade mit dem gleichen Farbcode (mit der gleichen Logik) kreuzen sich nicht, Pfade mit einem anderen Farbcode tun dies:

Der Verzweigungspunkt und der vertikale Draht funktionieren gleich, es sind jedoch weniger Pfade zu korrelieren:

$\neg A \vee \neg B$

Es ist möglich, diese Reduktion zu verallgemeinern, um einen beliebigen Baum von UND- und ODER-Gattern zu codieren, indem der Lesedraht auf unterschiedliche Weise verzweigt wird. Insbesondere können sowohl SAT-CNF als auch SAT-DNF auf die oben beschriebene Art und Weise auf das Problem des nicht schneidenden Pfades reduziert werden.

Das Problem scheint auf Turan 1944 zu datieren. Dies scheint eine gute Übersicht über Theorie und Algorithmen zu sein, die Crossing Number of Graphs: Theorie und Berechnung von Mutzel. wikipedia hat einige infos unter kreuzung der anzahl von diagrammen