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

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

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

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

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 может принести вам очки, так как сейчас жарко.

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

Не С++. Согласитесь с @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

Или :)

Решает случайную задачу 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) нечетно.

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