這是什麼樣的算法（穩定的婚姻變異）？

Question

我有一組對象（1到500之間）。每個對象都與來自同一組的某些（零個或多個）其他對象兼容。

任何人都可以給我一些關於如何確定最佳方式來創建對彼此兼容的對象的最佳方式，以便該對象中的大部分都配對？

Answer 1

您正在尋找一般圖表中的最大匹配。與您熟悉的穩定婚姻問題相反，在最大匹配問題中，輸入圖不一定是二分法。沒有穩定性的概念（因爲頂點不排列它們的兼容選項），並且你正在尋找的是圖的邊的子集，使得沒有兩個邊共享公共頂點（a.k.a.，匹配）。您正在嘗試構建包含最大可能邊數的匹配。

幸運的是，發現在一般的圖的最大匹配的問題可以使用Edmond's matching algorithm多項式時間（也稱爲因爲它是如何收縮花（奇數週期）插入單個頂點的開花算法）來解決。 Edmond匹配算法的時間複雜度爲O（E•V^2）。雖然效率不高，但我相信這對於您正在處理的相對較小的圖表來說已經足夠好了。您甚至不必從頭開始實施它，因爲您可以使用開放源代碼Java implementation of Edmond's algorithm。但是，如果您對現有技術感興趣，則可以使用以O（E•sqrt（V））運行的問題所知的most efficient algorithm。

如果輸入的頂點兼容性不是二元的（也就是說，每個頂點都有一個排名，用於指定其鄰居之間的首選項），則可以將相應的權重添加到邊緣以適應首選項配置文件並使用variation of Edmond's algorithm for weighted graphs。