Jak podzielić zestaw na określoną liczbę rozłącznych podzbiorów pod pewnymi warunkami?

Dostaję zestaw , liczbę całkowitą s \ leqslant k i nieujemne liczby całkowite a_ {ij} . Mój problem polega na znalezieniu s podzbiory rozłączne S_j z \ {1, \ ldots, k \} takie, że:$A\triangleq\{1,\ldots,k\}$$s\leqslant k$$a_{ij}$$s$$S_j$$\{1,\ldots,k\}$

1. $\bigcup_{j=1}^s S_j=A$ ; i
2. $|S_j|\leqslant a_{ij}$ dla wszystkich $i\in S_j$ i $j=1,\ldots,s$ .

Jak rozwiązać ten problem? Czy trudno jest znaleźć realne rozwiązanie?

Myślę, że nie jest łatwo rozwiązać problem, ponieważ próbowałem procedury, która zaczyna się od jakiegoś $j\in\{1,\ldots,n\}$ i przypisuje $i\in\{1,\ldots,k\}$ aż do liczby z $i$ przypisanych do $j$ są większe niż $a_{ij}$ dla niektórych przypisanych $i$ . Ale to nie jest poprawne, ponieważ mogłem zostawić część $i$ , której nie można przypisać do żadnego $j$ (z powodu ich $a_{ij}$ które nie mogą być spełnione).

Metoda brutalnej siły, gdy muszę wygenerować wszystkie podzbiory $A$ i przetestować każdy z nich, działa dla mnie ( $k=8,n=3$ ), ale jest bardzo nieefektywna.

Problem ten jest trudny do wyeliminowania przez NP w porównaniu z osłoną wierzchołków.

W zadaniu Pokrycia wierzchołków otrzymujemy wykres i liczbę , a naszym zadaniem jest ustalenie, czy istnieje jakiś podzbiór co najwyżej wierzchołków od tak że każda krawędź w jest padająca co najmniej jednego wierzchołka w . (Równoważnie: Czy można zabić każdą krawędź w poprzez usunięcie co najwyżej wierzchołków?)r U r V E U $G = (V, E)$$r$$U$$r$$V$$E$$U$$G$$r$

Po pierwsze, podział do rozłącznych podzbiorów jest równoważna przypisując każdy element w dokładnie jeden z możliwych etykiet. Podstawową ideą redukcji jest utworzenie etykiety dla każdego wierzchołka w i „umożliwienie” przypisania każdej krawędzi tylko jednej z dwóch etykiet odpowiadających jej punktom końcowym, w następującym znaczeniu: przypisanie krawędzi odpowiadającej etykieta nie wprowadza (prawdziwego) ograniczenia co do innych krawędzi, którym można przypisać tę samą etykietę, a przypisanie krawędzi do nie odpowiadającej etykiecie zapobiega przypisaniu tej samej etykiecie innej krawędzi - co oczywiście powoduje zwiększenie liczby wymagane odrębne etykiety.s A s S j v j$A$$s$$A$$s$$S_j$$v_j$$V$

Aby zbudować instancję problemu z instancji programu Vertex Cover:( G , r $(A, a, s)$$(G, r)$

1. Ustaw naI tworzyć element w do każdej krawędzi w . (Te pary można traktować jako liczby całkowite ; zrobi to każdy bijection między nimi).| E $k$$|E|$A v i v j E 1 , … , $(i, j)$$A$$v_iv_j$$E$$1, \dots, k$
2. Ustaw najeśli lub ; w przeciwnym razie ustaw na 1.$a_{(b, c), d}$d = b d = c a ( b , c ) , $|E|$$d=b$$d=c$$a_{(b, c), d}$
3. Ustaw .$s=r$

Jeśli jest instancją YES dla Cover Vertex, łatwo zauważyć, że właśnie skonstruowana instancja twojego problemu jest również instancją YES: wystarczy wybrać etykiety odpowiadające wierzchołkom w dowolnym rozwiązaniu , i dla każdej krawędzi przypisz odpowiedni element którakolwiek z etykiet lub została wybrana (wybierz dowolnie, jeśli obie etykiety zostały wybrane). To rozwiązanie wykorzystuje podzbiory i jest poprawne, ponieważ jedynymi obowiązującymi są odpowiednieS j v j U v b v c ∈ E ( b , c ) $(G, r)$$S_j$$v_j$$U$$v_bv_c \in E$S b S c s a i j | E $(b, c) \in A$$S_b$$S_c$$s$$a_{ij}$etykiety, które mają (nie) efekt zapobiegania więcej niżkrawędzie mają przypisaną tę samą etykietę.$|E|$

Pozostaje pokazać, że wystąpienie YES twojego problemu oznacza, że ​​oryginał jest wystąpieniem YES okładki wierzchołka. Jest to nieco bardziej skomplikowana, ponieważ ważnego rozwiązania na mogą w przypisaniu krawędź dla etykiety -corresponding , czyli , co oznacza, że nie może niekoniecznie „odczytać” prawidłową pokrywy wierzchołków z ważnego rozwiązania .( G , r ) Y $X=(A, a, s)$$(G, r)$$Y$$X$S m m ∉ { i , j } U $(i, j)$$S_m$$m \notin \{i, j\}$$U$$Y$

Jednakże, przypisywanie innego niż odpowiednie etykiety ma wysoki koszt, który znacznie ogranicza struktury rozwiązania: gdy krawędź jest przypisana taka etykieta z , fakt że zapewnia, że ​​musi to być jedyna krawędź, której przypisano tę etykietę. Tak więc w każdym rozwiązaniu zawierającym taką nieoznaczoną krawędź , moglibyśmy skonstruować alternatywne rozwiązanie w następujący sposób:S m m ∉ { i , j } a ( i $(i, j)$$S_m$$m \notin \{i, j\}$Y(i,j)↦ S m Y $a_{(i, j), m} = 1$$Y$$(i, j) \mapsto S_m$$Y'$

1. Dowolnie wybierz nową etykietę dla jako lub . ( i , j ) S i S $S_z$$(i, j)$$S_i$$S_j$
2. Przypisz tę nową etykietę. Jeśli skutkuje to nieprawidłowym rozwiązaniem, musi to być spowodowane tym, że dokładnie jedna inna krawędź , została już przypisana do etykiety . W takim przypadku ustaw i przejdź do kroku 1.( i ′ , j ′ ) z ∉ { i ′ , j ′ } S z ( i , j ) = ( i ′ , j ′$(i, j)$$(i', j')$$z \notin \{i', j'\}$$S_z$$(i, j) = (i', j')$

Powyższy algorytm musi zakończyć się na jeden z dwóch sposobów: albo zostanie znaleziona nowa etykieta która nie wprowadza sprzeczności, albo zostanie znaleziony pełny cykl wierzchołków. W pierwszym przypadku znaleziono prawidłowe nowe rozwiązanie z zestawami , podczas gdy w drugim przypadku znaleziono prawidłowe nowe rozwiązanie z zestawami ; w obu przypadkach stworzyliśmy nowe, poprawne rozwiązanie z co najmniej jedną dodatkową krawędzią przypisaną do odpowiedniej etykiety. Po powtórzeniu całego tego procesu najwyżejrazy, stworzymy prawidłowe rozwiązanie z którego można odczytać rozwiązanie pierwotnego problemu z pokrywą wierzchołków . s - 1 s | E | Y $S_z$$s-1$$s$$|E|$$Y''$

Ta konstrukcja jest wyraźnie czasem wielomianowym, więc wynika z tego, że twój problem jest trudny do NP.