Pokrycie siatki prostokątami

Mamy siatkę . Mamy zbiór prostokątów na tej siatki, każdy prostokąta może być przedstawiony jako -by- binarna matryca . Chcemy pokryć siatkę tymi prostokątami. $N_1 \times N_2$ $N_1$ $N_2$ $R$

Czy wersja decyzyjna tego zestawu obejmuje problem NP-zupełny?

Dane wejściowe: Collection prostokątów na siatce (rozmiar wejściowy: ) i $\mathcal{C}=\{R_1,R_2,\dots,R_L\}$ $N_1N_2L$ $K \in \mathbb{N}^+$
Dane wyjściowe: Podzbiór z i zawierający dla każdej komórki co najmniej jeden prostokąt ją pokrywający. $\mathcal{S}\subset\mathcal{C}$ $|\mathcal{S}|\leq K$ $\mathcal{S}$

Odkryłem, że przypadek 1D ( ) można rozwiązać w czasie wielomianowym za pomocą programowania dynamicznego: każda optymalna osłona będzie połączeniem $N_2=1$

optymalne pokrycie niektórych podproblemów obejmujących pierwsze komórki . $N_1-n_1$
prostokąt 1D, tj. odstęp, obejmujący pozostałe komórki . $n_1$

Nie sądzę jednak, że DP może działać w przypadku problemu 2D: w przypadku problemu 1D masz problemy do rozwiązania, ale w przypadku 2D masz (liczba sieci północno-wschodniej ścieżki na siatce). $N_1$ $\binom{N_1+N_2}{N_2}$

Myślę, że problemem może być NP, ale nie jestem pewien (choć wydaje się trudniejszy niż P) i nie udało mi się znaleźć wielomianowej redukcji z powodu problemu NP-zupełnego (3-SAT, Cover Vertex ...)

Każda pomoc lub podpowiedź jest mile widziana.

complexity-theory np-complete set-cover

— Yann
źródło

Podpowiedź: poszukaj redukcji z Cover Vertex, w której tworzymyautor:siatka bloków, z których każdy jest blokiem elementów matrycy 3 na 3. Każdy rząd bloków odpowiada krawędzi i będzie zawierał 2 specjalnie zaprojektowane bloki odpowiadające wierzchołkom punktu końcowego. Dla każdego wierzchołka będzie wysokość -, prostokąt o szerokości 1, który przechodzi przez środkową kolumnę kolumny bloków 3 na 3 odpowiadających temu wierzchołkowi. Jak zmusić sumę dowolnej ważnej ochrony -vertex do kosztu dokładnie ? (Potrzebne będą inne prostokąty).

| E |

$|E|$

| V |

$|V|$

3 | E |

$3|E|$

k

$k$

| E | (| V | + 3) + k

$|E|(|V|+3)+k$

— j_random_hacker

Myślę, że jest to prawdopodobnie zadanie domowe, więc trochę niechętnie mówię o wiele więcej. Podana przeze mnie formuła kosztów zawiera pewne wskazówki. Pamiętaj, że możesz wymusić co najmniej 1 z kilku prostokątów, czyniąc je jedynymi prostokątami pokrywającymi jakiś element macierzy (przydatny jest także specjalny przypadek 1 prostokąta). FWIW, próbowałem też użyć-by-najpierw siatka, w której wybranie wierzchołka odpowiadałoby „przekreśleniu” wiersza i odpowiedniej kolumny, ale nie udało się ustalić, jak wymusić wybranie tej kolumny, gdy wybierany jest ty rząd, i odwrotnie.

| V |

$|V|$

| V |

$|V|$

i

$i$

i

$i$

— j_random_hacker

Miałem ten sam problem z-by-krata. Myślę, że rozumiem, jakie rozwiązanie masz na myśli (chociaż nie mam dokładnie takiej samej formuły kosztów), zobacz moją edycję. Nawiasem mówiąc, nie jest to zadanie domowe. Jest to problem kombinatoryczny, który pojawił się w prawdziwym problemie inżynieryjnym. Rozwiązujemy go za pomocą MIP, ale chciałem mieć pewność, że problemem był NP (i nie miałem rozwiązania wielomianowego). W każdym razie, jeśli potwierdzisz, że rozwiązanie jest prawidłowe, możesz podać podpowiedź jako odpowiedź, a ja ją zweryfikuję (ponieważ znalazłem rozwiązanie z twoją pomocą).

| V |

$|V|$

| V |

$|V|$

— Yann

Tak, to prawie dokładnie to, co miałem na myśli! :) Tworzyłem twoje prostokąty „typu 4” nieco dłużej na jednym końcu: tam gdzie twoje zajmują 2 komórki w bloku, moje zajmują wszystkie 3. Zamiast specjalnych prostokątów „typu 3” dla bloków końcowych, używam całego górnego rzędu, po prostu jak prostokąty „typu 2” dla . Wreszcie mam prostokąt zajmujący środkową lewą i dolną lewą komórkę w każdym lewym bloku końcowym (poziomo odwrócony dla każdego prawego bloku końcowego). Możesz więc zakryć dolne 2 rzędy wszystkich bloków, w tym i między blokami końcowymi, używając wzoru lub .

a < j < b

$a < j < b$ |==|

— j_random_hacker

Lubię twoją-by-pomysł redukcji. Z tym, w przeciwieństwie do-by-redukcji, mogą istnieć rozwiązania o minimalnych kosztach, które nie odpowiadają pokrywom wierzchołków - ale wszystkie takie rozwiązania można przekształcić w równe (ly minimum) rozwiązania kosztu przy użyciu tego samego argumentu, co w ostatnim punkcie wypunktowania, więc to nie jest problem z redukcją :)

| E |

$|E|$

