第四章 动态规划2整理ppt.pptVIP

第四章 动态规划 例 [多段图问题]多段图G=(V,E)是一个有向图，且具有特性: 结点：结点集V被分成k≥2个不相交的集合Vi， 1≤i≤k，其中V1和Vk分别只有一个结点：s(源结 点)和t(汇点)。 段： 每一集合Vi定义图中的一段——共k段。 边： 所有的边(u,v)均具有如下性质： 若u,v∈E， 则 若u∈Vi，则u∈Vi＋1,即该边将是从某段i指向i+1段，1≤i≤k－1。 成本：每条边(u,v)均附有成本c(u,v)。 s到t的路径：是一条从第1段的源点s出发，依次经过第 2段的某结点v2,i，经第3段的某结点v3,j、…、最后在第k段的汇点t结束的路径。该路径的成本是这条路径上边的成本和。 多段图问题：求由s到t的最小成本路径。 多段图问题的多阶段决策过程：生成从s到t的最小成本路径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1(1≤i≤k-2)中的哪个结点在从s到t的最短路径上。 ★ 最优性原理对多段图问题成立 假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径。 ● 初始状态：s ● 初始决策：(s,v2)， v2∈V2 ● 初始决策产生的状态：v2 则，其余的决策：v3,...,vk-1相对于v2将构成一个最优决策序列——最优性原理成立。 反证：若不然，设v2,q3,…,qk-1,t是一条由v2到t的更短的路径，则s, v2,q3,…,qk-1,t将是比s,v2,v3,…,vk-1,t更短的从s到t的路径。与假设矛盾。 故，最优性原理成立 问题描述的总结： ● 在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结果。 ● 第i次决策决定Vi+1中的哪个结点在这条路径上，这里1≤i≤k-2； ● 最优性原理对多段图问题成立 2. 向前处理策略求解 设 P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。 1) 向前递推式 2) 递推过程 ★ 第k-1段 c(j,t) j,t∈E COST(k-1,j) = ∞ ★各递推结果 第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5 第3段 COST(3,6) = min{6+COST(4,9),5+COST(4,10)} = 7 COST(3,7) = min{4+COST(4,9),3+COST(4,10)} = 5 COST(3,8) = min{5+COST(4,10),6+COST(4,11)} = 7 第2段 COST(2,2) = min{4+COST(3,6) , 2+COST(3,7), 1+COST(3,8)} = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15 第1段 COST(1,1) = min{9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5)} = 16 S到t的最小成本路径的成本 ＝ 16 ★ 最小成本路径的求取 记 D(i,j)＝每一COST(i,j)的决策 即，使c(j,l)+COST(i+1,l)取得最小值的l值。 例：D(3,6)