6、动态规划算法的应用.docx

《6、动态规划算法的应用.docx》由会员分享，可在线阅读，更多相关《6、动态规划算法的应用.docx（25页珍藏版）》请在三一办公上搜索。

1、课程设计说明书课程名 称：算法设计与分析-课程设计课程代码:7106620题 目:动态规划算法的应用年级/专业/班：学生姓名：学号：开始时间：2010年 12 月 27日完成时间：2011 年 01 月 07日课程设计成绩:学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分 （100）指导教师签名：年 月 日目 录1弓I言11.1问题的提出11.2国内外研究的现状11.3 任务与分析12程序的主要功能22.1求最短路径的功能22.2求最优树功能22.3求最小代价子母树功能33程序运行平台34总体设计45程序类的说明55.1最短路径的动态规划算法55.2最优

2、树的动态规划算法55.3最小代价子母树的动态规划算法66模块分析66.1最短路径的动态规划模块66.2最优树的动态规划模块76.3最小代价子母树的动态规划模块87系统测试97.1最短路径的动态规划测试结果：97.2最优树的动态规划117.3最小代价子母树测试结果118结论12致谢13参考文献14附录15摘要动态规划算法的有效性依赖于问题本身具有最优子结构性质和子问题重叠性质。动 态规划求最短路径，研究了任意点对的平面避障问题.用凸多边形表示障碍物，凸多边 形的集合构成障碍环境.在此基础上，提出了一种新的路径规划思路：对图结构进行扩 展，用传统的Floyed算法进行一级规划；对传统Floyed算

3、法扩展后进行二级规划，很 好地解决了任意点对的平面避障问题.利用矢量间夹角的关系来判断障碍环境中点对的 连线是否交叉于多边形.经理论证明和算例验证，该算法方便简洁，容易实现，表明了 算法的正确性.用动态规划算法构造最优二叉搜索树的详细步骤，并用C+语言具体实现了该算 法。用一定的空间换取时间，提高了解决本问题的效率。关键词：凸多边形；动态规划算法；最优子结构；子问题重叠；最优二叉搜索树1.1问题的提出动态规划问世以来，在经济管理、生产调度、工程技术、和最优控制等方面得到了 广泛的应用。例如最短路线、库存管理、设备更新、排序、装载等问题，用动态规划方 法比用其它方法求解更为方便。1.2国内外研究

4、的现状现今动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时 间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多 阶段决策过程，也可以用动态规划方法方便地求解。1.3任务与分析任务是实现多种问题的动态规划算法并分析、编程和总结，给出结论。1、给出动态规划的基本思想；2、给出最小代价子母树的动态规划算法和程序；3、给出最短路径的动态规划算法和程序；4、给出最优树的动态规划算法和程序。动态规划算法分析；1、动态规划算法的基本思想是段化自顶向下的分析自底向上运算，此方法 的正确性建立在最优性原理上。2、设计动态规划算法的步骤(1) 找出最优解的性质，并刻

5、划其结构特征。(2) 递归地定义最优值。(3) 以自底向上的方式计算出最优值。(4) 根据计算最优值时得到的信息，构造最优解。3、针对算法实现，要求掌握算法的思想和原理，通过编程语言(VC、VB、Java 等均可)实现算法。4、具体算法和方案可参考任务书后相关参考文献。2程序的主要功能2.1求最短路径的功能动态规划的正向思维方法的要点可归纳为一下三个步骤： 构造状态网络； 根据状态转移关系和状态转移方程建立最优值的递推计算式； 按阶段的先后秩序计算每个状态的最优值。2.2求最优树功能步骤一：寻找最优树结构。一个最优二叉树的子树必定包含连续范围的关键字kikj，1=i=j=n，同时也必 须含有连

