dac*_*man 20 algorithm edit-distance shortest-path hamming-distance
对于Data Structures项目,我必须找到两个单词之间的最短路径(例如"cat"和"dog"),一次只能更改一个字母.我们给出了一个拼字游戏单词列表,用于查找我们的路径.例如:
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题,但我正在寻找更好的东西(我用trie代表字典).
请给我一些更有效的方法(在速度和记忆方面)的想法.有些荒谬和/或挑战是首选.
我问过我的一个朋友(他是一名大三学生),他说这个问题没有有效的解决办法.他说我会学习为什么我参加算法课程.对此有何评论？
我们必须一个接一个地移动.我们不能去cat -> dat -> dag -> dog.我们还必须打印出遍历.
Jac*_*cob 15
新的答案
鉴于最近的更新,您可以尝试使用汉明距离作为启发式的A*.这是一个可接受的启发式算法,因为它不会高估距离
老答复
您可以修改用于计算Levenshtein距离的动态程序,以获得操作序列.
编辑:如果有一个恒定数量的字符串,问题可以在多项式时间内解决.另外,它是NP难的(维基百科都有)...假设你的朋友正在谈论NP难的问题.
编辑:如果您的琴弦长度相等,则可以使用汉明距离.
使用字典,BFS是最佳的,但所需的运行时间与其大小(V + E)成比例.对于n个字母,字典可能有〜a ^ n entires,其中a是字母大小.如果字典包含所有单词,但是应该在链的末尾,那么你将遍历所有可能的单词,但不会找到任何单词.这是图遍历,但大小可能呈指数级大.
您可能想知道是否可以更快地进行操作 - "智能地"浏览结构并在多项式时间内完成.我认为答案是否定的.
问题:
你有一个快速(线性)的方法来检查一个单词是否在字典中,两个单词u,v并且要检查是否有序列u - > a 1 - > a 2 - > ... - > a n - > v.
是NP难的.
证明:拿一些3SAT实例,比如
(p或q或不r)和(p或不q或r)
你将从0 000 00开始,并检查是否可以转到2 222 22.
第一个字符将是"我们完成了",三个接下来的位将控制p,q,r和两个接下来将控制子句.
允许的话是:
要从0 000 00生成2 222 22,您必须以这种方式执行:
(1)翻转适当的位 - 例如,分成四个步骤的0 100 111.这需要找到3SAT解决方案.
(2)将第一位更改为2:2 100 111.在此您将验证这确实是一个3SAT解决方案.
(3)更改2 100 111 - > 2 200 111 - > 2 220 111 - > 2 222 111 - > 2 222 211 - > 2 222 221 - > 2 222 222.
这些规则强制您不能作弊(检查).只有当公式可以满足并且检查是NP难时,才可能进入2 222 22.我觉得它可能更难(可能是#P或FNP),但我认为NP硬度就足够了.
编辑:您可能对不相交的集数据结构感兴趣.这将使您可以从彼此访问的词典和组词.您还可以存储从每个顶点到根或某个其他顶点的路径.这将为您提供一条路径,而不是最短路径.