Эта проблема np-complete?
Скажите, что существует строка x мусорных ведер, заполненных пустяками (случайная сумма) в простом виде (Вы видите, сколько пустяков там находится в каждом мусорном ведре). Теперь существует два игрока, которые могут, когда это - их выбор поворота мусорное ведро от любого конца. Они не могут воздержаться от поворота. Придумайте стратегию плеера получить максимальную сумму пустяков.
x ровен.
Действительно ли это - np-complete проблема? Действительно ли это подобно булеву SAT?
4 ответа
Это очень простая проблема, и она не является NP полной. Вот краткое описание алгоритма, он основан на динамическом программировании.
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;
}
Извините за отсутствие комментариев, но если вы прочитаете несколько статей о динамическом программировании, то поймете это без проблем.
Нет, она легко решается динамическим программированием за O(x^2). Посмотрите на задачу 10 здесь.
Эта задача кажется идеальной для альфа-бета-отсечения, так как легко получить нижнюю границу для ваших баллов. Предположим, что перед игроком четное количество бункеров. Затем он может играть так, чтобы все ячейки были на четных или все на нечетных позициях:
Допустим, у нас есть 1 0 1 0 1 0, затем он может взять 1 слева, и что бы ни делал противник, он просто продолжает набирать единицы.
Таким образом, легко вычислить нижнюю границу - это максимум суммы всех интервалов на четных позициях и суммы всех интервалов на нечетных позициях.
Для «нечетного» игрока вы можете просто взять сумму (длина + 1) / 2 наименьших значений, что не так хорошо, как оценка для «четного» игрока, но также легко вычисляется.
Я думаю, что с этими границами дерево поиска будет разреженным для практических приложений (хотя я думаю, вы всегда можете найти «патологические» контрпримеры для этого типа проблем), поэтому решение должно быть довольно быстрым.
Очевидно, что у первого игрока есть стратегия ничьей/выигрыша. Все, что ему нужно сделать, это проверить, имеют ли бины нечетной позиции или бины четной позиции больший итог, а затем он может легко играть так, чтобы заставить противника забрать бины "проигрывающего" равенства.
Например:
2,6,11,4,7,3
Здесь нечетные позиции лучше (20 против 13), поэтому игрок 1 должен выбрать 2. Затем игрок 2 должен выбрать либо 6, либо 3, которые находятся на четных позициях. Если выбрана 3, игрок 1 должен выбрать 7, и так далее. На самом деле, игрок 1 всегда должен выбирать позицию, следующую за той, которую выбрал его оппонент, и это гарантирует ничью или победу.