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

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

与其以可能不太好的方式重新发明轮子，不如直接使用现有的模块：

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

Answer 2

我假设你有一个有效单词的列表，其实你并不是在寻找一条单独的路径（为什么要优化这个呢），而是想要找到很多条路径。这可以通过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提供的示例单词。

如果你真的想自己实现这些算法，可以在维基百科上找到很多相关的描述。经典的单源最短路径算法是Dijkstra算法，而经典的所有点对之间的最短路径算法是Floyd-Warshall算法。

Answer 3

如果你真的想自己重新发明轮子，也许这个会对你有帮助（注意：这个代码使用了集合字面量，所以至少需要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))