8

0と1のグリッドが与えられているとします。目標は、一連の「反転」操作を実行して、グリッドをすべてゼロのグリッドに変えることです。グリッド内の位置（x、y）を反転すると、（xと同じ行または列のすべてのビット） 、y）反転します。

この問題を解決するために使用できる効率的なアルゴリズムを知っている人はいますか？

4

1 に答える 1

29

これを解決する 1 つの可能な方法は、実数の代わりに 0 と 1 だけを使用することを除いて、この問題を線形連立方程式として扱うことです。

数値 0 と 1は、演算 XOR と AND の下でフィールドを形成します (ちなみに、このフィールドはGF(2)と呼ばれます)。つまり、2 つのビットを XOR することで「加算」でき、AND することで 2 つのビットを「乗算」できます。XOR と AND の動作は、通常の乗算​​と加算の多くの特性と一致することがわかります。たとえば、乗算と加算は交換可能で結合的であり、乗算は加算に分配されます。これらのプロパティは、ガウス消去法を使用して 0 と 1 の線形連立方程式を解くのに十分であることがわかります。たとえば、ガウスの消去法を使用して、次の線形連立方程式を解くことができます。

x XOR z = 1
x XOR y XOR z = 0
y XOR z = 0

したがって、XOR と AND を使用した線形連立方程式で問題を表現できれば、このフィールドに対して標準のガウス消去法を使用するだけで多項式時間で問題を解くことができます。

これを行うには、まず、ビットを反転することは、1 で XOR することと同じであることに注意してください。

  • 0 排他的論理和 1 = 1
  • 1 XOR 1 = 0

これは、行と列全体を切り替えると、その行と列のすべてを値 1 で XOR することと同じになることを意味します。

ここで、0 と 1 の m × n 行列があるとします。A[i][j] は、i 番目の行と j 番目の列の数値の値を示します。(i, j) を切り替えると、同じ行と列にあるすべての要素が切り替えられるため、(i, j) を切り替えることは、元の行列 A を次のような新しい行列 A に XOR することと同じであるとイメージできます。

0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
1 1 ... 1 1 1 ... 1
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0

ここで、1 は行 i と列 j にあり、0 はそれ以外の場所にあります。

グリッド内のすべての位置が、これらの「トグル マトリックス」の 1 つを生成することに注意してください。操作「フリップ (i, j)」を実行すると、現在のマトリックスとトグル マトリックス番号 (i, j) の XOR 演算が行われます。

もう 1 つの重要な観察事項として、この問題に対する最適な解決策 (操作の数が最も少ない解決策) は、同じ位置を 2 回反転することはありません。この理由は、XOR 自体が反転するためです。XOR a = 0 です。したがって、同じ位置を 2 回反転するソリューションは、2 つの反転を削除して短いソリューションを取得することで短縮できます。さらに、XOR は結合的かつ可換であるため((x XOR y) XOR z = x XOR (y XOR z)、および x XOR y = y XOR x)、最適な結果を得るためにフリップを実行する順序は問題ではありません。解決。どのフリップを行うかがわかったら、好きな順序でフリップを実行するだけです。

これらすべてを組み合わせると、可能なフリップごとに、そのフリップを実行する必要があるかどうかを判断しようとしています。ご注文、数量は問いません。

ここで、実際の線形連立方程式にたどり着きます。開始マトリックス A と、実行できるさまざまなフリップごとに 1 つずつ、さまざまな「トグル マトリックス」が与えられます。位置 (i, j) のトグル マトリックスを T[i, j] とします。次に、新しい変数 b[i, j] を 0 または 1 の値として導入し、実際に位置 (i, j) を反転する必要があるかどうかを示します。このセットアップを考えると、b[i, j] の値のセットを探しています。

A XOR b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = 0

ここで、0 はゼロ行列です。機能する b の選択肢を見つけることができれば、解決策があります。そうでない場合、解決策はありません。問題は、それらをどのように見つけるかです。

これを行うために、上記のシステムに 1 つの小さな変更を加えます。この式の両辺を A で XOR してみましょう。A XOR A = 0 であるため、左辺から A を相殺します。A XOR 0 = A なので、これは A を右側に移動します。今、私たちは持っています

b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = A

最後に、もう 1 つ変更を加えます。A と T[i, j] を行列として表現するのではなく、行優先の列ベクトルとして表現しましょう。これは、上記の線形連立方程式が、実際には行列の和ではなく、列ベクトルの和と考えることができることを意味します。

取引を成立させるために、行列 T を定義しましょう。ここで、T の最初の列は T[1, 1]、T の 2 列目は T[1, 2]、...、T の mn 列目です。は T[m, n] です。次に、b = (b[1, 1], b[1, 2], ..., b[m, n])^T としましょう (ちなみに、これは転置です)。その場合、上記のシステムを次のように書き換えることができます。

Tb = A

美しいです！ここで、T に b を掛けると行列 A が得られるようなベクトル b を解こうとしています。前述のように、XOR と AND を使用した 0 と 1 は体を形成するため、標準のガウス消去法を使用してこのシステムを解くことができます。

では、これはどのくらい効率的ですか？行列 T のサイズは mn × mn です。したがって、ガウス消去法を実行すると O(m 3 n 3 ) の時間がかかります。これは大きいですが、適度に小さいグリッドではそれほど悪くはありません。どのエントリがトグルされるかを単純に把握することで、時間 O(m 2 n 2 )でグリッドを構築することもできます。全体として、これにより問題の O(m 3 n 3 ) アルゴリズムが得られます。わーい！

ゲーム "Lights Out"のソルバーの実装があります。これは、トグルが行と列全体を反転するのではなく、(i, j) のすぐ近くのライトのみを反転することを除いて、この問題と非常によく似ています。これはまったく同じアプローチに基づいているため、コードを取得して開始点として使用したい場合は、おそらくこのソルバーを短時間でコーディングできます。読みやすくするためにコードの関連部分にコメントを追加しようとしましたので、うまくいけば便利です。

お役に立てれば！

于 2013-01-05T07:15:44.943 に答える