6、续的虚叶子节点di-1dj。如果一棵最优二叉查找树T有一棵含有关键字kikj的子树T，那么，T也是一棵 最优查找树，这通过剪贴思想可以证明。现在开始构造最优子结构:在kikj中，选定一个r,i=r=i时，需要选择合适的kr作为根节点，然后其余节点kiK(r-1)和k(r+1广kj 构造左右孩子。这时要考虑左右孩子这些节点成为一个节点的子树后，它的搜索代价的 变化：根据ET的计算，得知它们的期望代价增加了 “子树中所有概率的总和” w。 wi,j =pl /对每个l=ij+ql /对每个 l=i-1j于是当 j=i 时，ei,j=pr + (ei,r-1+wi,r-1) + (er+1,j+wr

7、+1,j) =ei,r-1 + er+1,j+wi,j;步骤三：计算最优二叉树的期望代价ei,j =q(i-1) /如果 j=i-1min(ei,r-1 + er+1,j+wi,j),如果 i=j，其中 i=r=j wi,j=q(i-1)如果 j=i-1wi,j=wi,j-1+pj+qj 如果 i=j2.3求最小代价子母树功能设有一排数，共n个，例如：22，14，7，13，26，15，11。任意两个相邻的数可 以进行归并，归并的代价为该两个数的和，经过不断的归并，最后归为一个堆，而全部归并代价的和称为总代 价，给出一种归并算法，使代价为最小。例如有3个数，12 7 8。12 7 812 7 8

8、I / / I19 / 15 / /2727如上，归并的过程有2种：19+27=46和15+27=42。由此可见第二种归并方 法总代价为最小。3程序运行平台Windows XP、VC+6.0。具体操作如下:1、新建一个运算中；2、添加后缀为c.pp的源文件;3、在源文件中进行编程；4、编译，链接，执行。4总体设计最短路径设计：图（1）最优树的设计：图（2）最小代价子母树的设计：图(3)5程序类的说明5.1最短路径的动态规划算法Floyd算法实现计算完全最短路径的Floyd算法输入：图的权重矩阵W输出：包含最短路径长度的距离矩阵DWfor k1 to n dofor i 1 to n dofor

9、 j 1 to n doDi,j minDi,j,Di,k+Dk,j return D5.2最优树的动态规划算法输入：一个n个键的有序列表的查找概率数组P1n输出：在最优BST中成功查找的平均比较次数，以及最优BST中子树的根表ROptimalBST(p1n)for i 1 to n doCi,i-1 0Cii PiRi,i iCn+1,n 0for d1 to n-1 do /对角线计数for i 1 to n-d doj i+dminval 8for ki to j doif Ci,k-1+Ck+1,jminvalminvalCi,k-1+Ck+1,j;kminkRi,j kminsumP

10、i;for s i+1 to j do sumsum+PsCi,j minval+sumreturn C1,n,R5.3最小代价子母树的动态规划算法对fn+1(xn+1 )初始化；边界条件for k:=n downto 1 dofor 每一个 x EX dofor 每一个 u EU (x ) do beginf (x ):= 一个极值；8或一8x：+1:=Tk(xk,uk);状态转移方程t: 二 (fk+1 (xk+1),vk (xk,uk);基本方程(9)式if t比f (x )更优then f (x ):=t; 计算f (x )的最优值k kk kk k8或一8按照10式求出最优指标end

11、;t:= 一个极值；for 每一个 x EX doif f1 (x1) t匕 t 更优 then t:=f1 (x1);6模块分析6.1最短路径的动态规划模块void FLOYD(GRAPH g,int n,int dN,int pN) int i,j,k,w;for(i=0;in;i+)for(j=0;jn;j+)dij=g.edgesij;if(dijMAXDIST)&(dij!=0)elsepij=-1；for(i=0;in;i+)dii=0;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jdik+dkj)(dij=dik+dkj;pij=pik;6.2最优树的

12、动态规划模块void optimal_bst(double eMAXNUM,int rootMAXNUM,double wMAXNUM,int n)(int i =0,j=0;/针对左或右孩子为空树情况初始化for(i = 1;i=n+1;i+)(eii-1 = qi-1;wii-1 = qi-1;int l = 0;计算顺序如下：根据计算式：ei,j = ei,r-1+er+1,j/首先计算节点个数为1的最优二叉树的代价e1,1,e2,2/接着计算节点个数为1的最优二叉树的代价e1,2,e2,3/最后计算结点个数为n的最优二叉树的代价e1,n，利用之前保存的较少结点最优二叉树的结果。for(

13、l = 1;l=n;l+)(for(i = 1;i=n-l+1;i+)( j = i+l-1；eij = MAX;wij = wij-1 + pj+qj;for(int r = i;r=j;r+)( double t = 0;t = eir-1+er+1j + wij;if(teij)(eij= t;rootij = t; ) 6.3最小代价子母树的动态规划模块void PrintResult(MIN_NODE *pNode, bool br) ( using std:queue;queue aQueue;MIN_NODE* pointer = pNode;if(pointer)aQueue.

14、push(pointer); int level = pointer-level;while(!aQueue.empty()( pointer = aQueue.front();if(level!=pointer-level)( level=pointer-level;printf(n)； printf(val=%d level=%d | , pointer-minVal, pointer-level);aQueue.pop();if(pointer-pSubNode0)aQueue.push(pointer-pSubNode0); if(pointer-pSubNode1)( aQueue.

15、push(pointer-pSubNode1); 7系统测试7.1最短路径的动态规划测试结果图（4）二口 I?函*E:算法设计与分析Debug最短路径-eke径99径99径99径径 Jrre9Jrre9Jrre9Jrre0Jrre0 世 98 9 世 9E2E3 U4短短短短短s 为最最最最最- 0011223353 XX xz XX xz XX 原至一手一手一至一手一 444I4-4I4-44443到H最短路径: 3-09999B到i最短路径: 3-l9999&到2最短路径: 3-2 9999 3到4最短路径: 3-4 9999 &到S最短路径:3-510源点为。打5到。最短路径： 5-09

16、999S到1最短路径： 5-1 9999 5到2最短路径： 5-29999S到3最短路径： 5-3 99995到4最短路径: 5-49999Press any key to continue图（5）7.2最优树的动态规划7.3最小代价子母树测试结果图（7）8结论在做这个课程设计中，关键在于对动态规划思想的了解。这三个实际问题，在学习 过的知识中，通过数据结构来实现基本算法，再通过c语言来实现程序的调试、输出 结果。对于我来说，我的这个课程设计中的最小代价子母树有点难度，最短路径为标题 和最优树的求解相对容易些。在动态规划问题求解过程，由于自己对数据结构还不太熟 练，所以我也参考了一些资料。并且

17、不少操作需进一步完善，这次课程设计有许多不足 之处，可能是因为经验还不足，对问题预期不够等一些不可预见的原因所致。这些都是 以后做课程设计的经验，我想在以后的课程设计中，我会做得越来越好。致谢能够完成这次课程设计首先要感谢辅导老师谢春芝老师，在课程设计中我遇到了很 多的问题，谢老师都是很耐心的给我讲解，而且还教了我很多小技巧。其次要感谢黄襄 念老师，他教会我认识到算法的时间效率在现今的运用时多么的重要。再次要感谢的是 教我C语言的周立章老师，他教会了我C语言的基本语法知识以及编程技巧，使得我能 够了解到C语言未来在我人生中的用途，教会我要要高瞻远瞩要掌握全局，这样才是一 个优秀的程序员；这次能

18、够成功完成这次课程设计就是很好的证明。最后要感谢我的同 学，在编程的过程中我遇到了问题，而在此时老师也无法联系到，是我的同学帮我解决 问题，指出错误让我能顺利完成这次课程设计。再次感谢大家！参考文献1 严蔚敏吴伟民著.数据结构（C语言版）（第三版）.北京：清华大学出版社 2007.42 谭浩强著.C程序设计（第三版）.北京：清华大学出版社；2006.93 Anany Levitin著.潘彦译 算法设计与分析基础（第二版）.北京：清华大学 出版社；2010.14 美S巴斯著.计算机算法：设计和分析引论.朱洪等译 上海：复旦大学出版社;1985.1附录最短路径源程序：#include#define

19、 N 10#define MAXDIST 9999typedef structchar dataN;int edgesNN;GRAPH;void DIJKSTRA(GRAPH g,int n,int i,int d,int p)int sN;int mindist,dist;int j,k,u;for(j=0;jn;j+)dj=g.edgesij;sj=0;if(djMAXDIST)&(dj!=0)pj=i;elsepj=-1;si=1;for(j=0;jn-1;j+)mindist=MAXDIST;u=i;for(k=0;kn;k+)if(sk=0)&(dkmindist)u=k;mindi

20、st=dk;su=1;for(k=0;kn;k+)if(sk=0)dist=du+g.edgesuk;if(distdk)dk=dist;pk=u;void opdijk(int v0,int n,int d,int p)int i,j,k,pre;for(i=0;in;i+)if(i!=v0) printf(n%d,i);pre=pi;while(pre!=-1)printf(-%d,pre);pre=ppre;if(di=MAXDIST)printf(-%d,v0);printf(%d,di);void FLOYD(GRAPH g,int n,int dN,int pN)int i,j,k

21、,w;for(i=0;in;i+)for(j=0;jn;j+)dij=g.edgesij;if(dijMAXDIST)&(dij!=0) pij=j;elsepij=-1;for(i=0;in;i+)dii=0;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jdik+dkj)dij=dik+dkj;pij=pik;void opfloy(int n,int dN,int pathN)int i,j,k,c,min,next;for(i=0;in;i+) printf(nn 源点为 v%d:,i);for(j=0;j%d,next);next=pathnextj;if(

22、dij=MAXDIST) void main()printf(-%d,j);printf(t%d,dij);GRAPH g;int i,j,k,n;int dN,pN,sdNN,spNN;/ clrscr();g.data0=a;g.data1=b;g.data2=c;g.data3=d;g.data4=e;g.data5=f;for(i=0;in;i+)for(j=0;jn;j+)g.edgesij=MAXDIST;for(j=0;jn;j+)g.edgesjj=0;0 O O T 2 34g.edges g.edges g.edges g.edges g.edges g.edges g.e

23、dgesg.edges42 4 5 2 3 5 3510;30;100;5;50;10;20;60;for(i=0;in;i+)DIJKSTRA(g,n,i,d,p);/ opfloy(i,sd,sp);printf(nn 源点为 v%d:,i);opdijk(i,n,d,p);FLOYD(g,n,sd,sp);opfloy(n,sd,sp);getchar();n=6;最优树的源程序：#include using namespace std;#define MAXNUM 100#define MAX 65536/p中为有序关键字k1到k5的搜索概率，k1vk2vk3vk4vk5double

24、pMAXNUM = 0.00,0.15,0.10,0.05,0.10,0.20;double qMAXNUM = 0.05,0.10,0.05,0.05,0.05,0.10;void optimal_bst(double eMAXNUM,int rootMAXNUM,double wMAXNUM,intn)int i =0,j=0;/针对左或右孩子为空树情况初始化for(i = 1;i=n+1;i+)eii-1 = qi-1；wii-1 = qi-1；int l = 0;计算顺序如下：根据计算式：ei,j = ei,r-1+er+1,j/首先计算节点个数为1的最优二叉树的代价e1,1,e2,2

25、/ 接着计算节点个数为1的最优二叉树的代价e1,2,e2,3/./最后计算结点个数为n的最优二叉树的代价e1,n，利用之前保存的较 少结点最优二叉树的结果。for(l = 1;l=n;l+)for(i = 1;i=n-l+1;i+)j = i+l-1;eij = MAX;wij = wij-1 + pj+qj;for(int r = i;r=j;r+)double t = 0;t = eir-1+er+1j + wij;if(teij)eij= t;rootij = t;int main()double eMAXNUMMAXNUM;int rootMAXNUMMAXNUM;double wMA

26、XNUMMAXNUM;optimal_bst(e,root,w,5);for(int i =1;i=6;i+)for(int j = 0;j=5;j+)cout eij cout endl;最小代价子母树：MinCostTree.h./头 文件#ifndef _MINCASTTREE_H#define _MINCASTTREE_H#ifndef NULL#define NULL 0#endiftypedef struct MIN_NODEint minVal;int level;int index;MIN_NODE* pParent;MIN_NODE* pSubNode ；MIN_NODE;具

27、体程序：void GetMinCost(int *input, int num);#endif#include MinCostTree.h#include #include #include #define MAX_VAL 0xFFFFFint input=3,18,7,14,10,12,23,41,16,24;int input1=12,5,16,4;void PrintResult(MIN_NODE *pNode, bool br)using std:queue;queue aQueue;MIN_NODE* pointer = pNode;if(pointer)aQueue.push(po

28、inter);int level = pointer-level;while(!aQueue.empty()pointer = aQueue.front();if(level!=pointer-level)level=pointer-level;printf(n);printf(val=%d level=%d | , pointer-minVal, pointer-level);aQueue.pop();if(pointer-pSubNode0)aQueue.push(pointer-pSubNode0);if(pointer-pSubNode1) aQueue.push(pointer-pS

29、ubNode1); int main(int argc, char *agrv) MIN_NODE *pRoot=NULL;GetMinCost(input, 10);return 0;void GetMinCost(int *input, int num)MIN_NODE *pNode=NULL;pNode = new MIN_NODEnum*num;int idx=0;for(int i=0; inum; i+)switch(i)case 0:for(int j=0; jnum; j+)idx=i*num+j;pNodeidx.level = i;pNodeidx.index = j;pN

30、odeidx.minVal = 0;pNodeidx.pSubNode0=NULL;pNodeidx.pSubNode1=NULL;/idx+;break;case 1:for(int j=0; jnum-1; j+)idx=i*num+j;pNodeidx.level = i;pNodeidx.index = j;pNodeidx.minVal = inputj+inputj+1;pNodeidx.pSubNode0=NULL;pNodeidx.pSubNode1=NULL;/idx+;break;default:for(int j=0; jnum-i; j+)idx=i*num+j;int

31、 to=i+j;int sum = 0;for(int k=j; k=0; k-) index1 = k*num+j;index2 = inc*num+i-inc+j;/val = pRltkj + pRltinci-inc+j;val = pNodeindex1.minVil+pNodeindex2.minVal; if(pNodeidx.minValval) pNodeidx.minVal = val;pNodeidx.pSubNode0 = pNode+index1;pNodeidx.pSubNode1 = pNode+index2; inc+;pNodeidx.minVal+=sum; for(i=0; inum; i+) for(int j=0; jnum-i; j+) idx = i*num+j;printf(%03d , pNodeidx.minVal);printf(n);idx = num*(num-1);printf(min value=%03dn, pNodeidx.minVal);/PrintResult(pNode+idx, true);delete pNode;