最低婚姻可能算法

有一些男人M1，M2，....錳和一些婦女給W1，W2，W3，..... Wm。還有一個二維矩陣也給出了這個矩陣，它說明了他喜歡的男人的興趣。計算結婚所有男性和女性所需的婚姻數量。最低婚姻可能算法

constraint:一個男人可以與多個女人結婚，一個女人可以與多個男人結婚。

Approach that I think:我覺得這個問題可以用雙方解決，但我很困惑什麼情況下用來啓動問題。請指導解決這個問題。

2012-08-30 devsda

你的意思是「一個人有多個可能的女性結婚，但可以娶只是其中之一」，或者你真的意味着「一個人不能同時娶多個女人」？ –

一個男人可以一次結婚多個女人，反之亦然 – devsda

你想要最小的邊緣覆蓋，這是一個多項式時間問題。您可以使用Hopcroft-Karp算法來查找最大匹配，然後從每個未連接的點向其任何可能的配對繪製一條邊。

2012-08-30 16:25:20 argentage

（男人，我對這個問題的第一個回答是錯誤的。） – argentage

我假設你的意思是[NP-Complete]（http://en.wikipedia.org/wiki/） NP完全問題）？這個問題絕對是在[NP]（http://en.wikipedia.org/wiki/NP_%28complexity%29）中，但這並沒有真正地告訴你很多。 –

是的，我做到了。然而，令人驚訝的是，我去了我的圖論教科書，正確的解決方案顯然比這更快！ – argentage

回答