我想在兩個部分圖中找到字典中最小的完美匹配。我應該使用庫恩的算法,但我不明白如何使匹配詞典學上最小。庫恩的算法完全可能嗎?我可以提供我的代碼,但它足夠經典。字典中最小的完美匹配
2
A
回答
0
作爲一個提示,考慮如何確定在lex-min匹配中應該只匹配第一個節點。
+0
是的,目前我使用這樣的實現,比庫恩算法差兩倍。 – 2011-04-07 16:23:20
0
在大多數情況下,這樣它通常是容易做出的減少而不是修改算法:
- 找到一種方法來改變你的問題的輸入,使得字典順序打破任何關係(但在完美匹配仍然比不完美匹配得分更高的方式)
- 通過庫恩算法運行修改後的圖。
- 如果需要,請將答案翻譯回原始問題。
我沒試過其實這個解決自己或詳細閱讀問題。但是,這似乎是一個教科書練習,我覺得這個答案就足夠了:-)
0
想想你如何創建鼓勵詞典上早期匹配的轉讓價格。
相關問題
- 1. 最大產品在完整的二分圖中完美匹配
- 2. 匹配和完美數學
- 3. function_score:將缺失的字段視爲完美匹配
- 4. 如何匹配Javascript中的空字典?
- 5. 模式匹配字典3
- 6. ,通過匹配字典值
- 7. 美麗的湯線匹配
- 8. 算法回溯。在圖中計算完美匹配
- 9. 字典值的大小寫不敏感匹配
- 10. 字符串完全匹配
- 11. 刪除匹配的類型的字典
- 12. 最快可能類似於字典的匹配
- 13. 最匹配的字段值
- 14. 最小最大匹配問題
- 15. 使用匹配器匹配字符串中的小數()
- 16. 瑞典文字符的模式匹配
- 17. 如何過濾的字典來匹配
- 18. 匹配日期範圍的字典鍵
- 19. Python字典匹配的單詞
- 20. Python的方式來匹配字典
- 21. 不匹配錯誤即使有完美的輸出
- 22. 彈性搜索 - 給予完美匹配的偏好
- 23. 正則表達式僅與在整個匹配的字符數最小匹配
- 24. 正則表達式:我如何施加完美的字符串匹配?
- 25. 功能匹配 - 匹配的最小數量
- 26. 字體大小不匹配
- 27. RegExp PHP顯示最小的匹配
- 28. Solr的最小匹配定製
- 29. UIWebView中的字體大小與iOS字體大小不匹配
- 30. 最大匹配字符串
@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