这是旅行商问题的变化吗？

Question

我对两个单词列表的功能感兴趣,这两个单词列表将返回它们之间的顺序不可知的编辑距离.

也就是说,参数将是两个(例如空格分隔)单词列表,返回值将是列表中单词的编辑(或Levenshtein)距离的最小总和.

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

我的直觉(没有用计算机科学课程培养)没有找到任何其他解决方案而不是使用蛮力:

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

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

对我来说这听起来有点像旅行推销员的问题.是吗,你会如何解决我的特定问题？

Answer 1

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

那么你的问题可以被描述为"最小加权二分匹配",或者等价地,"最大加权二分匹配".这也可以在多项式时间内完成(比旅行推销员更快).见http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs