Najkrótsza nie przecinająca się ścieżka dla wykresu osadzonego w płaszczyźnie euklidesowej (2D)

Jakiego algorytmu użyłbyś do znalezienia najkrótszej ścieżki wykresu, która jest osadzona w płaszczyźnie euklidesowej, tak aby ścieżka nie zawierała żadnych skrzyżowań własnych (w osadzaniu)?

Na przykład na poniższym wykresie chcesz przejść z . Zwykle algorytm taki jak algorytm Dijkstry tworzyłby następującą sekwencję:$(0,0) \rightarrow (-3,2)$

Pełny wykres:

Najkrótsza droga:

Najkrótsza nie przecinająca się ścieżka:

Jednak ta ścieżka przecina się na płaszczyźnie euklidesowej, dlatego chcę algorytmu, który dałby mi najkrótszą nie przecinającą się sekwencję, w tym przypadku:

Ta ścieżka jest dłuższa niż najkrótsza, ale jest najkrótszą nie przecinającą się ścieżką.

Czy istnieje (wydajny) algorytm, który może to zrobić?

Źródła TikZ

• Pełny wykres .
• Najkrótsza ścieżka .
• Najkrótsza nie przecinająca się ścieżka .

Uzupełnienie NP pozwala nawet zdecydować, czy istnieje jakaś ścieżka.

Jest oczywiście możliwe sprawdzenie, czy dana ścieżka jest prawidłową ścieżką na danym wykresie. Zatem problem ograniczonej długości występuje w NP, podobnie jak jego podzbiór, problem dowolnej ścieżki.

Teraz, aby udowodnić twardość NP dla problemu dowolnej ścieżki (a zatem problemu o ograniczonej długości), zredukujmy SAT-CNF do tego problemu:

Globalna struktura to siatka kawałków drutu połączona z kolumną kawałków klauzuli. Formuła logiczna jest zadowalająca, jeśli na wykresie istnieje nieprzecinająca się ścieżka.

Nie można przekroczyć dwóch elementów ścieżki, ale konieczne jest skrzyżowanie dwóch przewodów logicznych. Przepływ ścieżki jest raczej ściśle podany: punkt drutu jest podawany przez dwa węzły. Kolejność punktów drutu, przez które przechodzi ścieżka, jest wymuszona przez redukcję. Logika jest reprezentowana przez wybrany węzeł. Można wybrać dowolną ścieżkę, o ile przechodzi ona przez wszystkie punkty drutowe.

Na tym schemacie ścieżka jest reprezentowana przez czerwoną krzywą, a przepływ logiczny reprezentowany jest przez czarne przewody:

Teraz zbudujmy każdy komponent.

Okablowanie wykorzystuje trzy kafelki: skrzyżowanie, punkt rozgałęzienia i drut pionowy. Zacznijmy od najtrudniejszego:

Podstawową ideą skrzyżowania jest przygotowanie ścieżki dla każdej pary punktów drutowych i wygięcie możliwych ścieżek na tyle, aby wszystkie pary oprócz tych, które kodują tę samą logikę (kompatybilne ścieżki) krzyżowały się. Oczywiście nie możemy po prostu powiedzieć, że przecinają się dwie równoległe krawędzie, ale możemy wprowadzić dodatkowe 2-rzędowe węzły, aby przeciąć dwie ścieżki.

Zakładając, że ścieżki prowadzą z północy na zachód i z południa na wschód, możemy: zebrać każdą ścieżkę z północy za pomocą kompatybilnej ścieżki ze wschodu na linii (niektóre niekompatybilne ścieżki będą się krzyżować); krzyżuj każdą parę ze sobą, odwracając kolejność par; rozłóż ścieżki do ich południowych i zachodnich punktów końcowych. Można to najlepiej wyjaśnić za pomocą diagramu. Tutaj każda para węzłów reprezentuje punkt drutu. Ścieżki o tym samym kodzie kolorów (o tej samej logice) nie przecinają się, ścieżki o innym kodzie kolorów:

Punkt rozgałęzienia i drut pionowy działają tak samo, ale istnieje mniej ścieżek do korelacji:

$\neg A \vee \neg B$

Możliwe jest uogólnienie tej redukcji w celu zakodowania dowolnego drzewa bramek AND i OR poprzez rozgałęzienie drutu czytającego w różny sposób. W szczególności SAT-CNF i SAT-DNF są możliwe do zredukowania do problemu ścieżki nie przecinającej się w sposób opisany powyżej.

problem wydaje się do tej pory Turan 1944. wygląda to na dobrą analizę teorii i algorytmów, Crossing Number of Graphs: Theory and Computation autorstwa Mutzela. wikipedia ma kilka informacji pod przekraczającą liczbą wykresów