Поиск в ширину с использованием трехбуквенных слов, оптимизация - PullRequest
Новая
       37

Поиск в ширину с использованием трехбуквенных слов, оптимизация

4 голосов
/ 25 февраля 2011

Я использую алгоритм поиска в ширину в 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 секунды. Есть ли более быстрый способ сделать это?

Ответы [ 3 ]

4 голосов
/ 25 февраля 2011

Я предполагаю, что у вас есть список допустимых слов, и вы на самом деле ищете не один путь (почему вы хотите оптимизировать для этого), а множество путей.Это можно сделать довольно легко с помощью 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 .Классический алгоритм кратчайшего пути с одним источником - Дейкстры , а классический алгоритм кратчайшего пути всех пар - Floyd-Warshall .

2 голосов
/ 25 февраля 2011

Если вы хотите заново изобрести колесо, возможно, это поможет (примечание: для этого установлены литералы, поэтому требуется как минимум 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))
0 голосов
/ 25 февраля 2011

Вместо того, чтобы изобретать колесо, возможно, неоптимальным способом: используйте существующие модули:

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

...