Saya bukan ahli teori ilmu komputer, tetapi saya pikir masalah dunia nyata ini ada di sini.

Masalah

Perusahaan saya memiliki beberapa unit di seluruh negeri.

Kami menawarkan kepada karyawan kemungkinan untuk bekerja di unit lain. Tetapi ada syaratnya: Jumlah total pekerja pada suatu unit tidak dapat berubah.

Itu berarti: Kami akan mengizinkan karyawan untuk meninggalkan unitnya jika seseorang menginginkan tempatnya.

Data permintaan contoh (fiktif):

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

Di atas, diplot:

Lihat bagaimana kita harus memilih antara opsi merah, biru atau hitam?

Masalah sebenarnya sedikit lebih kompleks, karena kami memiliki 27 unit dan 751 permintaan. Silakan lihat visualisasi

Hasil

Setelah mengumpulkan semua permintaan, bagaimana memuaskan sebagian besar dari mereka?

Aplikasi Teori (?)

Memiliki grafik , biarkan setiap unit menjadi simpul V dan permintaan menjadi ujung terarah E , pertukaran yang berhasil akan mengambil bentuk cyle terarah.$G(V, E)$$V$$E$

Setiap siklus harus menggunakan hanya sekali ( pekerja tidak dapat meninggalkan unitnya dua kali ), tetapi dapat mengunjungi V beberapa kali ( unit dapat memiliki banyak pekerja yang ingin pergi ).$E$$V$

Pertanyaan

Jika masalah ini dinyatakan sebagai

"Bagaimana menemukan siklus yang, bersama-sama, melibatkan jumlah terbesar tepi yang tidak dibagi dalam grafik yang diarahkan"?

Apakah kita akan memuaskan sebagian besar pemohon?

Itu benar, ada algoritma untuk menemukan set siklus yang optimal?

Akankah pendekatan greddy ini menyelesaikan masalah?

1. Temukan siklus terarah terbesar di ;$G$
2. Hapus tepi itu dari ;$G$
3. Ulangi 1 sampai tidak ada siklus terarah pada ;$G$

Bisakah kamu membantuku?

Apakah Anda tahu cara lain untuk menggambarkan masalah asli (membuat sebagian besar pemohon senang)?

Sunting : departemen diubah ke unit, untuk lebih menggambarkan masalah.

OK, saya membaca kode TradeMaximizer dan saya percaya ini memecahkan masalah yang lebih umum.

MASALAH: Diberikan adalah grafik terarah yang busurnya memiliki biaya. Temukan satu set siklus disintegrasi titik yang memaksimalkan jumlah simpul tertutup terlebih dahulu, dan meminimalkan total biaya kedua.

Untuk menyelesaikan pertanyaan yang diajukan di sini, buat simpul menjadi karyawan dan tarik busur biaya unit saat x ingin pekerjaan y . Perhatikan bahwa karyawan sekarang menjadi simpul, bukan ujung. Yang menyenangkan adalah bahwa seorang karyawan dapat mengatakan "Aku benar-benar menginginkan pekerjaan y , tetapi z juga akan melakukannya".$x\to y$$x$$y$$y$$z$

Larutan:

1. Buat grafik bipartit sebagai berikut: Untuk setiap simpul dalam grafik asli, perkenalkan simpul kiri x L , simpul kanan x $x$$x_L$$x_R$ , dan busur yang biayanya sangat besar (lebih besar dari jumlah biaya dalam dokumen asli) grafik). Untuk setiap busur x → y dalam grafik asli, perkenalkan busur x L → y R dalam grafik bipartit.$x_L\to x_R$$x\to y$$x_L\to y_R$

2. Temukan pencocokan sempurna biaya minimum dalam grafik bipartit.

Ada beberapa preprocessing dari grafik asli juga: Hapus busur antara SCC, kemudian proses semua SCC dengan ukuran seperti yang ditunjukkan di atas.$>1$

(Faktanya, TradeMaximizer mengulangi semua solusi optimal, sesuai dengan dua kriteria di atas, untuk mengoptimalkan hal-hal lain secara heuristik, seperti lamanya siklus terbesar. Siklus besar meningkatkan kemungkinan "kesepakatan" tidak terjadi karena satu seseorang berubah pikiran.)

