Znajdź optymalne zamówienie

Natknąłem się na ten problem i staram się znaleźć sposób, aby go rozwiązać. Jakiekolwiek propozycje będą mile widziane!

Załóżmy, że mamy matrycę $\{-1, 0, 1\}^{n\ \times\ k}$, na przykład,

$$\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ -1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & -1 \\ -1 & -1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & -1 \end{bmatrix}$$

Nie próbując każdej permutacji, znajdź porządek kolumn $c_i$ co maksymalizuje liczbę wierszy, dla których jest pierwszy niezerowy element $1$.

W powyższym przykładzie jednym z takich porządków (to nie jest wyjątkowe!) Jest $(c_3, c_4, c_1, c_2, c_5)$tzn.

Tutaj dla $4$ poza $5$ wiersze jest pierwszym niezerowym elementem $1$.

Ten problem, który nazywam CO przy porządkowaniu kolumn, jest trudny do rozwiązania . Oto redukcja z trudnego NP NP Vertex Cover (VC) do niego:

Formularze problemów decyzyjnych VC i CO

Niech wejściowa instancja VC będzie $(V, E, k)$. Reprezentuje pytanie: „Biorąc pod uwagę wykres$(V, E)$, czy można wybrać co najwyżej zestaw $k$ wierzchołki od $V$ tak, że każda krawędź $E$ jest incydent na co najmniej jednym wybranym wierzchołku? ”Zbudujemy instancję $(A, k')$ CO, które reprezentuje pytanie: „Biorąc pod uwagę macierz $A$ z elementami w $\{-1, 0, 1\}$, czy można permutować kolumny $A$ tak, że 1 pojawia się przed -1 co najmniej $k'$wiersze? ”Te dwa problemy są określone w formularzu problemu decyzyjnego , przy czym odpowiedź na każdy z nich brzmi TAK lub NIE: formalnie rzecz biorąc, jest to forma problemu NP-zupełna (lub nie). Nie jest zbyt trudne zobacz, że bardziej naturalna forma problemu optymalizacji podana w pytaniu PO jest w przybliżeniu równoważna pod względem złożoności: wyszukiwanie binarne parametru progu może być użyte do rozwiązania problemu optymalizacji za pomocą rozwiązania problemu decyzyjnego, a pojedyncze wywołanie rozwiązania problemu optymalizacji , a następnie pojedyncze porównanie, wystarczy, aby rozwiązać problem decyzyjny.

Konstruowanie instancji CO z instancji VC

Pozwolić $n=|V|$ i $m=|E|$. Zbudujemy macierz$A$ z $(n+1)m + n$ wiersze i $n+1$kolumny. Szczyt$(n+1)m$ zostaną utworzone rzędy $m$ bloki $n+1$rzędy, przy czym każdy blok reprezentuje krawędź, którą należy zakryć . Dół$n$ wiersze zawierają „flagi” wierzchołków, co spowoduje, że kolumna (odpowiadająca wierzchołkowi) poniesie stały koszt, jeśli zostanie uwzględniona po lewej stronie rozwiązania CO (odpowiadającego wierzchołkowi objętemu pokrywą wierzchołków Rozwiązanie VC).

Dla każdego wierzchołka $v_i$, utwórz kolumnę, w której:

• wśród najlepszych $(n+1)m$ rzędy, $j$-ty blok $n+1$ wszystkie wiersze zawierają +1, gdy krawędź $e_j$ jest incydent na $v_i$, i 0 w przeciwnym razie, i
• dół $n$ wszystkie wiersze mają wartość 0, z wyjątkiem $i$-ty, który wynosi -1.

Utwórz jeszcze jedną kolumnę „ogrodzenia”, która się składa $(n+1)m$ kopie -1, a następnie $n$ kopie +1.

Na koniec ustaw próg $k'$ dla skonstruowanej instancji CO: $(n+1)m + n - k$. Innymi słowy, zezwalamy co najwyżej$k$wiersze, w których -1 pojawia się przed +1. Nazwijmy tę liczbę naruszających wiersze „kosztem” rozwiązania CO.

Dowód

Odpowiednikiem między rozwiązaniem instancji CO a zestawem wierzchołków w oryginalnej instancji VC jest: Każda kolumna po lewej stronie ogrodzenia odpowiada wierzchołkowi znajdującemu się w zestawie, a każda kolumna po prawej stronie ogrodzenia odpowiada wierzchołek, który nie jest.

Intuicyjnie, -1s na górze kolumny „ogrodzenia” wymuszają wybór podzbioru kolumn, które mają być umieszczone po jego lewej stronie, które razem zawierają + 1 we wszystkich tych pozycjach - odpowiadających podzbiorowi wierzchołków, które padają na każdym krawędź. Każda z tych kolumn, która pojawia się po lewej stronie „ogrodzenia”, ma -1 w odrębnym rzędzie gdzieś na dole$n$wiersze, ponosząc koszt 1; +1 w dolnej części „ogrodzenia” zapewniają, że wszystkie kolumny umieszczone po jego prawej stronie nie poniosą takich kosztów.

Najwyraźniej rozwiązanie VC wykorzystujące co najwyżej $k$ wierzchołki dają rozwiązanie dla skonstruowanego wystąpienia CO przy maksymalnym koszcie $k$: Wystarczy dowolnie zamówić kolumny odpowiadające wierzchołkom w pokrywie wierzchołków, następnie kolumnę ogrodzenia, a następnie wszystkie pozostałe kolumny w dowolnej kolejności.

Pozostaje pokazać, że rozwiązanie dla instancji CO ma co najwyżej koszt $k$ odpowiada najwyżej osłonie wierzchołka $k$ wierzchołki.

Załóżmy wręcz przeciwnie, że istnieje rozwiązanie dla instancji CO z najwyżej kosztami $k$ który pozostawia jakiś rząd na górze $(n+1)m$wiersze z -1 przed +1. Ten wiersz należy do bloku$(n+1)$ rzędy odpowiadające konkretnej krawędzi $uv$. Każdy wiersz w tym bloku w oryginalnej instancji$A$jest identyczny pod względem budowy; permutowanie kolumn może zmienić te wiersze, ale nie wpływa to na fakt, że są one identyczne. Tak więc każdy z nich$n+1$ identyczne rzędy mają -1 przed +1 w rozwiązaniu, co oznacza koszt co najmniej $n+1$. Ale$k \le n < n+1$: sprzeczność.

Ponieważ każdy z $m$ bloki rzędów u góry $(n+1)m$rzędy mają +1 przed -1, każda z odpowiednich krawędzi jest pokryta wierzchołkiem odpowiadającym kolumnie po lewej stronie ogrodzenia: to znaczy ten podzbiór wierzchołków stanowi pokrycie wierzchołków. Ponieważ żaden z najlepszych$(n+1)m$ rzędy mają -1 przed +1, jedynym miejscem, w którym koszty mogą narastać w rozwiązaniu, jest na dole $n$rzędy, od kolumn umieszczonych na lewo od ogrodzenia. Każda taka kolumna kosztuje dokładnie 1, więc biorąc pod uwagę, że koszt jest co najwyżej$k$, musi być co najwyżej $k$ takie kolumny i co najwyżej $k$ wierzchołki w okładce.

Wreszcie, jasne jest, że instancja CO może być konstruowana w czasie wielomianowym z instancji VC, co oznacza, że ​​gdyby istniał algorytm wielomianowy do rozwiązywania CO, dowolna instancja VC mogłaby być również rozwiązana w czasie wielomianowym, najpierw konstruując instancję CO zgodnie z opisem powyżej, a następnie rozwiązanie. Ponieważ VC jest trudne dla NP, również CO.

Nie wiem, czy rzeczywiście istnieje rozwiązanie wielomianowe. Niemniej jednak w oparciu o komentarz Pål GD można zbudować funkcję uproszczenia. Macierz początkowa jest uproszczona podczas budowania sekwencji wyjściowej$S$.

function simplification:
while(true)
    if any row i$ has no 1 or no -1 left, remove it
    if any column j has no -1 then,
       remove it and put j on the leftmost available position in S,
       remove all rows where column j has 1.
    if any column j has no 1 then, 
       remove it and put j on the rightmost available position in S.
    if no modification has been done on this loop, break

Następnie musisz przeprowadzić pełne badanie kombinatoryki, używając iteracyjnie wyboru funkcji:

function pick(k):
    put column k on the leftmost available position in S
    remove any row where column k is -1 or 1

Po każdym wyborze możesz dokonać uproszczenia, aby ewentualnie zmniejszyć liczbę możliwości eksploracji. Sugeruję eksplorację chciwie, zaczynając od kolumny mającej mniej -1, więc możesz osiągnąć dolną granicę, stawiając kryterium zatrzymania.

W podanym przykładzie pierwsze uproszczenie daje (jak wyjaśnił Pål GD w komentarzu)

• $S[0] = c3$usuń r1, r3
• $S[1] = c4$usuń r4
• $S[2] = c2$ pozwala to na przeglądanie prostej matrycy. $$\begin{bmatrix} -1 & 1 \\ 1 & -1 \\ \end{bmatrix}$$

Myślę, że matryca powodująca, że ​​ta metoda jest dość nieefektywna, miałaby dokładnie jeden 1, a jeden -1 na wiersz / kolumnę, coś w rodzaju

Niemniej uproszczenie wciąż oszczędza około połowy etapów eksploracji. Ten typ macierzy można podzielić na kilka niezależnych podmacierzy.