Блог

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

Робот и RobotB, которые для начала выбирают перестановку из N чисел. Робот выбирает первым, а они выбирают поочередно. Каждый ход роботы могут выбирать только одно оставшееся число из перестановки. Когда оставшиеся числа образуют возрастающую последовательность, игра заканчивается. Робот, который выбрал последний ход (после которого последовательность становится возрастающей), выигрывает игру.

Предполагая, что оба играют оптимально, кто выигрывает?

Пример 1:

  The original sequence is 1 7 3. 
 RobotA wins by picking 7, after which the sequence is increasing 1 3.
  

Пример 2:

  The original sequence is 8 5 3 1 2.
 RobotB wins by selecting the 2, preventing any increasing sequence.
  

Существует ли какой-либо известный алгоритм для решения этой проблемы? Пожалуйста, дайте мне какие-либо советы или идеи о том, где посмотреть, был бы очень благодарен!

Задана последовательность w различных чисел, пусть N(w) — длина w и пусть L(w) — длина самой длинной возрастающей подпоследовательности в w . Например, если

 w = 3 5 8 1 4
  

затем N(w) = 5 и L(w) = 3 .

Игра заканчивается, когда L(w) = N(w) или, что эквивалентно, N(w) - L(w) = 0 .

Прорабатываем игру в обратном порядке, если на очереди RobotX N(w) - L(w) = 1 , то оптимальной игрой является удаление уникальной буквы не в самой длинной возрастающей подпоследовательности, тем самым выигрывая игру.

Например, если w = 1 7 3 , то N(w) = 3 и L(w) = 2 с самой длинной возрастающей подпоследовательностью, равной 1 3 . Удаление 7 приводит к возрастающей последовательности, гарантируя, что игрок, который удалил 7 , выигрывает.

Возвращаясь к предыдущему примеру, w = 3 5 8 1 4 если либо 1 или 4 удалено, то в результате перестановки u мы имеем N(u) - L(u) = 1 , таким образом, игрок, который удалил 1 или 4 , безусловно, проиграет компетентному противнику. Однако любая другая игра приводит к победе, поскольку она вынуждает следующего игрока перейти на проигрышную позицию. Здесь оптимальной игрой является удаление любого из 3 , 5 или 8 , после чего N(u) - L(u) = 2 , но после следующего хода N(v) - L(v) = 1 .

Дальнейший анализ в этом направлении должен привести к оптимальной стратегии для любого игрока.

Ближайшая математическая игра, которую я знаю, — это игра с монотонными последовательностями. В монотонной игре с последовательностями два игрока поочередно выбирают элементы последовательности из некоторого фиксированного упорядоченного набора (например, 1,2,...,N ). Игра заканчивается, когда результирующая последовательность содержит либо возрастающую подпоследовательность длины A , либо убывающую подпоследовательность длины D . Эта игра берет свое начало с теоремы Эрдоса и Секереша, а хорошее изложение можно найти в ИГРАХ С МОНОТОННЫМИ ПОСЛЕДОВАТЕЛЬНОСТЯМИ, и эта слайд-презентация Брюса Сагана также является хорошим справочником.

Если вы хотите узнать больше о теории игр в целом или играх такого рода в частности, то я настоятельно рекомендую Winning Ways для ваших математических игр Берлекэмпа, Конвея и Гая. Я полагаю, что в томе 3 рассматриваются игры такого рода.

Похоже на минимаксную проблему.

Я думаю, что есть более быстрое решение для этой задачи. Я подумаю. Но я могу дать вам идею решения с помощью O (N! * N^2) сложность.

Во-первых, обратите внимание, что выбор числа из N-перестановки эквивалентен следующему:

1. Выберите число из N-перестановки. Пусть это было число X.

2. Переназначайте числа, используя правило:

1 = 1

2 = 2

…

X-1 = X-1

X = Ничего, оно ушло.

X 1 = X

…

N = N — 1

И вы получаете перестановку из N-1 чисел.

Пример:

1 5 6 4 2 3

Выбери 2

1 5 6 4 3

Переназначить

1 4 5 3 2

Давайте используем это как ход, вместо того, чтобы просто выбирать. Также легко видеть, что игры эквивалентны, игрок А выигрывает в этой игре при некоторой перестановке тогда и только тогда, когда он выигрывает в оригинале.

Давайте дадим код для всех перестановок из N чисел, N-1 чисел, … 2 чисел.

Определить F(x) -> {0; 1} (где x — код перестановки) — это функция, которая равна 1 при текущем

игрок выигрывает, и 0, если текущий игрок терпит неудачу. Легко видеть, что F(1 2 .. K-1 K) = 0.

F (x) = 1, если есть хотя бы один ход, который преобразует x в y, и F (y) = 0.

F (x) = 0, если для любого хода, который преобразует x в y, F (y) = 1.

Таким образом, вы можете использовать рекурсию с запоминанием для вычисления:

 Boolean F(X)
{
    Let K be length of permutation with code X.
    if you already compute F for argument X return previously calculated resu<
    if X == 1 2 .. K return 0;
    Boolean result = 0;
    for i = 1 to K do
    {
         Y code of permutation get from X by picking number on position i.
         if (F(y) == 0)
         {
             result = 1;   
             break;
         }
    }
    Store result as F(X);
    return resu<
}
  

Для каждого аргумента мы будем вычислять эту функцию только один раз. Существует 1! перестановки длиной 1, 2! перестановки длиной 2 .. N! перестановки длиной N. Для длины перестановки K нам нужно выполнить операцию O (K) для вычисления. Таким образом, сложность будет О(1*1! 2*2! .. N*N!) =<= O(N! * N ^2) = O(N! * N^2)

Вот код Python для алгоритма Wind от Wisdom. Он выводит выигрыши для RobotA.

 import itertools

def moves(p):
    if tuple(sorted(p)) == p:
        return
    for i in p:
        yield tuple(j - (j > i) for j in p if j != i)

winning = set()

for n in range(6):
    for p in itertools.permutations(range(n)):
        if not winning.issuperset(moves(p)):
            winning.add(p)

for p in sorted(winning, key=lambda q: (len(q), q)):
    print(p)