algorithm - 汉诺塔 - 贝尔曼方程解

Question

我必须使用 Bellman 动态规划方程(如果问题当然是可以解决的)。

现在，我明白了等式背后的逻辑:

其中 V^T 是时间 T 的目标函数，a^0 是时间 0 的 Action ，x^0 是起始配置，H_0 是累积增益 f(x^0, a^0)=x^ 1.

状态空间的基数是 $k^d$，我知道状态的良好表示是基数为 k 的数字:d 位数字，可以从 0 到 k-1。每个数字代表一个环，数字可以从0到k-1，即k个环的标签。

我想尽量减少从初始配置(第一个 pod 上的 10 个响铃)到最后一个配置(最后一个 pod 上的 10 个响铃)的移动次数。

我不明白的是:我该如何编写我的目标函数？

Answer 1

您需要做的第一件事是选择一个奖励函数 H_t(s,a) 来定义您的目标。一旦选择了这个函数，(最佳)值函数就被定义了，您所要做的就是计算它。

Bellman 方程的动态规划思想是您应该自下而上地计算 V_t(s):从 t=T 开始，然后是 t=T-1 等等，直到 t=0。

初始情况简单地给出:

V_T(s) = 0, ∀s

你可以从 V_T 计算 V_{T-1}(x)∀x:

V_{T-1}(x) = max_a [ H_{T-1}(x,a) ]

然后你可以从 V_{T-1} 计算 V_{T-2}(x)∀s:

V_{T-2}(x) = max_a [ H_{T-2}(x,a) + V_{T-1}(f(x,a)) ]

然后你继续从 V_{t} 计算 V_{t-1}(x)∀s:

V_{t-1}(x) = max_a [ H_{t-1}(x,a) + V_{t}(f(x,a)) ]

直到你达到 V_0。

给出了算法:

forall x:
  V[T](x) ← 0
for t from T-1 to 0:
  forall x:
    V[t](x) ← max_a { H[t](x,a) + V[t-1](f(x,a)) }