字典中最小的完美匹配

我想在兩個部分圖中找到字典中最小的完美匹配。我應該使用庫恩的算法，但我不明白如何使匹配詞典學上最小。庫恩的算法完全可能嗎？我可以提供我的代碼，但它足夠經典。字典中最小的完美匹配

2011-04-07 Artem Volkhin

@Benjamin，它幾乎相同，但加權匹配。你知道如何使用它來查找_lexicographically smallest_ matching，並且你能給我證明嗎？ – 2011-04-07 15:39:12

也許這可以幫到您：http://books.google.ca/books?id=NLngYyWFl_YC&lpg=PA668&ots=BxNoBH-nB8&dq=lexicographically%20smallest%20matching&pg=PA664#v=onepage&q=lexicographically%20smallest%20matching&f=false There also also在維基百科鏈接中有很好的信息，比如http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf – Benjamin 2011-04-07 15:41:54

據我所知，它是作爲Cormen的練習給出的。 – 2011-04-07 15:44:00

作爲一個提示，考慮如何確定在lex-min匹配中應該只匹配第一個節點。

來源

2011-04-07 16:21:28 jcd

是的，目前我使用這樣的實現，比庫恩算法差兩倍。 – 2011-04-07 16:23:20

在大多數情況下，這樣它通常是容易做出的減少而不是修改算法：

找到一種方法來改變你的問題的輸入，使得字典順序打破任何關係（但在完美匹配仍然比不完美匹配得分更高的方式）
通過庫恩算法運行修改後的圖。
如果需要，請將答案翻譯回原始問題。

我沒試過其實這個解決自己或詳細閱讀問題。但是，這似乎是一個教科書練習，我覺得這個答案就足夠了:-)

來源

2011-04-08 16:06:59 hugomg

想想你如何創建鼓勵詞典上早期匹配的轉讓價格。

來源

2013-02-05 17:44:09

字典中最小的完美匹配

回答

相關問題