3

最近インタビューを受けましたが、特定の単語から特定の単語に到達するための1文字の変更の最小数を見つけるアルゴリズムを作成するように依頼されました。つまり、Cat-> Cot->Cog->Dogです。

問題の解決策を知りたくないのですが、このアルゴリズムでBFSを使用する方法を教えてください。

4

4 に答える 4

5

このスクラブル リストによると、猫と犬の間の最短経路は ['CAT', 'COT', 'COG', 'DOG'] です。

from urllib import urlopen

def get_words():
    try:
        html = open('three_letter_words.txt').read()
    except IOError:
        html = urlopen('http://www.yak.net/kablooey/scrabble/3letterwords.html').read()
        with open('three_letter_words.txt', 'w') as f:
            f.write(html)

    b = html.find('<PRE>') #ignore the html before the <pre>
    while True:
        a = html.find("<B>", b) + 3
        b = html.find("</B>", a)
        word = html[a: b]
        if word == "ZZZ":
            break
        assert(len(word) == 3)
        yield word

words = list(get_words())

def get_template(word):
    c1, c2, c3 = word[0], word[1], word[2]
    t1 = 1, c1, c2
    t2 = 2, c1, c3
    t3 = 3, c2, c3
    return t1, t2, t3

d = {}
for word in words:
    template = get_template(word)
    for ti in template:
        d[ti] = d.get(ti, []) + [word] #add the word to the set of words with that template

for ti in get_template('COG'):
    print d[ti]
#['COB', 'COD', 'COG', 'COL', 'CON', 'COO', 'COO', 'COP', 'COR', 'COS', 'COT', 'COW', 'COX', 'COY', 'COZ']
#['CIG', 'COG']
# ['BOG', 'COG', 'DOG', 'FOG', 'HOG', 'JOG', 'LOG', 'MOG', 'NOG', 'TOG', 'WOG']

import networkx
G = networkx.Graph()

for word_list in d.values():
    for word1 in word_list:
        for word2 in word_list:
            if word1 != word2:
                G.add_edge(word1, word2)

print G['COG']
#{'COP': {}, 'COS': {}, 'COR': {}, 'CIG': {}, 'COT': {}, 'COW': {}, 'COY': {}, 'COX': {}, 'COZ': {}, 'DOG': {}, 'CON': {}, 'COB': {}, 'COD': {}, 'COL': {}, 'COO': {}, 'LOG': {}, 'TOG': {}, 'JOG': {}, 'BOG': {}, 'HOG': {}, 'FOG': {}, 'WOG': {}, 'NOG': {}, 'MOG': {}}

print networkx.shortest_path(G, 'CAT', 'DOG')
['CAT', 'OCA', 'DOC', 'DOG']

おまけとして、最も遠くまで取得できます。

print max(networkx.all_pairs_shortest_path(G, 'CAT')['CAT'].values(), key=len)
#['CAT', 'CAP', 'YAP', 'YUP', 'YUK']
于 2012-08-05T01:56:01.813 に答える
4

一見、レーベンシュタイン距離のことを考えていましたが、BFS を使用する必要があります。ですから、ツリーを構築することから始めるべきだと思います。与えられた単語はルートである必要があり、次のノードは最初の文字が変更された単語です。次の次のノードは 2 番目の文字が変更されました。グラフを作成するときは BFS を使用し、新しい単語を見つけたらパスの長さを保存します。アルゴリズムの最後に最小距離を選択します。

于 2012-08-04T20:59:53.847 に答える
0

宛先単語からソース単語への有向非巡回グラフの作成を幅方向に開始し、辞書検索を行って、単語を追加する際にツリーの前の単語を見たかどうかを確認すると、次に、ソース単語の最初の出現により、「ターゲット単語」から「ソース単語」への逆方向の最短パスが得られるはずです。

これから、「ソース」から「ターゲット」へのパスを出力できます

于 2012-08-05T05:07:09.090 に答える
0

  1. パス セットの最初の単語から始めます。

  2. パス セット内のいずれかのパスの末尾の単語が目的の単語である場合、停止します。そのパスが目的のパスです。

  3. パス セット内の各パスを、そのパスで始まるが 1 単語長いすべての可能なパスに置き換えます。

  4. 手順 2 に進みます。

于 2012-08-04T21:07:38.030 に答える