algorithm - ボーグルを解く解の O(n)

Question

ボーグル ボードが n x n の場合、ボーグルを解く関数の最適な時間計算量 O(n) は?

n^2キャラクターごとに他のキャラクターを見なければならないからだと思い2(n-1)ます。インタビュアーは、これは辞書引きn^2用ではないと主張しました。O(1)

Answer 1

http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.htmlをご覧ください。動的計画法の解は O(D) であり、D は辞書のサイズです。

Answer 2

辞書に何ができるかはあまり明確ではありません。

少しばかげていますが、私の意見では正しい答えは次のとおりです。

boggle では、単語は (各文字から、この単語でまだ使用されていない隣接する (水平、垂直、または斜めの) 文字まで) 任意の方向に移動できるため、長さ の単語のL場合、単語の組み合わせは8^L、文字が複数回出現する組み合わせ。とにかく、一定であると考えるLと（使用される辞書が一定であるため）、この値も一定です。要約すると、特定の位置から始まる単語を見つけるには、 の時間複雑性がありO(1)ます。

したがって、残っているのは単語の開始位置であり、これはスペース内n^2にあるため、ボーグル ソルバーの時間計算量は でO(n^2)あり、正しいです。

前述したように、この議論は少しばかげていると思います。

問題は、ディクショナリが非常に大きいため、ディクショナリが定数であると見なしたくないことです。それは無限に大きいと仮定しますが、既存の単語O(1)のルックアップを実装します(これは辞書に使用できる唯一のクエリであり、特に単語の接頭辞のルックアップはありません)、さらに制限要因ではないと仮定します語長と比較すると、時間の計算量は指数関数的です。しかし、この演習では、検索が既存の単語に対してのみ成功するという仮定は間違っていると思います。n

別の考えられる仮定は、辞書に単語の接頭辞のルックアップがあることです (これは、指定された文字列で始まるが、必ずしも文字列と等しいとは限らない単語が存在するかどうかを返します)。この場合、限られた検索スペースを検索する (各文字を最大 1 回使用する)より優れた、より複雑なアルゴリズムを実装できます。単語の長さの制限要因はn^2、 (現在のボーグル ボードに含まれる) 単語がそれより長くなることはできないためです (各文字は 1 回しか使用できないため)。繰り返しますが、開始位置は spacen^2にあるため、愚かなパスベースのアルゴリズムの時間の複雑さはO(n^4)になるため、間違っています. 現在、この仮定の下でより良い時間複雑度を持つアルゴリズムは考えられません。

Answer 3

私はついにそれを理解しました。答えは、時間的に指数関数的であることが判明しました。

4X4 のボーグル グリッドを想像してみてください

ABCD
EFGH
IJKL
MNOP

A次に、たとえば、 ABCDHGFEIJKLPONM で始まる順序付けられたサブシーケンスのいずれも潜在的な単語です。AAEIMNOPLHDCBFJKG または AEIMNOPLHGFIK または ABCDHLPONMIEFGKJ で始まる順序付けられたサブシーケンスも同様です。次に、B で始まり、次に C で始まる可能性のある単語を調べる必要があります。

これを別の方法で見てみましょう。_ABCD のみを考慮する必要があるとします。ここで、 ;_などの開始文字を表しますX。次に、パワーセットに属する潜在的な単語は次のとおりです。

XD; XC; XCD; XB; XBD; etc.

したがって、各文字から始まる時計回りのらせんだけを考えると、すでに を見ていn^2*2^(n-1)ます。n^2グリッドがn by nそうであるため、4 by 4グリッドには 16 の可能な開始文字があります。そして2^(n-1)、各開始キャラクターが率いるパワーセットのおかげです。もちろん、時計回りのスパイラルだけが可能なパターンではありません。しかし、最初のパターンである Big-Omega(2^n) で時間の複雑さを既に確認できます。これは指数関数的です。