3

我对两个单词列表的函数感兴趣，它将返回它们之间的顺序不可知的编辑距离。

也就是说，参数将是两个（假设用空格分隔）单词列表，返回值将是列表中单词的编辑（或 Levenshtein）距离的最小总和。

"cat rat bat"和之间的距离"rat bat cat"为0。和之间的距离与和"cat rat bat"之间"fat had bad"的距离相同，4。如果列表中的单词数不相同，则较短的列表将用长度为0的单词填充。"rat bat cat""had fat bad"

我的直觉（没有通过计算机科学课程培养）除了使用蛮力之外没有找到任何其他解决方案：

   |had|fat|bad|   a solution
---+---+---+---+ +---+---+---+
cat| 2 | 1 | 2 | |   | 1 |   |
---+---+---+---+ +---+---+---+
rat| 2 | 1 | 2 | | 3 |   |   |
---+---+---+---+ +---+---+---+
bat| 2 | 1 | 1 | |   |   | 4 |
---+---+---+---+ +---+---+---+

从第一行开始，选择一列并转到下一行，而无需重新访问您已经访问过的列。一遍又一遍地这样做，直到你尝试了所有的组合。

对我来说，这听起来有点像旅行商问题。是吗，您将如何解决我的特定问题？

4

2 回答 2

8

正如您已经在左侧的网格中显示的那样，您可以从计算每对单词的编辑距离开始。这很容易在多项式时间内完成（n^2 编辑距离计算）。

那么您的问题可以描述为“最小加权二分匹配”，或者等效地，“最大加权二分匹配”。这也可以在多项式时间内完成（比旅行推销员更快）。见http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs

于 2010-04-26T18:26:45.227 回答
1

这看起来是打破Levenshtein 距离算法的绝佳机会。该算法将完全满足您的要求（两个字符串之间的最小距离），而且它也非常有效。至于它是旅行推销员的变体，那将是一个否定，因为由于问题的结构，这可以在多项式时间内解决。希望这可以帮助。

于 2010-04-26T19:01:36.700 回答