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

Это классическая игра, в которой два игрока играют в следующую игру:

В ряду лежат n монет разного номинала. В этой игре игроки выбирают монету из крайнего левого или крайнего правого положения (выбирают вслепую из любого крайнего положения с вероятностью 0,5, оба они тупые). Я просто хочу подсчитать ожидаемую сумму игрока, который начинает игру.

Для этого я хочу суммировать все возможные комбинации ценностей, которые может иметь игрок. Я использую рекурсивное решение, которое суммирует все возможные значения результатов, но имеет перекрывающиеся подзадачи. Я хочу сделать его эффективным и хочу запомнить эти перекрывающиеся подзадачи.

Я не могу собрать логику для его выполнения. Пожалуйста, помогите.


memoization dynamic-programming expectations
person Login Test    schedule 13.10.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Пусть F(start, end) обозначает возможные суммы первого игрока, играющего на интервале [start, end]. Аналогично определяют S(start, end). Мы можем хранить возможные суммы с вероятностями сумм со словарем, например {2: 0.25, 5: 0.25, 6: 0.5}.

Чем выполняются рекурсии:

F(start, end) = {row[end]  +sum: p/2,  for sum,p in S(start, end-1)} +
                {row[start]+sum: p/2,  for sum,p in S(start+1, end)}
S(start, end) = {sum: p/2, for sum,p in F(start, end-1)} +
                {sum: p/2, for sum,p in F(start+1, end)}
F(start, end) = {row[start]: 1} if start == end
S(start, end) = {} if start == end

Это можно рассчитать, увеличив длину интервала:

for length = 0 to row_length-1:
  for start = 1 to row_length - length:
    calculate `F(start, start+length)` and `S(start, start+length)`

Словари F(1, row_length) и S(1, row_length) используются для расчета ожидаемой суммы.

person Ante    schedule 13.10.2012
comment
Спасибо за ответ, но у меня ничего не выходит. Фрагмент кода, который вы написали, содержит множество вещей, требующих объяснения. Было бы неплохо, если бы вы отредактировали его с некоторыми пояснениями. - person Login Test; 14.10.2012
comment
С чего начать объяснение? Что такое F() и S()? Зачем эти рекурсии? - person Ante; 14.10.2012