《[理学]第10章_程序设计基础》由会员分享，可在线阅读，更多相关《[理学]第10章_程序设计基础（41页珍藏版）》请在金锄头文库上搜索。
1、第十章 动 态 规 划内 容 要 点 动态规划思想 动态规划基本概念 动态规划的解题思路动态规划（dynamic programming）思想：动态规划是运筹学的一个重要分支，是解决多阶段决策 过程最优化的一种方法。动态规划的依据是“最优化原理”。最优化原理(Principle of optimality) ：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。ABCIJ若路线I和J是A到C的最优路径 ，则根据最优化原理，路线J必 是从B到C
2、的最优路线。直线表示边，波状线表示两顶点间的最短路径（路径中其他节点未显示）；粗线表示从起点到终点的最短路径。不难看出，start 到 goal 的最短路径由 start 的相邻节点到 goal 的最短路径及 start 到其相邻节点的成本决定。 图：使用最优子结构寻找最短路径【任务10.1】最短路径问题（由P至A）DAGCKBNP POMJFHELI312345214323142212223344阶段1阶段2阶段3阶段4阶段5图10-1 最短路径问题所用的交通图 思路： (1) 先看第5阶段，到达A点有两条路：B A，需要 2kmC A，需要 3km令：从 P A 的最短路径为P(A)；从
3、P B 的最短路径为P(B)；从 P C 的最短路径为P(C)；P(A) = minP(B)+2, P(C)+3；P(B) = minP(D)+1, P(E)+2；P(C) = minP(E)+5, P(F)+4； P(N) = 2; P(O) = 3;D2P(B)P(C)ABCEF45321(2) 设计适当的数据结构：将每条道路的长度存在数组中。h43 = 3,2,3, 2,1,4, 3,4,5, 3,1,2;0 1 23210312345214323东西（水平）方向上的道路长度 存放在二维数组 h43 中：1223412422342100 1 2 3南北（垂直）方向上的道路长度 存放在二维
4、数组 v34 中：v34 = 2,2,3,4, 4,1,2,4, 1,2,2,3;(3) 为编程方便，将 图10-1 改为 图10-2h30h31h32h20h21h22h10h11h12h00h01h02v20v21v22v23v10v11v12v13v00v01v02v03(3, 3)0213213yx图10-2 方便编程的改造后的交通图 (4) 【任务10.1】变为：从 (0, 0) 到 (3, 3) 求最短路径问题。 定义 P44 = 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,第1维为行，第2维为列。这时P(O)为P01；P(N)为P10；P(A)为P33，下面
5、分阶段递推求解：阶段1： P01 = P00+h00 = 0+3 = 3; P10 = P00+v00 = 0+2 = 2; 阶段2： P11 = min P01+v01, P10+h10 = min3+1, 2+2 = 4 P02 = P01+h10 = 3+2 = 5 P20 = P10+v10 = 2+4 = 6 阶段3： P12 = min P02+v02, P11+h11 = min5+3, 4+1 = 5 P03 = P02+h02 = 5+3 = 8 P21 = min P11+v11, P20+h20 = min4+1, 6+1 = 5 P30 = P20+v20 = 6+1
6、= 7阶段4： P13 = min P03+v03, P12+h12 = min8+4, 5+4 = 9 P22 = min P12+v12, P21+h21 = min5+2, 5+4 = 7 P31 = min P21+v21, P30+h30 = min5+2, 7+3 = 7阶段5： P23 = min P13+v13, P22+h22 = min9+4, 7+5 = 12 P32 = min P22+v22, P31+h31 = min7+2, 7+1 = 8最后到终点： P33 = min P23+v23, P32+h32 = min12+3, 8+2 = 10数组P的通项表示为：
7、 Pij= min( ( Pi-1j+vi-1j), (Pij-1+hij-1) ) ( i, j0 ) P0j=P0j-1+h0j-1 ( i=0, j0 ) Pi0=Pi-10+vi-10 ( i0, j=0 ) P00=0 ( i=0, j=0 ) 最佳行走路径：P N L H D B A312345214323142212223344026734575578891210P点A点图10-3 各路口对 P点 的最小距离 int min(int,int); int main( ) int i,j; int h43= 3,2,3,2,1,4,3,4,5,3,1,2 ;int v34= 2,2,
8、3,4,4,1,2,4,1,2,2,3 ;int p44= 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ;p00=0; for(j=1; j=0;i-) /输出各路口对P的最小距离 for(j=0;j #include using namespace std; const int S=3215125; int d77; int main() memset(d,0,sizeof(d); int s1,i,j;s1=1000000; d06=S;for ( i=1; i=0;j-)for(i=0;ians) ans=x; return ans; 小结：动态规划的基本概念：- 阶
9、段 - 状态 - 决策与策略 - 状态转移方程动态规划基于分治思想，在每一阶段都将当前问题分解为多个已经解决的问题。动态规划方法是一个保证能获得最优解的方法，它是一个自底向上的过程，在每一阶段都列出所有可能的情况并逐个加以考察，无一遗漏，不会因剪枝而误删最优解。问题求解模式动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择， 达到结束状态。这些决策形成了一个决策序列，同时 确定了完成整个过程的一条活动路线（通常是求最优 的活动路线）。 初始状态决策决策决策结束状态动态规划的设计有一定的模式，一般要经历以下步骤：(1)划分阶段：按照问题的时间或空间特征，把问题
10、分为若干个阶段。在划分阶段时，要注意划分后的阶段是有序或可排序的，否则 问题无法求解。(2)确定状态和状态变量：将问题发展到各个阶段时所处的各种情况用不同的状态表示出来。当然，状态的选择要满足无后向性。(3)确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策导出本阶段的状态。如果确定了决策，状态转移方 程很容易写出。但事实上常常反过来做，根据相邻状态之间的关系来 确定决策。(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一 个递推的终止条件或边界条件。 多级图问题(multistage graph problem)：G = ( V, E ) 如下5级图：5个不相交的结点集
11、合 Vi , i=1,2,3,4,5。 V1 及 V5 分别只有 一个结点，称之为 源点S 和 汇点T 。寻找一条从 S 到 T 的最小耗费路径（同一级结点内无边连接）。向前法向后法向前法cost(i,j) = MIN c(j,k) + cost(i+1,k) cost(i,j)表示第i级上结点j到汇点T的最小耗费路径 c(j,k)表示结点j到k的耗费 目标：求cost(1,1) cost(4,9) = 4; cost(4,10) = 2; cost(4,11) = 5 cost(3,6) = MIN c(6,9) + cost(4,9); c(6,10) + cost(4,10) = 7 c
12、ost(3,7) = MIN c(7,9) + cost(4,9); c(7,10) + cost(4,10) = 5 cost(3,8) = MIN c(8,10) + cost(4,10); c(8,11) + cost(4,11) = 7 cost(2,2) = MIN c(2,6) + cost(3,6); c(2,7) + cost(3,7); c(2,8) + cost(3,8) = 7 cost(2,3) = 9; cost(2,4) = 18; cost(2,5) = 15 cost(1,1) = MIN c(1,2) + cost(2,2); c(1,3) + cost(2,
13、3) ; c(1,4) + cost(2,4);c(1,5) + cost(2,5) = 16记录路径：1 2 3 4 5 6 7 8 9 10 11 122 7 6 8 8 10 10 10 12 12 12 贪心法与动态规划法的差别：贪心法：自顶向下，产生一个按贪心策略形成的 判定序列，该序列不保证解是全局最优的。动态规划：自底向上，会产生许多判定序列，再 按最优化原理对这些序列加以筛选，去除那些非局部 最优的子序列。设 f (n,w) 表示前 n 个物品装 w 公斤重时的最大价值， wi为第 i 个物品的重量，vi 为第 i 个物品的价值，则递推公式为: f (i,w) = max f(i-1,w), f(i-1,w-wi)+vi 用动态规划方法求解背包问题： #define LIMIT 8 / 重量限制 #define N 5 / 物品种类 #define MIN 1 / 最小重量 struct body char name20; int size; int price; ;