3 | V |

$3|V|$

3 | E |

$3|E|$

3 | V |

$3|V|$

— j_random_hacker

Dzięki podpowiedzi j_random_hacker znalazłem rozwiązanie, aby zmniejszyć pokrycie wierzchołków do problemu z siecią:

Wykonujemy-by-siatka bloków 3 na 3, tj.-by-siatka z wierzchołkami uporządkowanymi jako kolumny i krawędziami uporządkowanymi jako wiersze . Na tej siatce zbudujemy prostokąty (poniższy rysunek bardzo pomoże zrozumieć różne użyte prostokąty) $|E|$ $|V|$ $3|E|$ $3|V|$ $\{v_1,\dots,v_{N_1}\}$ $\{e_1,\dots,e_{N_2}\}$

Dla każdego wierzchołka tworzymy prostokąt typu 1, który pokrywa środkową kolumnę kolumny bloków odpowiadającą temu wierzchołkowi, więc mamyprostokąty typu 1. $|V|$

Każdy blok odpowiada unikalnej parze , przy czym dla każdego bloku dodajemy prostokąt typu 2: $(e_i,v_j)$ $e_i=(v_a,v_b)$

jeśli lub , jest to prostokąt 3 na 3 pokrywający cały blok. $j<a$ $b<j$
jeśli (odpowiednio. ), jest to prostokąt 3 na 1 obejmujący lewą (lub prawą) kolumnę bloku. $j=a$ $j=b$
jeśli , jest to prostokąt 1 na 3 pokrywający górny rząd bloku. $a<j<b$

Mamy więcprostokąty typu 2, te prostokąty będą obowiązkowe do wyboru, ponieważ każdy będzie jedyną osłoną dla lewego górnego (lub prawego górnego) rogu bloku, w którym się znajduje. $|E||V|$

Jak powiedzieliśmy, każda krawędź odpowiada rzędowi, z dwoma blokami (nazwijmy je blokami końcowymi) odpowiadającymi punktom końcowym wierzchołków i , teraz mamy prostokąty typu 3: $(e_i,v_a)$ $(e_i,v_b)$

dla bloku końcowego (odpowiednio. ) mamy prostokąt 1 na 2 pokrywający prawy górny (lub lewy górny) narożnik bloku końcowego. $(e_i,v_a)$ $(e_i,v_b)$

Mamyprostokąty typu 3 i znowu są obowiązkowe, ponieważ każdy będzie jedyną przykrywką dla prawego górnego rogu (jeśli jest to pierwszy blok końcowy) lub lewego górnego rogu (jeśli jest to drugi blok końcowy), w którym się znajduje. $2|E|$

Teraz dla każdej krawędzi budujemy prostokąty typu 4, między blokami końcowymi mamy dwa prostokąty dla drugiego rzędu:

Jeden biegnie od centralnego kwadratu pierwszego bloku do środkowo-lewego kwadratu drugiego bloku.
Jeden biegnie od środkowo-prawego kwadratu pierwszego bloku do centralnego kwadratu drugiego bloku.
I te same dwa prostokąty dla trzeciego rzędu.

Mamyprostokąty typu 4, jednak nie wszystkie są obowiązkowe. $4|E|$

A teraz, aby objąć siatkę:

$|E|(|V|+2)$ prostokąty (typ 2 i 3) są obowiązkowe i(typ 1 i 4) są opcjonalne. $|V|+4|E|$

Aby pokryć, dla danej krawędzi, część między końcowymi blokami krawędzi jeszcze nie zakrytymi (drugi i trzeci rząd rzędu bloków), możemy użyć:

cztery prostokąta typu 4.
jeden prostokąt typu 1 i dwa prostokąty typu 4.

Pamiętaj, że w każdym razie potrzebujemy co najmniej dwóch prostokątów typu 4.

Więc tutaj funkcją kosztu będzie: $|E|(|V|+4) + k$

Jeśli jest to prawidłowa osłona wierzchołka o wierzchołku mniejszym niż k: używamy obowiązkowych prostokątów , to w przypadku prostokątów opcjonalnych możemy użyć prostokątów typu 1 odpowiadających osłonie wierzchołków, oraz na każdy wiersz potrzebujemy tylko 2 prostokąty typu 4 (mamy już prostokąt typu 1). Więc jeśli wykres ma prawidłową osłonę wierzchołków, siatka ma prawidłową osłonę zestawu. $|E|(|V|+2)$
Jeśli mamy prawidłowy zestaw pokrycia dla siatki (z mniej niż ) prostokątami, to dla każdej krawędzi albo mamy już prostokąt typu 1 (a krawędź jest „zakryta” ") lub cztery prostokąty typu 4, w którym to przypadku możemy zastąpić dwa z nich jednym prostokątem typu 1 i nadal mamy ważną osłonę z prostokątami . Poprzez iterację tego procesu osiągamy prawidłowe rozwiązanie bez wiersza, używając czterech prostokątów typu 4, z których możemy uzyskać prawidłową osłonę wierzchołków. $|E|(|V|+4) + k$ $|E|(|V|+4) + k$

Tak więc osłonę wierzchołków można zredukować do osłony siatki. I wystąpienie problemu z siecią może być kodowane przezobejmuje na siatce zelementy, więc redukcja jest wielomianowa, a problemem siatki jest NPC. $|E|(|V|+6) + |V|$ $9|V||E|$

PS: Zauważyłem po napisaniu tej odpowiedzi, że wiele prostokątów jest w rzeczywistości bezużytecznych i można znacznie prostszą redukcję za pomocą-by-siatka zobejmuje, wykorzystując funkcję kosztów $|E|$ $3|V|$ $|V|+4|E|$ $3|E|+k$

— Yann
źródło