硬幣翻轉游戲：優化問題

Question

有一個矩形的硬幣網格，其中頭部由數值1表示，尾部由數值0表示。您使用2D整數數組表格（1到10行/包括列）。

在每次移動中，您在網格（第R行，第C列）中選擇任意單個單元格（R，C）並翻轉所有單元格中的硬幣（r，c），其中r在0和R（含），並且c在0和C之間，包括端值。翻轉硬幣意味着將單元格的值從零反轉爲一或一到零。

返回將網格中的所有單元格更改爲尾部所需的最小移動次數。這將永遠是可能的。

例子：

1111 
1111 
returns: 1 

01 
01 
returns: 2 

010101011010000101010101 
returns: 20 

000 
000 
001 
011 
returns: 6 

這是我的嘗試： 由於翻轉的順序並不重要，並作出此舉在硬幣上兩次不一樣作出動彈，我們只要找到所有不同的翻轉硬幣組合，並最大限度地減少好組合的大小（好的含義是那些能夠提供所有尾巴的組合）。

這可以通過製作一個由所有硬幣組成的集合來完成，每一個硬幣都由一個索引表示（即如果共有20個硬幣，這個集合將包含20個元素，給它們索引1至20）。然後製作所有可能的子集，並查看其中哪些給出了答案（即，如果在子集中的硬幣上移動給我們所有的尾部）。最後，儘量減少組合的大小。

我不知道我是否能夠清楚地表達自己......如果需要，我會發布代碼。 無論如何，這種方法太耗費時間和浪費，並且不可能用於大於20的硬幣（在我的代碼中）。 如何解決這個問題？

Answer 1

我認爲一個貪婪的算法就足夠了，每硬幣一步。

每一步都會翻轉板子的矩形子集。一些硬幣被包含在比其他硬幣更多的子集中：（0,0）左上角的硬幣存在於每個子集中，而右下方的硬幣僅存在於一個子集中，即包含每個硬幣的硬幣。

因此，選擇第一步是顯而易見的：如果必須翻轉右下角，請翻轉所有硬幣。消除可能的舉措。

現在，右下角硬幣的直接鄰居，只剩下一個剩餘移動可能會被翻轉。所以，如果這一舉措必須執行，那就做吧。評估鄰居的順序並不重要，因爲它們並不是彼此真正的替代品。但是，光柵圖案應該足夠了。

重複，直到完成。

這裏是一個C++程序：

#include <iostream> 
#include <valarray> 
#include <cstdlib> 
#include <ctime> 
using namespace std; 

void print_board(valarray<bool> const &board, size_t cols) { 
    for (size_t i = 0; i < board.size(); ++ i) { 
     cout << board[i] << " "; 
     if (i % cols == cols-1) cout << endl; 
    } 
    cout << endl; 
} 

int main() { 
    srand(time(NULL)); 
    int const rows = 5, cols = 5; 

    valarray<bool> board(false, rows * cols); 
    for (size_t i = 0; i < board.size(); ++ i) board[i] = rand() % 2; 
    print_board(board, cols); 

    int taken_moves = 0; 
    for (size_t i = board.size(); i > 0;) { 
     if (! board[ -- i ]) continue; 

     size_t sizes[] = { i%cols +1, i/cols +1 }, strides[] = { 1, cols }; 

     gslice cur_move(0, valarray<size_t>(sizes, 2), 
          valarray<size_t>(strides, 2)); 
     board[ cur_move ] ^= valarray<bool>(true, sizes[0] * sizes[1]); 

     cout << sizes[1] << ", " << sizes[0] << endl; 
     print_board(board, cols); 

     ++ taken_moves; 
    } 

    cout << taken_moves << endl; 
} 

Answer 2

你可以使用遞歸試驗。

您至少需要移動計數並傳遞向量的副本。您還需要設置一個最大移動截止點，以設置對搜索樹中每個節點出來的分支廣度的限制。請注意，這是一個「強力」辦法「

你的通用算法結構將是：

const int MAX_FLIPS=10; 
const unsigned int TREE_BREADTH=10; 

int run_recursion(std::vector<std::vector<bool>> my_grid, int current flips) 
{ 
    bool found = true; 
    int temp_val = -1; 
    int result = -1; 
    //Search for solution with for loops; if true is found in grid, found=false; 
    ... 
    if (! found && flips < MAX_FLIPS) 
    { 
     //flip coin. 
     for (unsigned int more_flips=0; more_flips < TREE_BREADTH; more_flips++) 
     { 
     //flip one coin 
     ... 
     //run recursion 
     temp_val=run_recursion(my_grid,flips+1) 
     if ((result == -1 && temp_val != -1) || 
       (temp_val != -1 && temp_val < result)) 
      result = temp_val; 
     } 
    } 

    return result; 
} 

...對不起提前任何錯別字/輕微的語法錯誤就想原型快速的解決方案。你不寫完整的代碼...

或者更容易，你可以使用線性試驗的蠻力。使用外循環將是試驗次數，內循環將在試驗中翻轉。每個循環都會翻轉並檢查你是否成功了，回收你的成功並從上面翻轉代碼。成功會縮短內部循環。在內部循環結束時p，將結果存儲在數組中。如果在max_moves之後失敗，則存儲-1。搜索最大值。

