Эта проблема с NP-полным?

Question

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

Икс даже.

Это проблема с полным NP? Это похоже на Boolean Sat?

Answer 1

Это очень простая проблема, и она не завершена. Вот краткое описание алгоритма, он основан на динамическом программировании.

Может [i] - массив, который хранит количество безделушек.
F [i, j] - массив, определяющий, что лучше всего двигаться, если только банки от I до J являются доступными. 0 означает взять с левой стороны, 1 означает взять с правой стороны.
G [i, j] - массив, где хранится «добро» движения.

for (i=1 to n) F[i,i] = 0
for (i=1 to n) G[i,i] = Can[i]

for (i=1 to n-1)
   for (j=1 to n-i)
       tmp1 = Can[j] - G[j+1,j+i]
       tmp2 = Can[j+i] - G[j,j+i-1]
       if (tmp1>tmp2)
       {
             F[j,j+i] = 0;
             G[j,j+i] = tmp1;
       }
       else
       {
             F[j,j+1] = 1;
             G[j,j+i] = tmp2;
       }

Извините за отсутствие комментариев, но если вы прочитаете некоторые статьи о динамическом программировании, вы получите его без каких -либо проблем.

Answer 2

Нет, его легко разрешить динамическим программированием в O(x^2). Анкет Посмотрите на проблему 10 здесь.

Answer 3

Эта проблема, кажется, идеально подходит для альфа-бета-срыва, так как легко получить нижнюю границу для ваших точек. Предположим, что игрок сталкивается с равномерным количеством ящиков. Тогда он может играть в каком -то смысле, чтобы получить все корзины ровно или все на нечетных позициях:

Скажем, у нас есть 1 0 1 0 1 0, тогда он может взять 1 слева, и что бы ни делал противник, он просто продолжает поднимать 1.

Таким образом, легко вычислять нижнюю границу - максимум суммы всех бункеров на равномерных положениях и суммы всех бункеров на нечетных положениях.

Для «нечетного» игрока вы можете просто взять сумму (длина+1)/2 наименьших значений, что не так хорошо, как граница для «ровного» игрока, но, как и легко рассчитать.

Я думаю, что с этими границами дерево поиска будет скудно для практических применений (я думаю, вы всегда можете найти «патологические» противодействие для этого типа проблемы), поэтому решение должно быть довольно быстрым.

Answer 4

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

Например:

2,6,11,4,7,3

Здесь нечетные позиции лучше (20 против 13), поэтому игрок 1 должен выбрать 2. Тогда игрок 2 должен выбрать 6 или 3, которые находятся на ровных положениях. Если 3 выбрано, игрок 1 должен выбрать 7 и так далее. На самом деле, игрок 1 всегда должен выбирать позицию рядом с той, которая выбран его противником, и гарантирует галстук или победу.