相关疑难解决方法(0)

我遇到了编辑距离问题的这种变化:

设计一种将源字转换为目标字的算法.例如:从头到尾,在每一步中,你只需要替换一个字符,并且该字必须有效.你会得到一本字典.

它显然是编辑距离问题的变体,但在编辑距离中我不关心该单词是否有效.那么如何添加此要求来编辑距离.

分析显示这是我写的一个小字游戏的代码中最慢的部分:

def distance(word1, word2):
    difference = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

def getchildren(word, wordlist):
    return [ w for w in wordlist if distance(word, w) == 1 ]

笔记:

• distance()被调用超过500万次,其中大部分是来自getchildren,它应该让wordlist中的所有单词与word1个字母完全不同.
• wordlist被预先过滤为只有包含相同数量字母的单词,word所以它保证word1并word2具有相同数量的字符.
• 我是Python的新手(3天前开始学习它)所以对命名约定或其他风格的东西的评论也很受欢迎.
• 对于wordlist,使用"2 + 2lemma.txt"文件获取12dict单词列表

结果:

谢谢大家,通过不同建议的组合,我现在运行程序的速度提高了两倍(除了我自己在询问之前做的优化之外,所以从初始实现开始,速度提高了4倍)

我测试了2组输入,我称之为A和B.

优化1:迭代word1,2 ...的索引

for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

使用迭代迭代字母对zip(word1, word2)

for x,y in zip …

根据我所做的大部分读数,当"向前"和"向后"边界首先相交时,称双向搜索算法终止.然而,在人工智能:现代方法的第3.4.6节中,Russel和Norvig说:

通过检查目标测试以查看两个搜索的边界是否相交来实现双向搜索; 如果他们这样做,就找到了解决方案.重要的是要意识到找到的第一个解决方案可能不是最优的,即使这两个搜索都是广度优先的; 需要进行一些额外的搜索,以确保跨越差距没有捷径.

我已经考虑了这个陈述很长一段时间了,但我找不到这种行为的例子.任何人都可以提供一个示例图,其中双向BFS或A*搜索的前向和后向边界之间的第一个交叉点不是最短路径吗？

编辑:显然,BFS无法在加权图中找到最短路径.听起来这段摘录指的是无向图上的双向BFS.或者,我有兴趣在加权图上看到使用双向A*的反例.

最近我接受了采访,我被要求编写一个算法来查找从特定单词到给定单词的最小1个字母变化数,即Cat-> Cot-> Cog-> Dog

我不希望问题的解决方案只是指导我如何在此算法中使用BFS？