n x mのゲーム盤上で長さlのすべての可能な行を調べる時間計算量は?
たとえば、三目並べボードは 3x3 で、線は長さ 3 として定義されます。8 つの可能な行があります。また、9x9 のボードで、勝つためには長さ 5 のラインが必要であるというルールを想像することもできます。n、m、lの値が異なる可能性のあるすべての行を調べることの複雑さをどのように特徴付けますか?
これは、ゲーム ツリーを将来のゲーム状態にトラバースすることを考慮していないことに注意してください。ボードの現在の状態を調べて、現在の状態に勝者がいるかどうかを確認するだけです。
明らかに、水平、垂直、および対角線を確認する必要があります。
n2つの値が等しくない場合、n が常に大きい方の数になるようにボードが配置され、横向きに配置されていると仮定しましょう」(超高層ビル スタイルではなく、レゴ スタイル) m。
水平線はn * (m - l)数になります。
縦線はm * (n - l)本数になります。
対角線は(m - l) * (n - l)、またはm*n - l*m - l*n + l*l
と仮定すると、2 次元のボードで予想されるように、n >= m > l内にあると安全に言えます。O(n^2)
結果が出ないことはわかってl > n >= mいます。n = m = l定数 ( ) があるとします2*n + 2。n = l > m対角線や垂直線をチェックする必要がなく、線だけをチェックする必要があるため、さらに良いケースが残っている場合m. の場合n > l > m、再び垂直線を除外できますが、対角線を考慮する必要があります。いずれにせよ、対角線、垂直線、および水平線を実行するよりも少なくなります。
ただし、 phant0m のコメントに基づいて実行できる最適化があります。最後の移動が何であったかを知っている必要があります。
移動が行われた場合、ボードに勝者がいないときに行われたと安全に想定できます。したがって、移動後にボードに勝利条件がある場合、それは最新の移動の結果として形成されたに違いありません。したがって、この情報が与えられた場合の最悪のシナリオは、ウィニング ラインが最後の動きで形成されることです。l - 1したがって、各方向 (水平、垂直、前方斜め、後方斜め) に伸びる 4 つの線分を確認する必要があります。これは の合計です。4 * (2*l - 1)安全に に入れO(l)ます。追加の座標 (最新の動き) を 1 つだけ保存する必要があることを考えると、これは最も賢明な最適化です。