Złożoność problemu z siecią przełączników

Sieć przełączników (nazwa została wymyślona) składa się z trzech typów węzłów:

• jeden węzeł początkowy
• jeden węzeł końcowy
• jeden lub więcej węzłów Switch

Węzeł przełączający ma 3 wyjścia: lewy, górny, prawy; ma dwa stany L i R oraz stan docelowy TL lub TR . Do każdego przełącznika można przejść zgodnie z następującymi zasadami:

• zawsze od lewej do góry; stan przełącznika zmienia się na L
• zawsze od prawej do góry; stan przełącznika zmienia się na R.
• od góry do lewej tylko wtedy, gdy przełącznik znajduje się w stanie L; stan się nie zmienia
• od Up to Right, jeśli przełącznik jest w stanie R; stan się nie zmienia
• nigdy od lewej do prawej lub od prawej do lewej

Rysunek 1. Przełącz węzeł w stan L ze stanem docelowym TR

Te właściwości obejmują również:

• 0, 1 lub 2 wyjścia przełącznika mogą być izolowane (niepodłączone do innego przełącznika);
• ścieżka może po prostu „dotknąć” przełącznika, aby zmienić jego stan: wejść z lewej i wyjść z lewej lub wejść z prawej i wyjść z prawej;
• nie ma ograniczeń co do liczby przejść / dotknięć przełącznika.

Problemem decyzyjnym jest: „Czy istnieje ścieżka od węzła początkowego do węzła końcowego, tak że wszystkie końcowe stany przełączników są zgodne z odpowiednim stanem docelowym?”

Oczywiście wszystkie przełączniki, które początkowo nie są w stanie docelowym, muszą zostać przemierzone (lub dotknięte) przynajmniej raz;

To jest szybkie narysowanie trywialnej sieci (wykonanej za pomocą Excela ... zrobię lepszą):

Trywialne rozwiązania to:

S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

EDYCJA 2:

1. Czy ten problem jest znany? ---> dałeś mi dobre odniesienie do tezy Hearn'a (wykresy ograniczeń);

$NPSPACE = PSPACE$

$\mathsf{NP}$

$\mathsf{NP\text{-}complete}$

Problem jest co najmniej trudny NP, przez redukcję z 3-SAT.

Najpierw rozważ problem ze znalezieniem ścieżki od początku do wyjścia z następującego ukierunkowanego wykresu, z tym, że żadna ścieżka nie może odwiedzić wszystkich trzech (kwadratowych) węzłów klauzuli:

$(X1 \lor X2 \lor X3)\land(X1\lor\neg X2\lor X4)$

Przekształcamy te wykresy w sieć przełączników. Do tego używamy trzech gadżetów:

1. Każdy węzeł okręgu i krawędź dwukierunkowa staje się Drutem , tworząc połączenia między przełącznikami.
2. Każda ukierunkowana krawędź staje się gadżetem Jednokierunkowym składającym się z jednego przełącznika (patrz poniżej).
3. Każdy kwadratowy węzeł reprezentuje jeden z trzech przełączników, które są częścią gadżetu Klauzula (patrz poniżej).

Na poniższych ilustracjach przełączniki są rysowane jako dwie przychodzące strzałki, z których jedna jest przerywana (wyłączona). Kierunek docelowy jest rysowany za pomocą czarnego koła (tak, aby stała strzałka musiała ostatecznie znajdować się z boku koła).

Uwaga: Pogrubioną czcionką użyjemy do odróżnienia wyjścia wykresu od wyjść gadżetów.

$A$$B$$B$$A$$X1$$X2$$X3$$X1'$$X2'$$X3'$ .

Przypomnijmy, że dla oryginalnego wykresu znalezienie ścieżki, która prowadziła do wyjścia i nie odwiedziła wszystkich trzech kwadratowych węzłów jakiejkolwiek klauzuli, była NP-zupełna. Teraz rozważ problem dotarcia do wyjścia z transformowanego wykresu bez martwienia się o docelowe pozycje przełączników.

Zauważ, że każda ścieżka, która jest rozwiązaniem pierwotnego problemu z grafem, jest również rozwiązaniem dla transformowanego wykresu. Załóżmy więc, że ścieżka dla przekształconego wykresu nie jest rozwiązaniem dla oryginalnego wykresu. Może się to zdarzyć w dwóch przypadkach:

1. $B$$A$
2. Ścieżka przecina wszystkie trzy ścieżki jakiegoś gadżetu Klauzula .

W pierwszym przypadku gadżet jednokierunkowy musiał najpierw przejść w zamierzonym kierunku, w którym to przypadku równie dobrze można by uniknąć przejścia przez niego.

Rozważmy więc drugi przypadek, w którym ścieżka przemierza wszystkie trzy przełączniki jakiegoś gadżetu Klauzula . Wtedy ten gadżet będzie miał wszystkie trzy przełączniki odwrócone (patrz poniżej). Tutaj wykorzystujemy pozycje docelowe. Zauważ, że szary szkielet z klauzulą gadżet nie może zostać osiągnięty, co oznacza, że przełączniki nie mogą już być kierowane do ich położeń docelowych. W takim przypadku mówimy, że tego gadżetu Klauzuli nie można odzyskać.

Pozostaje pokazać, że dla dowolnego rozwiązania pierwotnego problemu graficznego przełączniki transformowanego wykresu można ustawić w ich położeniu docelowym. W tym celu wykorzystujemy fakt, że do drutu wyjściowego można dotrzeć tylko wtedy, gdy istnieje rozwiązanie, lub niektóre gadżety z klauzulami stają się niemożliwe do odzyskania.

Aby umieścić przełączniki w ich pozycji docelowej, możemy teraz dodać dodatkowe gadżety jednokierunkowe z drutu wyjściowego do wejścia każdego istniejącego gadżetu jednokierunkowego , a także do trzech drutów wyjściowych wszystkich gadżetów klauzuli . Następnie, gdy token dotrze do wyjścia , można przejść wszystkie dodatkowe gadżety jednokierunkowe (a tym samym umieścić je w pozycji docelowej), a także ustawić pozostałe przełączniki w pozycjach docelowych (chyba że istnieje klauzula niemożliwa do odzyskania). Wreszcie token może powrócić do wyjścia, a łamigłówka zostanie rozwiązana.

Należy zauważyć, że gadżety Klauzuli można odzyskać tylko wtedy, gdy zostaną wprowadzone z nienaprawionego wyjścia; a ze względu na gadżety jednokierunkowe umieszczone między gadżetami Klauzula a następną zmienną, nie może się to zdarzyć, dopóki nie zostanie osiągnięty drut wyjścia .

Stąd problem sieci przełączników jest trudny NP.

Nadal nie jest jasne, czy problem dotyczy NP, czy PSPACE. Redukcja twardości NP budująca planarną sieć przełączników będzie miała wielkie implikacje dla ograniczonych wariantów Sokoban, ponieważ wszystkie przełączniki są równoważne z gadżetem Sokoban poniżej.