动态规划

动态规划的一般模型:状态集合、有限转移集合、子问题集合、状态充分性与值代数;循环引用时转为 Bellman 方程。

标签 动态规划 / DP / 状态转移 / 无后效性

模型

设 𝑆 是状态集合,𝑉 是值集合,⊕:𝑉×𝑉→𝑉 是交换、结合的二元运算。对每个 𝑠∈𝑆,给定非空有限转移集合 𝐸(𝑠);每条转移 𝑒∈𝐸(𝑠) 给定有限子问题集合 𝐷𝑒(𝑠)⊆𝑆 与合并函数

Φ𝑒:𝑉𝐷𝑒(𝑠)→𝑉.

这里 𝑉𝐷𝑒(𝑠) 表示所有 𝐷𝑒(𝑠)→𝑉 的 索引族。

状态值 𝑓:𝑆→𝑉 满足

𝑓(𝑠)=⨁𝑒∈𝐸(𝑠)Φ𝑒((𝑓(𝑡))𝑡∈𝐷𝑒(𝑠)).

当 𝐷𝑒(𝑠) 为单元集、⊕=min 且 Φ𝑒(𝑣)=𝑤𝑒+𝑣(𝑤𝑒 为转移代价)时,值方程退化为 贪心决策模型 的值方程。

若某条转移的 𝐷𝑒(𝑠)=∅,Φ𝑒 是常值函数,其值由初值给出。

若同一子问题在合并中出现多次,把 𝐷𝑒(𝑠) 看成多重集;若不同子问题的角色不同,用标签区分。

若存在计算顺序,使每个 𝑓(𝑠) 计算时所有 𝑓(𝑡)(𝑡∈𝐷𝑒(𝑠))都已求出,则依次计算所有状态。𝑆 有限且不存在循环引用时,这样的顺序存在。

状态

状态给出部分解集合的一个等价类划分,是部分解的一个充分统计量:若两个部分解属于同一状态,则对任意未来扩展,它们的代价、计数贡献或可行性相同;否则把差异并入状态,细化划分。

值代数

若 𝑉 具有 半环结构 (𝑉,⊕,⊗,0,1),每条转移 𝑒 带有权重 𝑤𝑒∈𝑉,其贡献为 𝑤𝑒 与所有 𝑓(𝑡)(𝑡∈𝐷𝑒(𝑠))的 ⊗-乘积;空乘积取 1。此时 Φ𝑒 取该乘积,转移间的合并取 ⊕。

扩展

若子问题关系出现循环,或引用链可无限延伸,则递归定义不能直接展开;把整组等式作为 Bellman 方程,讨论不动点、解的存在性与唯一性,以及值迭代等求解方式,见 Bellman 方程。

源码位置