我相信你们都听说过“文字游戏”，在这种游戏中，您试图通过一次更改一个字母来将一个单词更改为另一个单词，并且只浏览有效的英语单词。我正在尝试实现一个 A* 算法来解决它（只是为了充实我对 A* 的理解），并且需要的东西之一是最小距离启发式。
也就是说，这三个突变之一可以将任意字符串 a 变成另一个字符串 b 的最小数量：
1）将一个字母改为另一个字母
2) 在任意字母之前或之后的某个位置添加一个字母
3）删除任何字母
Examples
aabca => abaca:
aabca
abca
abaca
= 2
abcdebf => bgabf:
abcdebf
bcdebf
bcdbf
bgdbf
bgabf
= 4
我尝试过很多算法；我似乎找不到一个每次都能给出实际答案的人。事实上，有时我不确定我的人类推理是否能找到最佳答案。
有谁知道用于此类目的的算法？或者也许可以帮我找到一个？
（为了澄清，我要求一种算法，可以将任何任意字符串转换为任何其他字符串，而不管它们的英语有效性。）
你想要的最小编辑距离（或编辑距离） http://en.wikipedia.org/wiki/Levenshtein_distance:
两个字符串之间的编辑距离定义为将一个字符串转换为另一个字符串所需的最小编辑次数，允许的编辑操作是插入、删除或替换单个字符。它以弗拉基米尔·莱文斯坦 (Vladimir Levenshtein) 的名字命名，他于 1965 年考虑了这个距离。
确定编辑顺序的一种算法位于同一页面上here http://en.wikipedia.org/wiki/Levenshtein_distance#Computing_Levenshtein_distance.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
