算法设计与分析实用教程杨克昌 第6章 动态规划

《算法设计与分析实用教程杨克昌 第6章 动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求掌握最优性原理与动态规划设计的基本步骤掌握应用动态规划设计求解0-1背包问题、三角形划分、最长子序列与最优路径问题等多阶段决策典型案例本章重点根据案例的实际构建状态转移方程在案例求解基础上理解与掌握最优性原理第6章动态规划6.1动态规划概述1.动态规划的概念(1)动态规划（Dynamicprogramming）是运筹学的一个分支，是求解决策过程最优化的数学方法。(2)动态规划处理的对象是多阶段决策问题。(3)多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段

2、都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。2.最优性原理作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。最优决策序列中的任何子序列都是最优的。“最优性原理”用数学语言描述：假设为了解决某一多阶段决策过程的优化问题，需要依次作出n个决策D1,D2

3、,…,Dn，如若这个决策序列是最优的，对于任何一个整数k，1

4、4*731；在7313中插入1个乘号使乘积最大为：731*3；在3926中插入2个乘号使乘积最大为：3*92*6；在4731392中插入3个乘号使乘积最大为：4*731*3*92。这些子问题的最优解都包含在原问题的最优解中。最优性原理是动态规划的基础。3.最优子结构特性举例（1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。（2）将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始条件。分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。（3）应用递推求

5、解最优值。递推计算最优值是动态规划算法的实施过程。（4）根据计算最优值时所得到的信息，构造最优解。构造最优解就是具体求出最优决策序列。4.动态规划实施步骤6.20-1背包问题6.2.1一般0−1背包问题案例提出：1.动态规划设计逆推求解要点2)逆推计算最优值for(j=0;j<=c;j++)if(j>=w[n])m[n][j]=p[n];//首先计算m(n,j)elsem[n][j]=0;for(i=n−1;i>=1;i−−)//逆推计算m(i,j)for(j=0;j<=c;j++)if(j>=w[i]&&m[

6、i+1][j]m(i+1,cw),i=1,2,…,n−1则x[i]=1；装载w(i)。其中cw=c开始，cw=cw−x(i)*w(i)。否则，x(i)=0,不装载w(i)。最后，所装载的物品效益之和与最优值比较，决定w(n)是否装载。2.动态规划设计顺推求解要点6.3西瓜分堆动态规划设计要点：

7、一般把n个整数分成两组，每组的个数不限，使两组数据和之差为最小。两组数据之和不一定能相等，不妨把数据之和较小的一组称为第1组。设n个整数b(i)之和为s，则第1组数据之和s1≤[s/2]，这里[x]为x的取整。问题要求在满足s1≤[s/2]前提下求s1最大值maxc，这样两组数据和之差的最小值为mind=s-2*maxc。如果maxc=[s/2]=s/2，则mind=0,即两组数据和相等。递推关系：6.4凸n边形的三角形划分给定凸n边形P={1,2,…,n},每一个顶点i带一个权数r(i)(i=1,2,…,n)

8、。要求在该凸n边形的顶点间连n-3条互不相交的连线，把凸n边形分成n-2个三角形，每个三角形的值为三角形的三个顶点权数之积。试确定一种三角剖分，使得剖分的n-2个三角形的值之和最小。例如一个各顶点带权数的凸7边形，如何连接对角线分割成5个三角形，使得这5个三角形的值之和最小？（1）建立递推关系设m(i,j)是求多边形划分的最小值，则有递推关系(j=i+2时，即三角形)(i