硬币翻转游戏：优化问题

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次）。换句话说，只有一个解决方案，因此上面产生了最优解。