問題タブ [boggle]

逆ボーグル問題を解こうとしています。簡単に言えば、単語のリストが与えられた場合、リスト内の単語と同じ数の単語が隣接する文字のシーケンスで見つかる 4x4 の文字グリッドを作成します (文字は直交方向と斜め方向の両方で隣接しています)。

既知のボードを使用して解決したくありません。これは簡単な TRIE 問題であり、人々の CS プロジェクトのためにここで議論/解決されています。

単語リストの例:

解決：

この問題は（私にとって）難しいです。私がこれまでに持っているアルゴリズム:

1. 入力の各単語について、それ自体が合法的にボードに表示される可能性のあるすべての方法のリストを作成します。
2. これらのボードに単語 #2 を配置するすべての可能な組み合わせを試し、競合のないものを保持します。
3. リストの最後まで繰り返します。
4. ...
5. 利益！！！（/を読んでいる人向け）

明らかに、実装の詳細があります。最初に最も長い単語から始めます。他の単語の部分文字列である単語を無視します。

約 0.4 秒で、7 文字の単語に対して 68,000 の可能なすべてのボードを生成できます。その後、さらに 7 文字のボードを追加すると、68k x 68k のボード x 7 の比較が必要になります。解決時間が氷河になります。

これを行うためのより良い方法があるはずです!!!!

いくつかのコード:

そして、次のように使用します。

疑似コードや、Boggle ボードで単語を再帰的に検索する方法を説明する再帰的な式を教えてもらえますか?

この関数は、ノードとそのデータをリンク リストに挿入する場所です。

この関数は、ボグル ボードからすべての単語を取得する場所です (ここで単語を出力すると、正しく出力されるため、この関数は正しく動作しているようです。

序文: これは、これに対するフォローアップの質問です。

R で Boggle Game Solver をプログラミングしました (ソース コードについては、この github ページを参照してください)。そのパフォーマンスは期待外れです。

これがどのように機能するかです...

13文字の単語候補の再現可能な例

このような小さなパス リストの場合、これはかなり高速です。しかし、13 文字の単語のパスの実際の数は 2,644,520 です。そのため、すべての候補を見つけるのに 1 分以上かかる場合があります。doSNOW を使用すると、検索を並列化して合計時間を大幅に短縮できますが、これには大きな欠点があります。通常のループを使用すると、単語がなくなった時点で終了/中断できます。見つかった。これは、並列プロセスでは明らかではありません (不可能ですか?)。

私の質問は、このタスクのためのより良い関数/アルゴリズムを考えてもらえますか? 一部のWeb サイトでは、数秒でボーグル ゲームの解決策が提供されます...可能な文字の組み合わせをすべて生成し、結果をデータベースに保存するか (!)、そうでない場合は、より優れたアルゴリズム (およびおそらくコンパイルされた言語) を使用してそれらを達成しています。結果。

何か案は？

文字列が完全な単語であるかどうかを確認する方法についてはいくつかの回答が見つかりましたが、文字列が単語の最初の部分であるかどうかを確認する方法はありません。

たとえば、"c"、"b"、"cong" (おめでとう、合同など)、または "exa" (例、調べるなど) に対しては true を返しますが、"congx" に対しては false を返す関数が必要です。 "、"qt"、またはその他の意味不明な表現。

これについては、いくつかの方法があると思います。戦略の大まかな概要を教えていただければ幸いです。Boggle ソルバーを作成しようとしています。ありがとう！

以下は、Boggle 内のすべての単語を検索するための (醜い) アルゴリズムです。

このアルゴリズムの Big-O ランタイムは? だと思いますがO((N²)!)、よくわかりません。

時間の複雑さはどうなりますか? これがO(n!)であることを避けたいだけです。深度優先検索を使用すると、時間の複雑さはO(n^2)になりますか?

これについて正しい方法で考えているかどうかはわかりません。

深さ優先検索を使用するとは、最初の文字から深さ優先検索を開始し、次に 2 番目の文字から開始するという意味です。

それは必要ですか？

注:
元の問題は、クロスワード/ボグル ボードですべての可能な単語を見つけることです。単語が辞書にあるかどうかを調べるためにトライ データ構造を使用することを考えていますが、単語自体を生成する方法を考えています。