5

N x M塗装すべき板があります。行全体または列全体を一度にペイントできます。すべてのボード セルの色のN x Mマトリックスを指定して、ボードをペイントするためのペイント操作の最小数を見つけます。

例: 3 x 3 のボードを次のようにペイントする必要があります (R - 赤、B - 青、G - 緑):

B、B、B
B、R、R
B、G、G、G

描画操作の最小数は 4 です。

  • 行 0 を青で塗りつぶす
  • 行 1 を赤で塗りつぶす
  • 行 2 を緑で塗りつぶす
  • 列 0 を青でペイント

どのように解決しますか？

4

2 に答える 2

6

これは楽しい問題のように見えます。疑似コードで試してみましょう。

Function MinPaints(Matrix) Returns Integer
    If the matrix is empty return 0
    Find all rows and columns which have a single color
    If there are none, return infinity, since there is no solution
    Set the current minimum to infinity
    For each row or column with single color:
        Remove the row/column from the matrix
        Call MinPaints with the new matrix
        If the result is less than the current minimum, set the current minimum to the result
    End loop
    Return the current minimum + 1
End Function

これで問題は解決すると思いますが、最適化などは試していません。これは十分に速くないかもしれませんが、わかりません。この問題が指数関数的時間内に解決できるとは思えません。

このアルゴリズムが例をどのように解決するかを次に示します。

BBB
BRR
BGG
|
+---BRR
|   BGG
|   |
|   +---RR
|   |   GG
|   |   |
|   |   +---GG
|   |   |   |
|   |   |   +---[]
|   |   |   |   |
|   |   |   |   Solvable in 0
|   |   |   |
|   |   |   Solvable in 1
|   |   |
|   |   +---RR
|   |   |   |
|   |   |   +---[]
|   |   |   |   |
|   |   |   |   Solvable in 0
|   |   |   |
|   |   |   Solvable in 1
|   |   |
|   |   Solvable in 2
|   |
|   Solvable in 3
|                       BB
+---Another branch with RR ...
|                       GG
Solvable in 4
于 2012-04-28T14:32:02.037 に答える
3

手始めに、十分な情報に基づいた網羅的な検索を試すことができます。

状態グラフを次のようG=(V,E)にV = {all possible boards}しE = {(u,v) | you can move from board u to v within a single operation}ます。

  • 事前にグラフを生成する必要がないことに注意してくださいsuccessors(board)。指定されたボードのすべての後継者を返す関数を使用して、その場でグラフを生成できます。

また、ボード1h:V->Rを評価する許容ヒューリスティック関数も必要です。

これで、 A*または双方向BFS 検索 [または両方の組み合わせ]を実行できます。ソースはホワイト ボードになり、ターゲットは要求されたボードになります。許容ヒューリスティック関数を使用しているため、A* は完全(存在する場合は常に解決策を見つける) であり、最適(最短の解決策を見つける) であるため、最適な解決策を見つけます。[双方向 BFS についても同様]。

欠点:

  • アルゴリズムは通知されますが、指数関数的な動作をします。しかし、それが面接の質問であれば、非効率的な解決策の方が解決策がないよりはましだと思います。
  • 完全で最適ですが、解決策がない場合、アルゴリズムは無限ループ、またはすべての可能性を使い果たしたことに気付くまで、少なくとも非常に長いループに陥る可能性があります。

(1) 許容ヒューリスティックの例はh(board) = #(miscolored_squares)/max{m,n}

于 2012-04-28T14:25:57.640 に答える