Эта проблема np-полная?

Question

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

x четный.

Это np-полная проблема? Это похоже на логическое SAT?

Answer 1

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

Can [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

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

Например:

2,6,11,4,7,3

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

Answer 4

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

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

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

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

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