使用三個字母的單詞優化的寬度優先搜索

我在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秒。有沒有更快的方法來做到這一點？

來源

2011-02-25 Zeta Two

兩個單詞之間的路徑是什麼？ – 2011-02-25 15:13:48

說明：路徑是一系列單詞，其中每個單詞是通過交換前一個單個字母生成的。 – 2011-02-25 15:32:04

如果你想推倒重來，也許這將有助於（NB這已面值因此在需求至少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))

來源

2011-02-25 15:25:01 Duncan

這是一個非常棒的解決方案。我的運行時間從80秒改爲0.5秒。 – 2011-02-25 16:08:30

取而代之的可能是次優的方式重新發明輪子的：利用現有的模塊：

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

來源

2011-02-25 15:12:03

如何設計圖表橫向加速他的算法？我會成爲第一個吃我自己的話的人，但是如果不增加開銷，這似乎就會有相同的表現。 – 2011-02-25 15:17:09

我假設你有有效的單詞列表，你實際上是不是在找一個單一的路徑（爲什麼你會在乎優化能），但很多路徑。這可以用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。

來源

2011-02-25 15:59:25

不錯。我首先想到'makeGraph'可能會有一個完整的有效單詞列表的不可行的複雜性，但我發現的列表有668個單詞，這只是222,778次迭代。絕對值得，尤其是如果你做了'makeGraph'並且之後計算了很多不同的路徑。 – 2011-02-25 16:14:26

這是對我提出的問題自然而然的問題的一個很好的回答。整個事情實際上是學校任務的一部分，所以我一次只做這一步，並試圖自己弄清楚大部分細節。 *：我們鼓勵在線尋求信息，所以這不是欺騙= D） – 2011-02-25 16:22:15

使用三個字母的單詞優化的寬度優先搜索

回答

相關問題