PS: Penulis, Chris Okasaki, mengkonfirmasi bahwa ini adalah apa yang dilakukan oleh kode, kembali di posting blog .

Ini adalah masalah sirkulasi biaya minimum standar. Berikan masing-masing kapasitas tepi terarah dan biaya - 1 . Maka sirkulasi yang layak adalah jumlah (yaitu, persatuan) dari siklus diarahkan-disjoint edge, dan biaya sirkulasi adalah negasi dari jumlah edge.$1$$-1$

Karena semua biaya dan kapasitas dibatasi oleh konstanta, algoritma pembatalan siklus sederhana akan menemukan sirkulasi yang diperlukan dalam waktu polinomial. Ini hampir sama dengan algoritma serakah yang jelas:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

Di sini, biaya siklus adalah jumlah dari biaya ujungnya. Siklus biaya negatif dapat ditemukan menggunakan algoritma jalur terpendek Bellman-Ford dalam waktu . Setiap iterasi mengurangi biaya sirkulasi saat ini dengan setidaknya 1. awal sirkulasi (kosong) memiliki biaya 0 , dan sirkulasi akhir memiliki biaya setidaknya - E . Dengan demikian, algoritme berakhir setelah paling banyak E iterasi, sehingga total waktu menjalankannya paling banyak$O(VE)$$0$$-E$$E$$O(VE^2)$

Ini bukan algoritma tercepat yang dikenal.

Pendekatan serakah ini tidak akan selalu memberikan solusi terbaik.

$C$$n$$\{(v_1, v_2),\dots,(v_n,v_1)\}$$C_1$$C_2$$n-1$$C$ .

$C$$n$$C_1$$C_2$ masing-masing kehilangan satu sisi dan tidak ada siklus lagi.

$C_1$$C_2$$2(n-1)=2n-2$

Selain: Daripada menambahkan dua siklus pada contoh di atas, Anda dapat menambahkan $\lfloor\frac{n}{2}\rfloor$ siklus yang membuat solusi serakah lebih buruk.

mungkin ada cara / rumus teori grafik untuk menyelesaikan ini, tetapi masalah ini terdengar lebih seperti masalah permutasi bagi saya di mana sebagian dari semua permutasi ditolak dan yang lainnya valid. permutasi adalah karyawan dan posisi adalah "posisi" di perusahaan. permutasi ditolak jika tidak sesuai dengan persyaratan "orang [x] yang menginginkan posisi [y]". perbedaan batas unit / depts / org tampaknya agak berlebihan untuk solusi dalam kasus ini.

jenis masalah permutasi dengan kendala ini dapat dengan mudah dikonversi menjadi turunan dari masalah SAT (satisfiability). penugasan variabel boolean mewakili karyawan, dan klausa kendala mewakili batasan "orang [x] menginginkan posisi [y]". ada contoh klasik terdekat ini, yang biasanya disebut masalah "meja makan" di mana Anda memiliki posisi duduk dan tamu dan tidak semua tamu ingin duduk bersebelahan (atau sangat mirip beberapa tamu ingin duduk di sebelah tamu lain).

dan tentu saja ada pemecah SAT canggih untuk contoh cukup besar yang melibatkan sekitar hingga ratusan variabel dan klausa, pada PC, dan jika masalahnya bukan "sulit", dalam ribuan.

lihat misalnya [1] untuk referensi profesional dan [2] untuk latihan kelas. ada juga beberapa kemiripan struktural dengan apa yang dikenal sebagai "masalah pigeonhole" yang dipelajari dengan baik di lingkaran SAT di mana merpati ditugaskan untuk lubang pigeon dan Anda memiliki lebih banyak atau lebih sedikit lubang daripada merpati. dalam hal ini bagaimanapun juga, merpati secara umum dianggap saling dipertukarkan. dengan kata lain masalah meja makan adalah seperti masalah lubang merpati dengan kendala yang lebih kuat dan tamu / merpati memerlukan preferensi.

perhatikan tentu saja / perlu diingat bahwa untuk jenis masalah ini, tergantung pada kendala jawabannya mungkin "tidak ada solusi yang dibatasi seperti itu".

[1] algoritma meja makan, oleh crato

[2] CS402 prinsip HW SAT

[3] Masalah kepuasan, wikipedia