python - 三字母词广度优先搜索，优化

Question

我在 Python 中使用广度优先搜索算法来查找从一个三字母单词到另一个单词的最短“路径”。我已经让它工作了，但性能很糟糕，我怀疑我的话 child 生成功能。

基本上，对于我从队列中弹出的每个单词，我都会生成所有其他可以通过交换一个字母形成的三个字母的单词。该函数的工作原理如下:

#Pseudo code
For each position (1-3)
    For each letter (a-z)
        create a new word by exchanging the letter at the position
        if this word is a valid word and is not used earlier
             add it to the return list

return the list

这通常需要大约 0.03 秒。有更快的方法吗？

Answer 1

我假设您有一个有效单词列表，并且您实际上并不是在寻找单一路径(您为什么要为此进行优化)，而是在寻找很多路径。这可以通过 networkX 轻松完成。 :

from networkx import Graph
from networkx.algorithms.shortest_paths import shortest_path, all_pairs_shortest_path

from itertools import combinations

WORDS = {'cat', 'hat', 'sat', 'car', 'cad', 'had', 'pad', 'pat', 'can', 'man'}

def makeGraph(words):
    """ create a graph where nodes are words and two words are 
        connected iff they have one different letter """

    G = Graph()

    # all word combinations
    for a,b in combinations(WORDS,2):
        # number of different letters
        diff = sum(1 for x,y in zip(a,b) if x!=y)
        if diff == 1:
            G.add_edge(a,b)
    return G

g = makeGraph(WORDS)
# path between two words
print shortest_path(g, 'cat', 'pad')

# generating all shortest paths is way more efficient if you want many paths
paths = all_pairs_shortest_path(g)
print paths['cat']['pad']

感谢@Ducan 提供的示例词。

如果您真的想自己实现这些算法，可以在 wikipedia 找到大量说明。 .经典的单源最短路径算法是Dijkstra's经典的所有对最短路径算法是Floyd-Warshall .