Pokrycie siatki prostokątami

15

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 N 2 RN1×N2N1N2R

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

  • Dane wejściowe: Collection prostokątów na siatce (rozmiar wejściowy: ) iN 1 N 2 L K N +C={R1,R2),,RL.}N1N.2)L.K.N.+
  • Dane wyjściowe: Podzbiór z i zawierający dla każdej komórki co najmniej jeden prostokąt ją pokrywający.| S | K SSdo|S|KS.

Wizualny przykład problemu

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

  • optymalne pokrycie niektórych podproblemów obejmujących pierwsze komórki .N1n1
  • prostokąt 1D, tj. odstęp, obejmujący pozostałe komórki .n1

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 + N 2N1(N1+N2N2)

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.

Yann
źródło
3
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).| V | 3 | E | k | E | ( | V | + 3 ) + k|E||V|3|E|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 | ja ja|V||V|ii
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|
Yann
1
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|==|
j_random_hacker
1
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ą :)3 | V | 3 | E | 3 | V ||E|3|V|3|E|3|V|
j_random_hacker

Odpowiedzi:

4

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)| V | 3 | E | 3 | V | { v 1 , , v N 1 } { e 1 , , e N 2 }|mi||V.|3)|mi|3)|V.|{v1,,vN.1}{mi1,,miN.2)}

wprowadź opis zdjęcia tutaj

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 a , v b )(mija,vjot)ei=(va,vb)

  • jeśli lub , jest to prostokąt 3 na 3 pokrywający cały blok.b < jj<ab<j
  • jeśli (odpowiednio. ), jest to prostokąt 3 na 1 obejmujący lewą (lub prawą) kolumnę bloku.j = bj=aj=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 b )(ei,va)(ei,vb)

  • 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 b )(ei,va)(ei,vb)

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