3

行列M*Nがあります。マトリックス要素は黒または白のいずれかです。同じ色の領域の隣接する要素を呼びます。任意の領域を選択してその色を反転できます（つまり、すべての要素の色を変更できます）。そのような行列が与えられた場合、行列全体を黒または白にするために必要な最小数のフリップを見つけます。

解決策：グラフの問題のように見えます。行列要素はグラフの頂点です。対応する行列要素が「隣接」であり、同じ色である場合、頂点は接続されます。答えは、グラフ内 の連結成分の数です。

それは意味がありますか？

修正された解決策： @ypercubeと@Billiskaのおかげで、解決策は次のように修正されるはずです。

  • （上記のように）連結成分を見つけて、それらの成分のグラフを検討します。
  • グラフの中心を見つけて裏返し、新しいグラフを作成し、グラフに頂点が1つだけ含まれるまで繰り返します。

グラフの中心を反転すると、反転の数が最小限になることを証明する必要があります。

4

3 に答える 3

5

あなたは解決策を提案しました：

グラフの問題のようです。行列要素はグラフの頂点です。対応する行列要素が「隣接」であり、同じ色である場合、頂点は接続されます。答えは、グラフ内の連結成分の数です。

そして改善：

次に、「黒」と「白」の連結成分の数を見つけて、両方のうち最小のものを選択する必要があります。

これはかなり良いようですが、答えは最初のように単純ではありません。このマトリックスを考えてみましょう。ここでは、13個の黒連結成分と4個の白成分があります。：

B w B w B w B w B
w w w w B w w w w
B w B B B B B w B
w w B B B B B w w
B B B B B B B B B  
w w B B B B B w w
B w B B B B B w B
w w w w B w w w w
B w B w B w B w B

ただし、最小限の解決策は2回の移動だけです。最初に、中央の大きな黒のコンポーネントを（白に）反転します。その結果、反転した1つのコンポーネントと4つの白いコンポーネントが1つのコンポーネントに接続されます。これを黒に反転すると、すべてのボードが黒になります。

したがって、この場合、最小値は4回ではなく、2回の移動です。

したがって、接続済み（黒と白のコンポーネント）を確立すると、これらのコンポーネント間の接続のグラフが作成されます（@Biliskaの回答のように）。上記のマトリックスのグラフは次のとおりです。

        B
        |
     B--w--B
        |
    B   |   B
    |   |   |
B---w---B---w---B
    |   |   |
    B   |   B
        |
     B--w--B
        |
        B

ここで、グラフの中心、または中心点の1つだけを見つける必要があります。たとえば、他のノードBまでの最大距離d（A、B）が最小であるノードA（この最小最大距離は「離心率」と呼ばれることもあります） 。上のグラフの場合、中心点が1つだけあり、「離心率」が2であることが図から明らかです。

離心率がである場合、長さまたは（またはノードの）nの「最大」パスが少なくとも1つあります。私たちの場合には：2n-12n2n2n+1

B-w-B-w-B

これらのグラフのどのパスでもノードは順番に白黒であるため、必要な最小限の変更が正確にn（この場合は2）であり、常に中央領域を変更することで達成できることを証明するのは難しくありません。

于 2012-11-26T17:56:45.920 に答える
3

この問題は最短経路問題として解決できます。

G=(V,E)問題を状態グラフとしてモデル化しますV = possible states (matrix states)。E = { (u,v) | can move from state u to state v with single "flip" }

グラフができたら、最短経路アルゴリズムを使用するだけです。

グラフは重み付けされていないため、最短経路アルゴリズムとしてBFSを使用できます。許容できるヒューリスティック関数が見つかった場合（A *アルゴリズムを使用できる場合もあります）、これは降下ヒューリスティックを使用した方が高速であると予想されます。

于 2012-11-26T18:09:20.527 に答える
3

まず、実際には問題を領域の接続グラフとしてモデル化する必要があるのに、問題をセルの接続グラフとしてモデル化しようとしているのは間違いです。

例として

b w b w b
w b b w b
w w b b w

次のように面積表記に変換されます。

1 2 3 4 5
6 3 3 4 5
6 6 3 3 7

これは次のように表されます。

1 - 2   4 - 5
|   | /     |
6 - 3 - - - 7

次に行うことはflip、エリアをマージする操作を繰り返し実行することです。ほとんどの接続がある領域を貪欲に反転させることが正しいかどうかはわかりません。

たとえば、エリア3には4つの接続があるため、最初にエリア3を反転します。それから私は得る：

1       5
  \   /
   (3)

次に、2つの接続があるため、エリア3をもう一度反転します。

   (3)

終わり

flipしたがって、操作には、隣接するすべてのノードを反転されているノードにマージする効果があることがわかります。

編集：実際、ほとんどの接続で貪欲にフリップする領域は最適ではありません。前にコメントした1次元の例を見てください。

入力：

             middle
                v
b w b w b w b w b w b w b w b w b
<---4 times--->   <---4 times--->

どのエリアでも最も多くの接続が2次であることがわかります。しかし、最も効率的なアルゴリズムは、中央のエリアを反転することだけを選択します。

于 2012-11-26T18:18:21.083 に答える