Gunakan minimum swap sehingga setiap nampan berisi bola dengan warna yang sama

Ada $n$ sampah, yang bin th mengandung bola. Bola memiliki warna, ada bola warna . Biarkan .$i$$a_i$$n$$a_i$$i$$m=\sum_{i=1}^n a_i$

Swap adalah mengambil bola dari satu nampan dan menukar dengan bola dari nampan lain. Kami ingin jumlah swap minimum sehingga setiap nampan hanya berisi bola dengan warna yang sama.

Saya tahu kasus khusus yang mudah untuk semua$a_i\leq 2$$i$ . (Jika untuk semua i , maka Anda bahkan dapat melakukannya dengan menukar setiap bola paling banyak sekali.)$a_i=2$$i$

Sunting : Ini salah karena menemukan NP-hard.$c(D)$

Jika kita tahu warna ke bin mana, masalahnya mudah.

Pertimbangkan multi-digraf , V = { v 1 , ... , v n } . Jika kita tahu warna i pergi ke bin b ( i ) , maka ada busur paralel k ( j , b ( i ) ) di A iff bin j berisi k bola warna $D=(V,A)$$V=\{v_1,\ldots,v_n\}$$i$$b(i)$$k$$(j,b(i))$$A$$j$$k$$i$. Setiap komponen grafik adalah Euler. Jumlah minimum swap yang dibutuhkan adalah , di mana c ( D ) adalah jumlah siklus menguraikan busur yang mencakup A . Kita dapat bertukar dengan "mengikuti" sirkuit Euler. (swap menggunakan busur siklus minimal dapat mengubahnya ke siklus minimal yang lebih kecil dan loop diri). Setelah seluruh grafik diatur dari loop otomatis, kami telah melakukan semua swap yang diperlukan.$m-c(D)$$c(D)$$A$

Seberapa sulit masalah ini secara umum?

Dekomposisi maksimal grafik berarah Euler ke siklus disjoint edge adalah NP-Hard, setidaknya menurut buku ini: Algoritma dan Aplikasi: Esai Didedikasikan untuk Esko Ukkonen pada Acara Ulang Tahunnya yang ke-60 .

btw, berikut ini adalah artikel yang relevan dengan masalah yang Anda coba selesaikan: Algoritma optimal asimtotik untuk algoritma bendera Nasional Belanda .

Untuk , makalah ini memberikan algoritma sederhana.$n \le 6$