更優雅的解決方案是使用多線程庫來啓動一堆線程翻轉，並在找到匹配項時向其他人發送一個線程信號，並且如果匹配低於目前運行的步數在另一個線程中，該線程退出失敗。

我建議MPI，但CUDA可能贏得你布朗尼分，因爲它現在很熱。

希望有所幫助，祝你好運！

Answer 3

基本上，你正在做的N + M-1的硬幣在右側和底部邊框和解決這些問題，那麼就調用遞歸上一切的算法。這基本上是Potatoswatter所說的。下面是一個非常簡單的遞歸算法。

Solver(Grid[N][M]) 
    if Grid[N-1][M-1] == Heads 
     Flip(Grid,N-1,M-1) 

    for each element i from N-2 to 0 inclusive //This is empty if N is 1 
     If Grid[i][M-1] == Heads 
      Flip(Grid,i,M-1) 

    for each element i from M-2 to 0 inclusive //This is empty if M is 1 
     If Grid[N-1][i] == Heads 
      Flip(Grid,N-1,i) 

    if N>1 and M > 1: 
     Solver(Grid.ShallowCopy(N-1, M-1)) 

    return;  

注：這可能是有道理的只是有求解具有寬度和網格的高度參數來實現Grid.ShallowCopy。我只稱它爲Grid.ShallowCopy來表明你不應該傳遞一個網格副本，儘管C++不會在默認情況下默認使用數組。

Answer 4

不是C++。同意@Potatoswatter最佳的解決方案是貪婪的，但我想知道如果一個線性丟番聞系統也工作。這個數學函數做的：

f[ei_] := (
    xdim = Dimensions[ei][[1]]; 
    ydim = Dimensions[ei][[2]]; 

    (* Construct XOR matrixes. These are the base elements representing the 
    possible moves *) 

    For[i = 1, i < xdim + 1, i++, 
    For[j = 1, j < ydim + 1, j++, 
    b[i, j] = Table[If[k <= i && l <= j, -1, 0], {k, 1, xdim}, {l, 1, ydim}] 
    ] 
    ]; 

    (*Construct Expected result matrix*) 
    Table[rv[i, j] = -1, {i, 1, xdim}, {j, 1, ydim}]; 

    (*Construct Initial State matrix*) 
    Table[eiv[i, j] = ei[[i, j]], {i, 1, xdim}, {j, 1, ydim}]; 

    (*Now Solve*) 
    repl = FindInstance[ 
      Flatten[Table[(Sum[a[i, j] b[i, j], {i, 1, xdim}, {j, 1, ydim}][[i]][[j]]) 
        eiv[i, j] == rv[i, j], {i, 1, xdim}, {j, 1, ydim}]], 
      Flatten[Table[a[i, j], {i, 1, xdim}, {j, 1, ydim}]]][[1]]; 

    Table[c[i, j] = a[i, j] /. repl, {i, 1, xdim}, {j, 1, ydim}]; 

    Print["Result ",xdim ydim-Count[Table[c[i, j], {i, 1, xdim}, {j, 1,ydim}], 0, ydim xdim]];) 

當您的實例名爲（-1而不是0）

ei = ({ 
    {1, 1, 1, 1}, 
    {1, 1, 1, 1} 
    }); 
f[ei]; 

ei = ({ 
    {-1, 1}, 
    {-1, 1} 
    }); 
f[ei]; 

ei = {{-1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1}}; 
f[ei]; 

ei = ({ 
    {-1, -1, -1}, 
    {-1, -1, -1}, 
    {-1, -1, 1}, 
    {-1, 1, 1} 
    }); 
f[ei]; 

結果是

Result :1 
Result :2 
Result :20 
Result :6 

或者:)

在我窮人的筆記本電腦上，在90秒內解決20x20的隨機問題。

Answer 5

矩形（x，y）翻轉的一個簡單標準似乎是：恰好當左上方平方（x，y）的2x2平方中的個數爲奇數時。

（在Python代碼）

def flipgame(grid): 
    w, h = len(grid[0]), len(grid) 
    sol = [[0]*w for y in range(h)] 
    for y in range(h-1): 
    for x in range(w-1): 
     sol[y][x] = grid[y][x]^grid[y][x+1]^grid[y+1][x]^grid[y+1][x+1] 
    for y in range(h-1): 
    sol[y][w-1] = grid[y][w-1]^grid[y+1][w-1] 
    for x in range(w-1): 
    sol[h-1][x] = grid[h-1][x]^grid[h-1][x+1] 
    sol[h-1][w-1] = grid[h-1][w-1] 
    return sol 

2D陣列返回的具有1在位置（x，y）的，如果矩形（X，Y）應該被翻轉，所以一的數量中它是回答你原來的問題。

編輯：要知道爲什麼它的工作原理： 如果我們做移動（X，Y），（X，Y-1），（X-1，Y），（X-1，Y-1） ，只有方（x，y）被倒置。這導致上面的代碼。該解決方案必須是最優的，因爲有2 ^（h w）可能的配置和2 ^（h w）可能的方式來轉換電路板（假設每個動作可以完成0或1次）。換句話說，只有一個解決方案，因此上面產生了最優解。