动态规划的基本概念 动态规划的条件 ●阶段 ●最优化原理 ●状态 个最优化策略具有这样的性质,不论过 ●决策 去状态和决策如何,对前面的决策所形成的 状态而言,余下的诸决策必须构成最优策 略 际上就是把原问题转换成规模更小的子 问题时,原问题最优当且仅当子问题最优 最优子结构 动态规划的条件 动态规划的条件 从13→5>8~9是1到9的最短 无后效性 最优化原理路,则135÷8是1到8的最短 路,1~3→5是1到5的最短略 最优子结构 当前状态为7的时候,到7的最短 过去的步骤只能通过当前状态影响 与以前所经过的结点无关,如到 未来的发展,当前的状态是历史的 无后效性 经过的点为1,2,5,7成1,3,5 7或1,3,6,7都对以后的求解无 总结。 动态规划法的思想 多叉路口交通灯管理问题 自底向上构造 五叉路口 ●在原问题的小子集中计算 ·右行规则 道路C、E是箭头所示的单行道 每一步列出局部最优解 订以同时行驶而不发生碰撞的路线用一种颜 用一张表保留这些局部最优解 交通灯 用空间换时间 避免重复计算 路?种色的变通灯,怎样分配给这些行驶 子集越来越大 是经最杷的全集上计算,所得出的就 1111 动态规划的基本概念 z阶段 z状态 z决策 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3 动态规划的条件 z最优化原理 z 最优子结构 一个最优化策略具有这样的性质，不论过 去状态和决策如何，对前面的决策所形成的 状态而言，余下的诸决策必须构成最优策 略。 实际上就是把原问题转换成规模更小的子 问题时，原问题最优当且仅当子问题最优。 动态规划的条件 z无后效性 z 过去的步骤只能通过当前状态影响 未来的发展，当前的状态是历史的 总结。 动态规划的条件 1 2 3 4 5 6 7 8 9 z 最优化原理 z 最优子结构 z 无后效性 从1->3->5->8->9是1到9的最短 路，则1->3->5->8是1到8的最短 路，1->3->5是1到5的最短路…… 当前状态为7的时候，到7的最短 路与以前所经过的结点无关，如到7 经过的点为1，2，5，7或1，3，5， 7或1，3，6，7都对以后的求解无 关。 动态规划法的思想 自底向上构造 z 在原问题的小子集中计算 z 每一步列出局部最优解 z 用一张表保留这些局部最优解 z 用空间换时间 z 避免重复计算 z 子集越来越大…… z 最终在问题的全集上计算，所得出的就 是整体最优解 多叉路口交通灯管理问题 z 五叉路口 z 右行规则 z 道路C、E是箭头所示的单行道 z 把可以同时行驶而不发生碰撞的路线用一种颜 色的交通灯指示 z 用多少种颜色的交通灯，怎样分配给这些行驶 路线？ z 颜色越少则管理效率越高 z 不考虑过渡灯（例如黄灯） B C A D E