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

Question

Существует прямоугольная сетка монет, в которой головы представлены значением 1, а хвосты представлены значением 0. Вы представляете это с помощью двумерной таблицы целочисленных массивов (от 1 до 10 строк / столбцов включительно).

В каждом ходу вы выбираете любую отдельную ячейку (R, C) в сетке (R-я строка, C-й столбец) и подбрасываете монеты во все ячейки (r, c), где r находится между 0 и R включительно, и с составляет от 0 до С включительно. Подбрасывание монеты означает изменение значения ячейки с нуля на единицу или с единицы на ноль.

Возвращает минимальное количество ходов, необходимое для изменения всех ячеек сетки на хвосты. Это всегда будет возможно.

Примеры:

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

Не с ++. Согласитесь с @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 секунд на ноутбуке моего бедняка.

Answer 3

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

Answer 4

По сути, вы берете монеты 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 ++ не будет делать это с массивами по умолчанию.

Answer 5

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

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

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

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 будет число попыток, внутренний для цикла будетВ каждом цикле вы будете переворачивать и проверять, добились ли вы успеха, перерабатывая свой успех и переворачивать код сверху. Успех замкнул бы внутренний цикл. В конце внутреннего цикла сохраните результат вмассив. Если произошел сбой после max_moves, сохраните значение -1. ​​Найдите максимальное значение.

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

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

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