Generalisasi dari algoritma Hungaria ke grafik umum yang tidak diarahkan?

14

Algoritma Hungaria adalah algoritma optimisasi kombinatorial yang memecahkan masalah pencocokan bipartit berat maksimum dalam waktu polinomial dan mengantisipasi perkembangan selanjutnya dari metode primal-dual yang penting . Algoritma ini dikembangkan dan diterbitkan oleh Harold Kuhn pada tahun 1955, yang memberi nama "Algoritma Hongaria" karena algoritma ini didasarkan pada karya sebelumnya dari dua ahli matematika Hongaria: Dénes Kőnig dan Jenő Egerváry. Munkres meninjau algoritma pada tahun 1957 dan mengamati bahwa itu memang polytime. Sejak itu algoritma ini juga dikenal sebagai algoritma Kuhn-Munkres.

Meskipun Hongaria berisi ide dasar metode primal-dual, ia memecahkan masalah pencocokan bipartit berat maksimum secara langsung tanpa menggunakan mesin pemrograman linier (LP) apa pun. Dengan demikian, dalam menjawab pertanyaan berikut , Jukka Suomela berkomentar

Tentu saja Anda dapat memecahkan LP apa pun dengan menggunakan LP solver serba guna, tetapi algoritme khusus biasanya memiliki kinerja yang jauh lebih baik. [...] Anda juga dapat sering menghindari masalah seperti menggunakan angka rasional yang tepat vs angka floating point; semuanya bisa dilakukan dengan mudah dengan integer.

Dengan kata lain, Anda tidak perlu khawatir tentang cara membulatkan solusi titik rasional / mengambang dari pemecah LP untuk mendapatkan kembali pencocokan sempurna berat maksimum dari grafik bipartit yang diberikan.

Pertanyaan saya adalah sebagai berikut:

Apakah ada generalisasi dari algoritma Hungaria yang bekerja untuk grafik tidak berarah umum tanpa menggunakan mesin LP mirip dengan semangat algoritma Hungaria asli?

Saya lebih suka eksposisi modern dan mudah dibaca daripada kertas rumit yang asli. Tetapi pointer apa pun akan sangat dihargai!

Terima kasih banyak sebelumnya dan Selamat Natal !!!


Pembaruan: Pertanyaannya dijawab dengan baik oleh Arman di bawah ini. Saya hanya ingin menunjukkan bahwa sumber lain yang bagus untuk mempelajari Algoritma Blossom Edmonds (untuk kasus berbobot) adalah Bab 11 Optimalisasi Kombinatorial oleh Korte dan Vygen . Buku Google sebenarnya menunjukkan hampir semua bagian yang saya butuhkan untuk memahami algoritma.

Dai Le
sumber
2
Bagaimana dengan algoritma pencocokan Edmonds? en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm
Arman
1
@Arman - Itulah yang saya pikirkan juga. Terima kasih atas tautannya, Wikipedia memiliki penjelasan terperinci yang mengejutkan tentang algoritma bunga Edmond.
Abraham Flaxman
2
Omong-omong, algoritma pencocokan Edmonds juga didasarkan pada metode Primal-Dual.
Arman
1
Terima kasih Arman. Tautan wikipedia juga menunjuk ke buku "Lovász, László; Plummer, Michael (1986). Matching Theory" untuk versi berbobot dari algoritma Edmonds. Saya harus benar-benar memeriksa buku itu. Terima kasih banyak atas komentar Anda! Mungkin jika ada di antara Anda yang bisa menjelaskan bagaimana algoritma membuat generalisasi algoritma Hungaria, Anda pasti bisa menjawabnya.
Dai Le
1
Saya pikir ini adalah jawaban yang cukup bagus :). Arman, Anda harus menambahkannya
Suresh Venkat

Jawaban:

16

Algoritma pencocokan Edmonds (juga disebut Algoritma Blossom) memecahkan pencocokan maksimum pada grafik umum. Sebenarnya itu adalah generalisasi dari metode jalur bolak-balik. (Saya tidak yakin dengan nama metode ini tetapi harus menggunakan metode König-Hall.) Pada dasarnya ia menemukan jalur tambahan (lihat halaman wikipedia.org: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm ) untuk memperpanjang pencocokan saat ini dan berhenti jika tidak ada lagi jalur tambahan. Dalam grafik umum, satu-satunya masalah terjadi dalam siklus aneh. Dalam algoritma pencocokan Edmonds, siklus aneh dikontrak (bunga) dan dikeluarkan kembali untuk memiliki solusi.

Ada juga korespondensi antara Algoritma Blossom dan metode Primal Dual. Siklus ganjil menyebabkan titik ekstrim fraksional. Karena itu kami menambahkan apa yang disebut ketidaksetaraan bunga untuk setiap siklus aneh.

Pencocokan sempurna berbobot minimum dan masalah pencocokan berat maksimum juga bisa ditangani dengan pendekatan ini.

Untuk detail algoritme, lihat http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf

Untuk formulasi matematika dan metode primal-dual yang sesuai, lihat http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf

Arman
sumber
9

Dua tahun lalu, ketika meneliti algoritma blossom (tidak berbobot), saya menemukan dua set catatan besar, satu oleh Tarjan dan satu oleh Zwick. Mereka membuat kasus tanpa bobot tampak cukup mudah dan saya bisa menerapkannya di Mathematica menggunakan rekursi. Ini bekerja dengan sangat baik.

Catatan yang menurut saya bermanfaat adalah

http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf dan http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/ tarjan-blossom.pdf

Mereka menyaring semuanya menjadi istilah yang sangat sederhana yang memungkinkan seseorang untuk berpikir secara rekursif dan kemudian, seperti dicatat, memprogram secara rekursif.

Saya pikir itu semua harus bekerja dalam kasus tertimbang, yang saya coba terapkan sekarang.

Stan Wagon
sumber
Dan saya memiliki demo yang dapat ditonton oleh siapa pun dengan perangkat lunak gratis: Yang pertama menunjukkan mekar dengan baik .... < demonstrations.wolfram.com/... > < demonstrations.wolfram.com/TheHungarianMaximumMatchingAlgorithm > < demonstrations.wolfram.com/ PlacingDominoOnACheckerboard >
Stan Wagon
Dan saya baru saja memprogram mekar tanpa bobot seperti yang diberikan di Korte / Vygen. Saya melihat beberapa speedups dimungkinkan untuk kode-nya (misalnya, mulai dengan pencocokan maksimal, sebagai lawan dari apa-apa), tetapi yang menyenangkan adalah bahwa kode proseduralnya diberikan dalam bentuk yang orang dapat dengan mudah menerjemahkan ke kode kerja. Berikutnya: bunga tertimbang, yang jauh lebih sulit.
Stan Wagon