我在 Python 中使用广度优先搜索算法来查找从三个字母单词到另一个单词的最短“路径”。我已经让它工作了，但性能很糟糕，我怀疑我的单词儿童生成功能。
基本上，对于我从队列中弹出的每个单词，我都会生成所有其他可以通过交换一个字母来形成的三字母单词。该函数的工作原理如下：
#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 秒。有没有更快的方法来做到这一点？
我假设您有一个有效单词列表，并且您实际上不是在寻找单个路径（为什么要为此进行优化），而是在寻找很多路径。使用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 的，经典的全对最短路径算法是Floyd-Warshall。
如果您确实想重新发明轮子，也许这会有所帮助（注意这已经设置了文字，因此至少需要 Python 2.7）：
from collections import defaultdict
WORDS = {'cat', 'hat', 'sat', 'car', 'cad', 'had', 'pad', 'pat', 'can', 'man'}
D1 = defaultdict(set)
D2 = defaultdict(set)
D3 = defaultdict(set)
for w in WORDS:
D1[w[:2]].add(w)
D2[w[0]+w[2]].add(w)
D3[w[1:]].add(w)
def follows(w):
followers = set(D1.get(w[:2]).union(D2.get(w[0]+w[2]), D3.get(w[1:])))
followers.discard(w)
return followers
for w in WORDS:
print(w, follows(w))
而不是以可能次优的方式重新发明轮子：使用现有模块：