Динамическое программирование: состояния в игре для двоих

Это проблема в соревновании по программированию, где я «нашел», как пройти через состояния за 2 -игровые игры.

Проблема заключается в следующем: между двумя игроками A и B разыгрывается альтернативная игра, где A всегда начинает первым и выбирает несколько букв из заданной матрицы и составляет слова из заданного словаря. Затем эти буквы отбрасываются. Следующий игрок выбирает из оставшихся букв. Проигрывает последний, кто не может сказать ни слова. Каждый играет оптимально.

Я цитирую здесь редакционную статью

    To iterate over all non-empty subsets of the given 
    set when they represented using bitmasks:

    submask = mask
    while submask > 0
        // do the job with the submask
        submask = (submask - 1) AND mask

В одном из решений я видел

    int solve(int state)
    {
        if(dp[state]!=-1)
            return(dp[state]);

        int res=1;
        int nstate=state;
        while(1)
        {
            if(valid[nstate])
                res=solve(state&(~nstate));
            if(res==0)
                break;
            nstate=((nstate-1)&state);
            if(nstate==0)
                break;
        }
        if(res==0)
            dp[state]=1;
        else
            dp[state]=0;
        return(dp[state]);
    }

В этом коде есть еще один оператор AND с ~.

Я не могу понять, что такое «СОСТОЯНИЕ» здесь на самом деле, и как это И ведет нас через все состояния? Пожалуйста, объясните это.


algorithm dynamic-programming
person Ashish Negi    schedule 25.02.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

ОБЪЯСНЕНИЕ СОСТОЯНИЯ

Состояние - это набор оставшихся букв.

Мы заменяем буквы, которые у нас остались, на единицы, а буквы, которые остались, на нули.

В результате получается двоичное число, которое является числом, содержащимся в маске переменной.

Например, предположим, что в начале игры у нас были буквы ABCDEFGH, а в определенный момент остались только буквы B и D.

Число 0x50 будет представлять это текущее состояние:

ABCDEFGH  at start
-B-D----  at current point in game
01010000  replace with 1's for letters we still have
0x50      treat as a binary number

БИТ ТВИДДЛИНГ

Оба решения используют битовый тиддл nstate=((nstate-1)&state).

Если вы начнете с nstate = state, этот код сгенерирует все подмножества состояния.

Что это значит? Что ж, предположим, что у нас есть состояние с текущими буквами B и D. Все возможные непустые подмножества этого состояния: {B, D}, {B}, {D}.

Они будут представлены двоичными числами 01010000,01000000,00010000.

И мы видим, что они действительно создаются путем выполнения следующего кода Python:

state=0b01010000
nstate=state
while nstate:
    print bin(nstate)
    nstate=(nstate-1)&state

Дает вывод:

0b01010000
0b01000000
0b00010000

Почему это работает?

Грубо говоря, код использует nstate = nstate-1 для обратного отсчета всех возможных двоичных чисел, а & state пропускает части, где есть только изменения в битах, которые нам не важны (немедленно устанавливая их на ноль, вместо того, чтобы ждать их обратный отсчет до нуля).

person Peter de Rivaz    schedule 25.02.2013