Zadanie zbioru trafień (HS) jest zdefiniowane w następujący sposób. Niech $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ zbiór podzbioru S ie $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Chcemy wiedzieć, czy istnieje $ {S} „\ subset S $ gdzie $ | {S} „| < k $ takie, że $ S_i \ cap S „\ neq \ emptyset $, $ i = 1,2, …, m. $
Udowodnij, że HS jest ukończony Np.
Wskazówka : Kiedy $ | S_i | = 2 $, HS staje się okładką wierzchołka, już wiemy, że jest NP-zakończona.
Komentarze
- Czego próbowałeś? utkniesz? ' z przyjemnością pomożemy Ci zrozumieć koncepcje, ale samo rozwiązanie ćwiczeń raczej nie przyniesie Ci rezultatu. Możesz znaleźć ta strona pomocna w ulepszaniu pytania.
Odpowiedź
3SAT jest zredukowany do trafienia Ustaw problem. Mając 3SAT $ \ phi $ z klauzulami $ m $ i zmiennymi $ n $, zdefiniuj
$$ S = \ {x_1, \ dots x_n, \ overline {x_1}, \ dots, \ overline {x_n} \} $$ $$ S_i = \ {y_1, y_2, y_3 \}, \ text {if} y_1, y_2, y_3 \ in S \ text {and} (y_1 \ lor y_2 \ lor y_3) \ text {to klauzula.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {for all zmienna} x. $$ $$ k = n $$
Załóżmy, że $ \ phi $ jest do spełnienia, a następnie istnieje przypisanie wartości prawdziwej dla $ n $ zmiennych. Więc dodaj $ x $ do $ S „$, jeśli $ x = true $, w przeciwnym razie dodaj $ \ overline {x} $ do $ S” $.
Teraz załóżmy, że problem HS ma rozwiązanie $ S „$. Zatem dla każdej zmiennej $ x $, $ S” \ cap S_x \ neq \ emptyset $, $ S „$ ma co najmniej $ n $ literałów w postaci $ x $ lub $ \ overline {x} $ dla każdej zmiennej $ x $. Ponadto żadne $ x $ i $ \ overline {x} $ nie mogą jednocześnie należeć do $ S „$, ponieważ rozmiar $ S” $ wynosi najwyżej $ n $. Ponadto, dla każda klauzula $ C_i $, $ S „\ cap S_i \ neq \ emptyset $ i tak dla każdej klauzuli wybieramy $ y_i \ in S” \ cap S_i $ i ustawiamy $ x = true $ if $ y_i = x $ i $ x = false $ if $ y_i = \ overline {x} $.
Komentarze
- czy możesz pokazać pozytywną i negatywną instancję?
Odpowiedź
Łatwo jest pokazać, że zestaw trafień jest w NP. Rozwiązanie musi po prostu pokazać zbiór H – można łatwo sprawdzić w czasie wielomianu, czy H ma rozmiar k i przecina każdy ze zbiorów B1,.., Bm.
Zmniejszamy z pokrycia wierzchołków. Rozważmy przykład wierzchołka problem z okładką – wykres G = (V, E) i dodatnia liczba całkowita k. Odwzorowujemy to na wystąpienie problemu z trafianiem w następujący sposób. Zbiór A to zbiór wierzchołków V. Dla każdej krawędzi e ∈ E mamy zbiór Se składający się z dwóch punktów końcowych e. Łatwo zauważyć, że zbiór wierzchołków S jest pokryciem wierzchołków G i jeśli odpowiednie elementy tworzą zestaw uderzeń w instancji zestawu uderzającego.
Komentarze
- Witamy w ComputerScience @ SE. Ciekawe użycie specjalnego symbolu
∈– często używa się MathJax, pozwalając np. Na prawidłowe indeksowanie: $ B_1, \ dots, B_m $. - co jeśli rozmiar Se jest większy niż 2? Czy to zadziała?
Odpowiedź
Problem z zestawami trafień jest odpowiednikiem problemu z okładką zestawu, który jest zdefiniowany jak następuje:
INPUT: zbiór C podzbiorów skończonego zbioru S.
ROZWIĄZANIE: zbiór okładek dla S, tj. podzbiór $ C „\ subseteq C $ taki że każdy element w S należy do przynajmniej jednego członka $ C „$.
Biorąc pod uwagę $ k $, czy istnieje zbiór okładek $ C” $ taki, że $ \ vert C „\ vert \ leq k $?
To wygląda na pracę domową, więc pozwolę Ci dowiedzieć się, w jaki sposób, biorąc pod uwagę wystąpienie Set Cover, możesz przekonwertować je na równoważne wystąpienie Hitting Set.
W przeciwnym razie, jeśli chcesz podążać za wskazówką, najpierw pokazujesz, że trafienie jest ustawione w $ NP $, czyli dane rozwiązanie możesz zweryfikować w czasie wielomianowym.
Następnie pokazujesz, że mając wykres $ G = (V, E) $, znalezienie pokrycia wierzchołka o rozmiarze $ k $ jest równoważne znalezieniu zbioru trafiającego o rozmiarze $ k $. To znaczy, jeśli $ | E | = m $, możesz zbudować uderzającą instancję zestawu z taką samą liczbą zestawów.