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 R
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 +
- Dane wyjściowe: Podzbiór z i zawierający dla każdej komórki co najmniej jeden prostokąt ją pokrywający.| S | ≤ K 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
- optymalne pokrycie niektórych podproblemów obejmujących pierwsze komórki .
- prostokąt 1D, tj. odstęp, obejmujący pozostałe komórki .
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 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.
|=
=|
Odpowiedzi:
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} { e1, … , EN.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 a , v b )( eja, vjot) mija=(va,vb)
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)
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:
Mamyprostokąty typu 4, jednak nie wszystkie są obowiązkowe.4|E|
A teraz, aby objąć siatkę:
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ć:
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
źródło