动态规划
动态规划的一般模型:状态集合、有限转移集合、子问题集合、状态充分性与值代数;循环引用时转为 Bellman 方程。标签 动态规划 / DP / 状态转移 / 无后效性
模型
设 是状态集合, 是值集合, 是交换、结合的二元运算。对每个 ,给定非空有限转移集合 ;每条转移 给定有限子问题集合 与合并函数
这里 表示所有 的 索引族。
状态值 满足
当 为单元集、 且 ( 为转移代价)时,值方程退化为 贪心决策模型 的值方程。
若某条转移的 , 是常值函数,其值由初值给出。
若同一子问题在合并中出现多次,把 看成多重集;若不同子问题的角色不同,用标签区分。
若存在计算顺序,使每个 计算时所有 ()都已求出,则依次计算所有状态。 有限且不存在循环引用时,这样的顺序存在。
状态
状态给出部分解集合的一个等价类划分,是部分解的一个充分统计量:若两个部分解属于同一状态,则对任意未来扩展,它们的代价、计数贡献或可行性相同;否则把差异并入状态,细化划分。
值代数
若 具有 半环结构 ,每条转移 带有权重 ,其贡献为 与所有 ()的 -乘积;空乘积取 。此时 取该乘积,转移间的合并取 。
扩展
若子问题关系出现循环,或引用链可无限延伸,则递归定义不能直接展开;把整组等式作为 Bellman 方程,讨论不动点、解的存在性与唯一性,以及值迭代等求解方式,见 Bellman 方程。