未知的算法名稱

我有一個匹配的問題，並設計了一個解決它的方法。我需要知道一個算法是否存在，如果是這樣的名字，對於以下情況，我看了很多，但找不到任何東西。我最接近的是循環賽，但那不完全相同。未知的算法名稱

它類似於一些網絡問題，但他們通常沒有得到最優化的路線，他們只是爲了一個好的路線。我需要最優化的。

這是一個很長的閱讀和一個不尋常的要求，但我找不到它的名字。

問題我有一堆物品。每個項目都可能連接到1個或更多其他項目。每個項目只能配對一次。每個連接都有一個值。

我需要找到什麼組合對將導致最高的連接值。

我的解決方案 找到的所有項目都對，並將其存儲在一個地圖採取的第一個項目，並與地圖價值的第一項配對。取下一個項目並將其與第一個未使用的項目配對。繼續這樣做，直到沒有更多的未使用的項目存在。保存此組合或對總價值。如果可能的話，更改對中的最後一對。與保存的組合相比較，如果更多保存新組合當對不能再進行更改時，刪除它並更改新的最後一對，找到更多可能的組合。這一直持續下去，直到組合列表減小到零爲止

上次保存的組合是最好的組合。（Fin）

來源

2013-04-27 Intern87

不確定，但可能是這樣嗎？ http://en.wikipedia.org/wiki/Blossom_algorithm#Weighted_matching – nhahtdh 2013-04-27 04:34:46

這個問題基本上只是一個最大加權匹配。

對於二分圖，找到最大匹配很容易。對於任意圖形來說，這很難但仍然可行。維基百科建議Edmonds的算法稱爲Blossom算法。至於你的算法，目前還不清楚你在做什麼，但它看起來像是一個貪婪的任務，然後爬山。我擔心你的算法不能保證產生最佳結果。你真的證明了這一點？你怎麼知道它不會陷入局部極小？

來源

2013-04-27 04:31:45 Antimony

它嘗試每一種可能性，而無需重試以前的比賽。我有一個程序與上面的例子一起工作，似乎每次都會帶來正確的結果。這絕對是相似的，它非常接近這個和Gale-Shapely算法。 – Intern87 2013-04-27 04:48:22

除非你使用擴充路徑，否則它可能是不正確的或比必要的慢得多。你可以發佈實際的代碼，以便我可以更清楚地看到你在做什麼？ – Antimony 2013-04-27 04:51:56

經過很多很快的閱讀，我同意你的看法，我需要使用Blossom算法，可能需要加權匹配。它在找到我需要的匹配方面要有效得多。非常感謝。我需要做更多的閱讀。 – Intern87 2013-04-27 05:02:48

我相信你正在尋找Gale-Shapley algorithm，它解決了穩定的婚姻問題。

來源

2013-04-27 04:32:15

這個問題似乎只顯示1組。該算法似乎在2套工作。 – nhahtdh 2013-04-27 04:36:37

@nhahtdh它只使用一個集合，但一個集合中的值可以與其中的其他值配對。我只需確保這些值不會多次配對。 – Intern87 2013-04-27 04:49:32

@ Intern87：那麼你的圖是一個通用圖。上述算法似乎只適用於二分圖 - 從我在概述中閱讀的內容。 – nhahtdh 2013-04-27 04:51:14

未知的算法名稱

回答

相關問題