Запоминание динамического программирования с конечным горизонтом - PullRequest
Новая
       58

Запоминание динамического программирования с конечным горизонтом

0 голосов
/ 18 января 2019

Я постараюсь задать мои вопросы здесь:

Итак, я пытаюсь запрограммировать простую задачу динамического программирования с конечным горизонтом.

Я пытаюсь использовать запоминание для ускорения вычислений. 

using Optim

V2dict = Dict()

function V2(t, K)
    if t >= T
        return 0.0
    else
        if haskey(V2dict, (t, K))
            return V2dict[t, K]
        else
            opt = optimize(K′ -> -(log(K - K′) + β * V2(t+1, K′)), eps(), K, iterations = 100_000)
            V2dict[t, K] = Optim.minimum(opt)
            return V2dict[t, K]
        end
    end
end

T = 6
β = 0.95

@time V2(1, 100)
#-6.333197046721626
# 32.262246 seconds (1.36 G allocations: 21.515 GiB, 14.51% gc time)

У меня два вопроса:

Так должно осуществляться запоминание?

Почему V2dict сохраняет много ключей для каждого t? Я только пытаюсь сохранить оптимальные значения для V2. 

V2dict
Dict{Any,Any} with 1799 entries:
  (4, 3.32187e-5)  => -24.3578
  (5, 5.22198e-15) => 32.9762
  (5, 4.50844e-16) => 36.4949
  (4, 8.69678e-5)  => -25.3202
  (5, 2.6052e-12)  => 26.6737
  (5, 2.19599e-9)  => 19.9366
  (5, 7.22726e-16) => 35.7118
  (5, 3.94054e-8)  => 17.0494
  (5, 0.118624)    => 2.1318
  (4, 1.3312e-14)  => -2.68559
  (4, 0.000596086) => -27.245
  (3, 4.50844e-16) => 35.5843
  (5, 6.72888e-16) => 35.8166
  (5, 0.0453104)   => 3.09422
  ⋮                => ⋮

1 Ответ

0 голосов
/ 18 января 2019

Это похоже на разумную реализацию памятки для функции V2.

Выход V2 зависит не только от первого параметра t, но и от второго параметра K. Таким образом, чтобы запоминать вывод V2, ключ словаря должен включать и t, и K, что он и делает. Но это означает, что вы получите несколько ключей с одинаковым значением t, потому что t - это не весь ключ; ключ (t, K).

Возможно, вы пытаетесь не запоминать функцию V2, а просто создаете словарь из значений t с самым низким значением V2, найденным для этого t (для всех значений K). Если это так, тогда вы можете просто использовать словарный ключ t и заменять существующее значение всякий раз, когда обнаруживаете «лучшее» значение.

...