1

Python で次のようなダブル ワード スクエアを作成する方法を期待していました。単語の正方形で使用される単語を含む単語のリストがあります。私が考えることができる現在の方法は、4x4 グリッドよりも大きなものに対して非常に非効率的な「力ずく」の方法です。 

S C E N T 
C A N O E 
A R S O N 
R O U S E 
F L E E T

助けていただければ幸いです。

4

2 に答える 2

4

ここでグラフ理論/検索アルゴリズムが役立ちます。ボードを次のようにレイアウトしたとします。

SCENT
CANOE
ARSON
ROUSE
?????

…そして、その最後の場所に固執する単語が 1 つ以上あること。ボードのこの状態 (上記) は、ツリー内のノードです。その場所に固執する単語が 5 つ残っているとしましょう。さらに 5 つの状態 (ノード) に移動できます。これは、プロセスの早い段階でより価値があります。

SCENT
?????
?????
?????
?????

繰り返しますが、これをツリー内のノードと考えてください。ここで、おそらく13の可能な単語があります。これらの 13 の選択肢のそれぞれが、12 の選択肢を持つノードに移動し、それらの 12 のそれぞれに 11 の選択肢がある、というようになります。探索しているツリーは次のようになります。

          ?
          |
        SCENT
        ?????
        ?????
        ?????
        ?????
    /---/ | \-----\----\
   /      |   \    \    \
  |       |    \    \    \
SCENT  SCENT    ?    ?    ?
CANOE  ARSON
?????  ?????   ... etc ...
?????  ?????
?????  ?????
| |    /  | \
| |   /   \  \
? ?  /     |  \
   SCENT   ?   ?
   ARSON
   CANOE
   ?????
   ?????

ブルート フォース ソリューションは、このツリーを完全に探索し、すべてのノードにアクセスします。ただし、通常、ノードの数は非常に多くなります。アイデアはそれを効率的に探索することです: 2 つの単語だけが埋められた「ノード」が有効な解決策に決してならないと判断できれば、その場で探索をやめることができます: そのノードとその下のすべてのノードを削除します。ブルートフォース検索に関するウィキペディアの記事では、次のように言及されています。

ブルート フォース アルゴリズムを高速化する 1 つの方法は、問題クラスに固有のヒューリスティックを使用して、検索スペース、つまり一連の候補ソリューションを削減することです。たとえば、8 クイーンの問題では、標準のチェス盤に 8 つのクイーンを配置して、どのクイーンも他のクイーンを攻撃しないようにすることが課題です。各クイーンは 64 マスのどこにでも配置できるため、原則として 648 = 281,474,976,710,656 通りの可能性があります。ただし、クイーンはすべて同じであり、同じマスに 2 つのクイーンを配置することはできないため、候補はすべて 64 マスのセットから 8 マスのセットを選択する可能な方法です。つまり、64 は 8 = 64!/56!/8! を選択します。= 4,426,165,368 の候補解 — 以前の見積もりの​​約 1/60,000。さらに、同じ行または同じ列に 2 つのクイーンを配置しても解決策にはなりません。

この例が示すように、少し分析するだけで多くの場合、解決策候補の数が劇的に減少し、扱いにくい問題が些細な問題に変わる可能性があります。

では、これを行うにはどうすればよいでしょうか。これは、正直なところ、賢くなければならない部分です。おそらく、できることは複数あります。たとえば、次の 2 つの単語が入力されている場合:

SCENT
CANOE
?????
?????
?????

これが有効な状態であるためには、SC、CA、EN、NO、および TE で始まる単語が必要であることがわかります。(最後の単語を入力すると、これらは垂直に沿った単語になります。) これらの接頭辞で始まる単語が不足している場合、垂直に可能な単語がないため、これは有効なソリューションを生成しません。 . それをすばやく判断できれば、この状態をすばやく排除でき、この状態から生じる可能性のあるすべての結果を取り除くことができます。これが総当たり攻撃の特に初期の段階である場合、これは価値があります。

すべての単語のすべてのプレフィックスのセットを生成することにより、O(1) 時間で「プレフィックス チェック」などを行うことができます。長さLのn語を想定すると、これには O( nL ) かかります。プレフィックスが有効かどうかを確認するには、それがセット内にあるかどうかを確認します。

もちろん、単語リストが (あなたの例のように) 考えられるすべての 5 文字の単語で構成されている場合、すべての接頭辞が問題ないため、これではどこにも到達しません。ただし、おそらくそのようなリストは提供されていません。

接頭辞セットを拡張して、接頭辞→その接頭辞を持つ単語のマップにすることができます。接頭辞に 1 つの単語しかない場合は、すぐにボードに追加できます。(それがそこに属していない場合、何もありません。) もちろん、これにより、ボードにさらに単語を配置することがより複雑になります。

グラフ理論はブルートフォースにも役立ちます。問題をグラフまたはツリーとして見ると、「ブルートフォース」は単なるツリー探索アルゴリズムであることがわかります。それは単なるノード自体であり、ノード間を移動する方法です。異なるそれら。

于 2013-10-22T00:12:59.377 に答える
1

共通の文字を持つ単語のペアのリストと、それらの単語の文字のインデックスを作成し、単語を正方形に配置する交差点の組み合わせが得られるまで、交差点のさまざまな組み合わせを検索します。

于 2013-10-21T23:19:07.823 に答える