第六章 动态规划1.ppt

第六章动态规划 信工计算机系2008 6 1资源分配问题 假设资源总数为m份 工程个数为n 给每项工程投入的资源不同 所获得的利润也不同 要求把总数为m的资源 分配给n个工程 以获得最大利润分配方案 数学描述 假设用函数Gi k 1 i n 0 k m 表示将k份资源分配给工程i获得的利润 设工程i分配xi份资源 资源分配问题数学描述为 设其最优解为X x1 x2 xn 资源分配问题求解 最优值 opt max fi x 1 i n 0 x m 记k i fi x opt p x fi x opt k p含义 分配p份资源给前k个工程时利润最大 即 xk 1 0 xk 2 0 xn 0 fi x 的计算 解资源分配问题实例 有8个份额的资源 分配给3个工程 其利润函数如下表 求资源的最优分配方案 计算过程 解 初始 f1 x G1 x d1 x xopt max f1 x 0 x 8 53k 1p 8 计算过程 其它及计算f3 x 同理 结果如下表 计算过程 opt 140k 3p 8 计算过程 计算最优解 最大利润opt 140第3个工程分配资源x3 d3 p 4份第2个工程分配资源x2 d2 p x3 4份第1个工程分配资源x1 d1 p x3 x2 0份最优解X 0 4 4 时间复杂性 初始化 O m 计算f2 x f3 x fn x O nm2 计算opt k p O nm 回溯 O n 时间复杂性 O nm2 算法分析 关于资源分配求解过程 上述解资源分配所采用的算法 动态规划 6 2动态规划的基本思想 动态规划也称多阶段决策 由状态和决策组成 从初始状态开始 根据各阶段决策使状态转移 到达最终状态 动态规划的一般决策过程示意图 Sn是最终状态集 S1 Sn中至少有一个状态是最优状态 最优值 假设为Sk kn 设状态Si si 1 si 2 si r 从Sk kn向前回溯可得到最优解或最优决策序列 P1 k1 P2 k2 Pk kn 即 动态规划最优解的确定 S0 Sk kn Pk kn S1 k1 P1 k1 各阶段赖以决策的策略或目标 称为动态规划函数 资源分配问题动态规划函数 fi x 动态规划函数可以递归定义 或用递推公式表达 动态规划函数 动态规划算法的设计步骤 找出最优解的性质 并刻画其结构特征 fi x 递归的定义最优值 fi x max Gi k fi 1 x k 以自底向上的方式计算最优值 表格根据计算最优值时得到的信息 构造最优解 回溯 动态规划算法的基本要素 可用动态规划求解的问题应具有以下两个基本要素 最优子结构问题的最优解包含了其子问题的最优解 动态规划算法 利用问题的最优子结构性质 自底向上的方式递归地从子问题的最优解构造出整个问题的最优解 动态规划算法的基本要素 重叠子问题在用动态规划递归地自底向上求解问题时 每次产生的子问题不是新问题 有些被反复计算多次 动态规划算法利用这些子问题的重叠性质 对每个子问题只计算一次 将结果保存在表格中 后续计算只需查找表格 从而节省时间 资源分配问题重叠子问题示意图 注 只画出fi x x 4的情况 其它同理 6 3多段图最短路径问题 多段图的最短路径问题 是求从源点s到收点t的最小花费的通路 假设用邻接矩阵C cij 存储图G 多段图最短路径问题的动态规划函数 最优值 cost 0 按子集顺序 对多段图各顶点编号 假设源点为0 收点为n 1 动态规划函数的递归表示 初始化 cost i INT MAX path i 10 i ncost n 1 0 i n 1若i 0 转 4 否则转 3 i 根据式 6 1 和 6 2 计算cost i path i 转 2 i 0 route i 0 若route i n 1 终止 否则 转 6 i route i path route i 1 转 5 动态规划解多段图最短路径算法描述 其中 数组route存放从0到n 1的最短路径 动态规划解多段图最短路径问题实例 计算过程 解 cost 6 0cost 5 4 cost 6 4path 5 6cost 4 5 cost 6 5path 4 6cost 3 min 8 cost 4 9 cost 6 9 cost 5 9path 3 6cost 2 min 5 cost 3 7 cost 5 11path 2 5cost 1 min 6 cost 3 6 cost 4 11 计算过程 path 1 4cost 0 min 4 cost 1 5 cost 2 8 cost 3 15最优值path 0 1回溯求最优解 route 0 0route 1 1route 2 4route 3 6最优解 0 1 4 6 时间复杂性 邻接矩阵 初始化 O n 计算cost 循环n 1次 每次访问邻接表一行 O n2 计算route O k 故为O n2 考虑邻接表存储的时间复杂性 动态规划解多段图最短路径算法分析 6 4货郎担问题 假设用邻接矩阵C cij 存储网 分别求从城市i出发的哈密尔顿回路 最后求n条回路的最小值 货郎担问题的动态规划函数 最优值 d i V i 货郎担问题动态规划函数的递归表示 4个城市1 2 3 4 邻接矩阵如下表 动态规划解货郎担问题实例 解 以从城市1出发为例 求哈密尔顿回路 其它城市同理 第一阶段d 1 2 3 4 min c12 d 2 3 4 c13 d 3 2 4 c14 d 4 2 3 第二阶段d 2 3 4 min c23 d 3 4 c24 d 4 3 d 3 2 4 min c32 d 2 4 c34 d 4 2 计算过程 d 4 2 3 min c42 d 2 3 c43 d 3 2 第3阶段d 3 4 c34 d 4 2 3 5 3 4 1 d 4 3 c43 d 3 5 6 11 4 3 1 d 2 4 c24 d 4 3 3 6 2 4 1 d 4 2 c42 d 2 7 5 12 4 2 1 d 2 3 c23 d 3 2 6 8 2 3 1 d 3 2 c32 d 2 4 5 9 3 2 1 计算过程 回溯第2阶段d 2 3 4 min 2 5 3 11 7 2 3 4 1 d 3 2 4 min 4 6 2 12 10 3 2 4 1 d 4 2 3 min 7 8 5 9 14 4 3 2 1 回溯第1阶段d 1 2 3 4 min 3 7 6 10 7 14 10 1 2 3 4 1 计算过程 动态规划解货郎担问题求解过程示意图 动态规划解货郎担问题算法分析 时间复杂性 O n22n 穷举法 O n 贪心法 O n3 6 50 1背包问题 0 1背包问题数学模型 即求X x1 x2 xn 满足上述优化方程 贪心法解0 1背包问题 例 有5个物体 其重量分别为6 2 6 5 4 价值分别为6 3 5 4 6 背包的载重量为10 求装入背包的物体及其总价值 解 价值 重量降序排 2 5 1 3 4x2 1剩余重量8x5 1剩余重量4x1 0 x3 0 x4 0总价值 9 最优解 1 0 0 0 1 最优价值 12 0 1背包问题的动态规划函数 最优值 opt fn M 动态规划函数的递归表示 回溯求最优解 1 若fn M fn 1 M 则xn 0 否则xn 1 2 令M M pnxn n 3 若n 0 终止 否则 转 1 动态规划解0 1背包问题实例 有5个物体 其重量分别为6 2 6 5 4 价值分别为6 3 5 4 6 背包的载重量为10 求装入背包的物体及其总价值 计算过程 解 初始 计算过程 第一阶段 f2 0 0f2 1 f1 1 0f2 2 max 3 f1 0 f1 2 3f2 3 max 3 f1 1 f1 3 3f2 4 max 3 f1 2 f1 4 3其它同理 结果见下表 计算过程 计算过程 回溯求最优解 f5 10 f4 10 x5 1