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


14

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)(-3),2))

[(0,0)3)(0,3))2)(1,2))4(-3),2))]=7+2).

Pełny wykres:

wprowadź opis zdjęcia tutaj

Najkrótsza droga:

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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:

[(0,0)3)(0,3))3)(0,6)5(-3),2))]=11

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


2
Niezły problem! (+1). Czy możesz powiedzieć coś o aplikacji lub kontekście, w którym pojawia się ten problem? Jestem zaintrygowany. (PS Na osobnej uwadze: Oczywistym wyjściem z tej zagadki jest sprawdzenie, czy możesz wprowadzić nowy wierzchołek dla każdego punktu przecięcia, tj. Każdego punktu, w którym jedna krawędź może przecinać drugą krawędź. Zdaję sobie jednak sprawę z tego, że w niektórych / wielu zastosowaniach może to nie być możliwe.)
DW

2
@DW to ja przeformułowuję źle sformułowany problem Babibu z płonącym osłem / kucykiem ; aplikacja jest jego heurystycznym algorytmem euklidesowym TSP, nie jestem do końca pewien, jak zamierza go użyć, ale wyobrażam sobie, że chce wiedzieć, czy uda mu się znaleźć ścieżkę między dwoma punktami, kiedy odwiedził już kilka innych (optymalna trasa Euclidean TSP nie przecinają się). I tak, jeśli możesz wprowadzić nowe węzły, byłoby świetnie, ale pytanie brzmi, czy nie możesz (i oczywiście nie możesz wprowadzić nowych miast dla Euclidean TSP).
Realz Slaw

1
Pozwól mi spróbować przekonwertować problem istnienia ścieżki na 3SAT. Największym wyzwaniem jest przejście przez dwa sygnały bez przecinania dwóch ścieżek.
John Dvorak

1
Tak. Chciałem przez to rozwiązać SAT.
John Dvorak

2
n

Odpowiedzi:


11

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:

siatka drutów po lewej, kolumna fragmentów klauzuli po prawej.

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:

graficzne przedstawienie powyższego

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

wystarczą tutaj dwie pary ścieżek.  Drut jest zasadniczo punktem rozgałęzienia ze zniszczoną gałęzią

¬ZA¬b

wprowadź opis zdjęcia tutaj

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.


Wow, dobra robota. Jeszcze go nie sprawdziłem, ale praca, którą włożyłeś, jest niesamowita.
Realz Slaw

OK, chcę tylko podsumować moje zrozumienie: za pomocą pierwszego gadżetu można przekroczyć dowolne dwie pary literalno-ścieżkowe i zachować używane ścieżki. Dlatego nie trzeba martwić się o płaskość przy układaniu ścieżek (podobnie jak gadżet Xor w PlanarCircuitSat dla obwodów). Następnie za pomocą ostatniego gadżetu można utworzyć dowolne klauzule logiczne (nie martwiąc się o płaskość). Czy to jest poprawne?
Realz Slaw

Wydaje się to poprawne, ale dla ogólnego układu musisz zapewnić dwie rzeczy: że możesz zasilać wszystkie gadżety ścieżką NIP (zawsze powinno to być możliwe - jeśli ścieżka utknie w środku, możesz wprowadzić gadżety przewodowe do połącz samotne końce ścieżki) i aby wszystkie ścieżki w drucie czytającym krzyżowały się ze sobą w taki sposób, że nie ma możliwości cofnięcia się w obrębie drutu (wydaje mi się, że jest zagwarantowane, jeśli nie ma prawdziwych klauzul ( nie przekraczając żadnego literału) i jeśli wszystkie klauzule znajdują się na zewnątrz obwodu (na tej samej powierzchni znajdują się początek i koniec).
John Dvorak

upewnienie się, że wszystkie ścieżki w przewodzie odczytu przecinają się, jest łatwe - jeśli chcesz mieć pewność, po prostu rozgałęź n ścieżek, a następnie skrzyżuj je wszystkie od razu. Myślę jednak, że nigdy nie jest to konieczne.
John Dvorak

1
Użyłem OpenOffice Draw dla globalnej struktury, a [yEd] (www.yworks.com/products/yed) dla reszty. Czy powinienem to edytować w (z <sub>)?
John Dvorak

-1

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


1
Może to lepiej jako komentarz?
Juho

naukowo odpowiada na podstawowe pytanie „jakiego algorytmu byś użył”
wer 22'13

1
Chociaż teoretycznie może to odpowiedzieć na pytanie, lepiej byłoby zawrzeć tutaj istotne części odpowiedzi i podać odnośnik.
John Dvorak

jan przytacza ref z stackexchange meta. chociaż jest to słuszny pomysł, rola cytatów w nauce / matematyce jest inna niż strona ze wskazówkami programistycznymi .... [co prawda referencje nie są dla mnie dostępne w celu uzyskania bardziej szczegółowej odpowiedzi] .. w każdym razie jest całkiem możliwe, że coś w rodzaju jans construction, choć użyteczny / wartościowy, jest już w literaturze i nauce, jest częścią standardowego procesu / najlepszych praktyk, aby [spróbować] go zlokalizować ....
dniu
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.