Bagaimana cara mempartisi suatu himpunan ke dalam sejumlah himpunan bagian terputus yang tunduk pada beberapa kondisi?

Saya diberi himpunan , integer , dan integer non-negatif a_ {ij} . Masalah saya adalah menemukan s himpunan bagian himpunan S_j dari \ {1, \ ldots, k \} sedemikian rupa sehingga:$A\triangleq\{1,\ldots,k\}$$s\leqslant k$$a_{ij}$$s$$S_j$$\{1,\ldots,k\}$

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

Bagaimana cara mengatasi masalah ini? Apakah sulit menemukan solusi yang layak?

Saya pikir itu tidak mudah untuk menyelesaikan masalah karena saya mencoba beberapa prosedur yang dimulai oleh beberapa $j\in\{1,\ldots,n\}$ dan menetapkan $i\in\{1,\ldots,k\}$ hingga angka of $i$ ditugaskan ke $j$ lebih besar dari $a_{ij}$ untuk beberapa $i$ ditugaskan. Tetapi ini tidak benar karena saya dapat meninggalkan beberapa $i$ yang tidak dapat ditugaskan ke $j$ (karena $a_{ij}$ yang tidak dapat dipenuhi).

Metode brute force, ketika saya harus menghasilkan semua himpunan bagian $A$ dan menguji masing-masing, bekerja untuk saya ( $k=8,n=3$ ) tetapi sangat tidak efisien.

Masalah ini NP-keras dengan reduksi dari Vertex Cover.

Dalam masalah Vertex Cover, kita diberi grafik dan sejumlah , dan tugas kita adalah untuk menentukan apakah ada beberapa subset paling banyak simpul dari sehingga setiap tepi dalam adalah kejadian pada setidaknya satu titik di . (Setara: Apakah mungkin untuk membunuh setiap sisi dalam dengan menghapus paling banyak simpul?)$G = (V, E)$$r$$U$$r$$V$$E$$U$$G$$r$

Pertama, partisi menjadi himpunan bagian menguraikan setara dengan menugaskan setiap elemen dalam tepat satu dari label mungkin. Ide dasar reduksi adalah untuk membuat label untuk setiap vertex di , dan untuk "memungkinkan" setiap sisi diberi hanya satu dari dua label yang sesuai dengan titik akhir, dalam arti berikut: menetapkan tepi yang sesuai label tidak memperkenalkan batasan (asli) pada tepi mana yang dapat diberi label yang sama, sementara menetapkan tepi pada label yang tidak sesuai mencegah tepi lainnya diberi label yang sama - yang tentu saja memiliki efek mendorong nomor tersebut diperlukan label berbeda.$A$$s$$A$$s$$S_j$$v_j$$V$

Untuk membuat instance masalah Anda dari instance Vertex Cover:$(A, a, s)$$(G, r)$

1. Set ke, Dan menciptakan sebuah elemen di untuk setiap tepi di . (Pasangan-pasangan ini dapat dianggap sebagai bilangan bulat ; setiap penambangan di antara keduanya akan dilakukan.)$k$$|E|$$(i, j)$$A$$v_iv_j$$E$$1, \dots, k$
2. Set kejika atau ; jika tidak, atur ke 1.$a_{(b, c), d}$$|E|$$d=b$$d=c$$a_{(b, c), d}$
3. Set .$s=r$

Jika adalah turunan YA dari Vertex Cover, maka mudah untuk melihat bahwa turunan yang baru saja dibangun dari masalah Anda juga merupakan turunan YA: cukup pilih label sesuai dengan simpul dalam solusi apa pun , dan untuk setiap sisi menetapkan elemen yang sesuai mana yang salah satu dari label atau dipilih (pilih secara sewenang-wenang jika kedua label diambil). Solusi ini menggunakan himpunan bagian , dan valid karena satu-satunya berlaku adalah yang sesuai$(G, r)$$S_j$$v_j$$U$$v_bv_c \in E$$(b, c) \in A$$S_b$$S_c$$s$$a_{ij}$label, yang memiliki efek (non-) mencegah lebih daritepi diberi label yang sama.$|E|$

Tetap menunjukkan bahwa YA-instance dari masalah Anda menyiratkan bahwa yang asli adalah instance-YA dari Vertex Cover. Hal ini sedikit lebih rumit, karena solusi yang valid ke mungkin dalam menetapkan umum tepi seorang non label -corresponding , yaitu, , yang berarti bahwa kita tidak bisa tentu "membacakan" penutup simpul yang valid dari solusi yang valid .$X=(A, a, s)$$(G, r)$$Y$$X$$(i, j)$$S_m$$m \notin \{i, j\}$$U$$Y$

Namun, menetapkan label yang tidak sesuai memiliki biaya tinggi yang sangat membatasi struktur solusi: setiap kali tepi diberikan label seperti , dengan , faktanya bahwa memastikan bahwa itu harus menjadi satu - satunya tepi yang ditetapkan label ini. Jadi, dalam setiap solusi mengandung tepi yang tidak berlabel yang sesuai , kita dapat membuat solusi alternatif sebagai berikut:$(i, j)$$S_m$$m \notin \{i, j\}$$a_{(i, j), m} = 1$$Y$$(i, j) \mapsto S_m$$Y'$

1. Secara sewenang-wenang pilih label baru untuk sebagai atau .$S_z$$(i, j)$$S_i$$S_j$
2. Tetapkan label baru ini. Jika ini menghasilkan solusi yang tidak valid, itu pasti karena tepat satu sisi lainnya , telah diberi label . Dalam hal ini, atur dan lanjutkan ke langkah 1.$(i, j)$$(i', j')$$z \notin \{i', j'\}$$S_z$$(i, j) = (i', j')$

Algoritme di atas harus diakhiri dengan salah satu dari dua cara: label baru ditemukan yang tidak menimbulkan kontradiksi, atau siklus lengkap simpul ditemukan. Dalam kasus sebelumnya, ditemukan solusi baru yang valid dengan set , sedangkan pada kasus yang kedua ditemukan solusi baru yang valid dengan set ; Bagaimanapun, kami telah membangun solusi baru yang valid dengan setidaknya satu keunggulan lagi ditetapkan untuk label yang sesuai . Setelah mengulangi seluruh proses ini paling banyakkali, kami akan menghasilkan solusi yang valid dari mana solusi untuk masalah Vertex Cover asli dapat dibacakan.$S_z$$s-1$$s$$|E|$$Y''$

Konstruksi ini jelas merupakan waktu polinomial, sehingga masalah Anda adalah NP-hard.