Игра с подбрасыванием монет: проблема оптимизации

Я думаю, что жадного алгоритма достаточно, с одним шагом на монету.

Каждый ход переворачивает прямоугольное подмножество доски. Некоторые монеты входят в большее количество подмножеств, чем другие: монета в верхнем левом углу (0,0) входит в каждое подмножество, а монета в правом нижнем углу входит только в одно подмножество, а именно в то, которое включает все монеты.

Таким образом, выбор первого хода очевиден: подбрасывайте каждую монету, если нужно подбросить нижний правый угол. Исключите этот возможный ход.

Теперь непосредственные соседи нижней правой монеты, слева и сверху, потенциально могут быть подброшены только одним оставшимся ходом. Итак, если это движение должно быть выполнено, сделайте это. Порядок оценки соседей не имеет значения, поскольку на самом деле они не являются альтернативами друг другу. Однако растрового изображения должно быть достаточно.

Повторяйте, пока не закончите.

Вот программа на С++:

#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;
}

Не С++. Согласитесь с @Potatoswatter в том, что оптимальное решение является жадным, но мне было интересно, работает ли линейная диофантова система. Эта функция Mathematica делает это:

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

Or :)

Решает случайную задачу 20x20 за 90 секунд на ноутбуке моего бедняги.

По сути, вы берете монеты 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, просто предоставив Solver аргументы для ширины и высоты сетки. Я назвал его Grid.ShallowCopy только для того, чтобы указать, что вы не должны передавать копию сетки, хотя C++ в любом случае не будет делать этого с массивами по умолчанию.

Простым критерием для переворачивания прямоугольника (x, y) является: ровно когда количество единиц в квадрате 2x2 с верхним левым квадратом (x, y) нечетно.

(код на Питоне)

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^(hw) возможных конфигураций доски и 2^(hw) возможных способов преобразования доски (при условии, что каждый ход можно сделать 0 или 1). раз). Другими словами, существует только одно решение, поэтому приведенное выше решение дает оптимальное решение.

Вы можете использовать рекурсивные испытания.

Вам понадобится как минимум количество ходов и передача копии вектора. Вы также хотели бы установить максимальное отсечение перемещения, чтобы установить предел ширины ветвей, выходящих из каждого узла дерева поиска. Обратите внимание, что это подход «грубой силы».

Ваша общая структура алгоритма будет следующей:

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;
}

... заранее извините за любые опечатки/незначительные синтаксические ошибки. Хотел прототипировать для вас быстрое решение, а не писать полный код...

Или, что еще проще, вы можете просто использовать грубую силу линейных испытаний. Использование внешнего цикла for будет числом испытаний, внутренним циклом for будет переворот в испытании. В каждом цикле вы переворачивали и проверяли, добились ли вы успеха, повторяя свой успех и переворачивая код сверху. Успех приведет к короткому замыканию внутренней петли. В конце внутреннего цикла сохраните результат в массиве. Если сбой после max_moves, сохраните -1. Найдите максимальное значение.

Более элегантным решением было бы использовать библиотеку многопоточности, чтобы запустить несколько потоков, переключающихся между ними, и чтобы один поток сигнализировал другим, когда он находит совпадение, и если совпадение меньше, чем количество шагов, выполненных до сих пор в другом потоке, этот поток завершается с ошибкой.

Я предлагаю MPI, но CUDA может принести вам очки, так как сейчас жарко.

Надеюсь, это поможет, удачи!