3

編集：新しい質問。この質問は当初考えていたよりも難しいと思われるため、NP 複合体の可能性があるため、別の質問があります。使用される文字数の最大化に近づくことができる有用なアルゴリズムは何ですか?

カードゲームの Scrabble Slam に基づいたプログラムを作成することに触発されました! ただし、私はアルゴリズムに慣れていないため、この問題を効率的に解決する方法が思いつきません。

英語で有効な 4 文字の単語を含む文字列から始めます。一度に 1 つの文字をその単語に配置して、その文字を配置することで新しい辞書で有効な単語を形成できます。あなたが持っている文字は、アルファベットの文字と同じです。

たとえば、最初の単語が「カート」だった場合、これは有効な一連の動きである可能性があります。

砂 --> 正気 --> 正弦 --> 線 --> リン --> ピン --> フィン など。

目標は、アルファベットの文字をできるだけ多く (文字を複数回使用せずに) 使用して、シーケンス内の単語の数を最大化することです。

私のアルゴリズムは、最長のシーケンスを見つけることができません。最長のものを推測するだけです。

最初に、開始単語の 1 文字を変更して形成できるすべての単語のリストを取得します。そのリストは「adjacentList」と呼ばれます。次に、adidasList 内のすべての単語を調べて、それらの単語の中で最も隣接する単語がどれかを見つけます。隣接する単語が最も多い単語がどれであっても、開始単語を次の単語に変えることを選択します。

たとえば、sane という単語は 28 の別の単語に変換でき、sine という単語は 27 の別の単語に変換でき、単語 line は別の 30 の単語に変換できます。より多くの単語を綴ることができます。

この問題を解決する最善の方法は何でしょうか? どのようなデータ構造が最適でしょうか? コードを改善して、より効率的で冗長なものにするにはどうすればよいですか?

##Returns a list of all adjacent words.  Lists contain tuples of the adjacent word and the letter that
##makes the difference between those two words.

def adjacentWords(userWord):
    adjacentList, exactMatches, wrongMatches = list(), list(), str()
    for dictWords in allWords:
        for a,b in zip(userWord, dictWords):
            if a==b: exactMatches.append(a)
            else: wrongMatches = b
        if len(exactMatches) == 3:
            adjacentList.append((dictWords, wrongMatches))
        exactMatches, wrongMatches = list(), list()
    return adjacentList
    #return [dictWords for dictWords in allWords if len([0 for a,b in zip(userWord, dictWords) if a==b]) == 3]


def adjacentLength(content):
    return (len(adjacentWords(content[0])), content[0], content[1])

#Find a word that can be turned into the most other words by changing one letter
def maxLength(adjacentList, startingLetters):
    return max(adjacentLength(content) for content in adjacentList if content[1] in startingLetters)

def main():
    startingWord = "sand"
    startingLetters = "a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z".replace(" ", "").split(',')

    existingWords = list()
    while True:
        adjacentList = adjacentWords(startingWord)
        letterChoice = maxLength(adjacentList, startingLetters)
        if letterChoice[1] not in existingWords:
            print "Going to use letter: "+ str(letterChoice[2]) + " to spell the word "+ str(letterChoice[1]) + " with "+ str(letterChoice[0]) + " possibilities."
            existingWords.append(letterChoice[1])
            startingLetters.remove(str(letterChoice[2]))
            startingWord = letterChoice[1]


main()
4

2 に答える 2

3

@Parseltongue与えられたタスクに最適な解決策はありますが、それを最適な方法で解決する既知の方法がないことに気付くかもしれません。このタスクは、NPクラスの問題の1つです。

このことを考慮：

sand --> [?]and

この時点で、のすべての可能な組み合わせを繰り返し処理して[?]and、基準に一致する単語を見つける必要があります。最悪の場合、ヒューリスティックがない場合、それは26回の反復です。

sand --> band, hand, land, wand

ここで、見つかったすべての単語を取得し、2番目の文字など
を繰り返します。繰り返しの量が指数関数的に増加することがわかります。

これは、ある意味でチェスの問題と非常によく似ています。コンピュータがどれほど強力であっても、組み合わせが多すぎるため、考えられるすべての動きを予測することはできません。

于 2011-08-12T09:10:00.020 に答える
0

私と友人は、データ構造とアルゴリズムのコースの研究室で、実際に同様のプログラムを (ただし Java で) 開発しました。タスクは、ある単語から別の単語への単語の最短チェーンを作成することでした。

1 つのノードが別のノードに接続されていて、それらが 1 文字だけ異なる場合、使用可能なすべての単語のツリーを作成しました。高速化のためには、辞書などのある種のハッシュテーブルを使用する必要があります。実際には、キーとして使用した単語から 1 文字を削除して、接続された単語が同じハッシュを持つという事実を利用しましたが、コードがないと説明するのは困難です。

最短チェーンを見つけるために、幅優先検索を使用しました。ただし、グラフ内の最短経路を見つけることは、最長経路よりも簡単です。詳細については、最長パスの問題を参照してください。

主な問題を解決するには、すべての単語を反復するだけです。ただし、速度が重要な場合は、優れた特別なヒューリスティック アルゴリズムを見つけようとする方が簡単な場合がよくあります。

于 2011-08-12T09:15:42.373 に答える