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

Question

我在 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 秒。 有没有更快的方法来做到这一点？

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 ，经典的所有对最短路径算法是 弗洛伊德-Warshall。

Answer 2

如果你确实想重新发明轮子，也许这会有所帮助（注意，这已经设置了文字，因此至少需要 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))

Answer 3

不要以可能次优的方式重新发明轮子：使用现有模块：

http://pypi.python。 org/pypi/altgraph/0.8