多段图的最短路径问题

《多段图的最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、广东金融学院实验报告课程名称：算法设计与分析课程设计实验编号及实验名称实验三动态规划算法I系别应用数学系姓名许夏梦学号071612117班级0716121实验地点新电605实验日期2009-9-30实验时数2指导教师骆世广同组其他成员成绩一、实验目的及要求1、理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一个阶段后的行为依赖于该阶段的状态，与该阶段Z前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（RichardBellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的

2、算法设计方法一一动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，信赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题的重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2、理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。3、一般方法1）找出最优解的性质，并刻画其结构特征；2）递归地定义最优值（写出动态规划方程）；

3、3）以自底向上的方式计算出最优值；4）根据计算最优值时得到的信息，构造一个最优解。步骤1—3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个优解，则必须执行步骤4,步骤3中记录的信息必须足够多以便构造最优解。二、实验坏境及相关情况（包含使用软件、实验设备、主要仪器及材料等）使用软件：C++软件；使用实验设备：计算机:Intel（R）;Pentium（R）4CPU2.80GHz;2.79GHz,0.99GB的内存；使用系统：MicrosoftWindowsXP;Professional;版本200

4、2；ServicePack2.三、实验内容及步骤(包含简要的实验步骤流程)实验内容：1、编程实现多段图的最短路径问题的动态规划算法。2、图的数据结构采用邻接表。3、要求用文件装5个多段图数据，编写从文件到邻接表的函数。4、验证算法的时间复杂性。多段图算法：ProcedureFGRAPH(E,k,n,P)//输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c(i,j)是边的成本。P(1：k)是最小成本路径。//realCOST(n),integer(n-1),P(k),r,j,k,nCOST(n)<-0forj<-n~lto1by~1do/

5、/计算COST(j)//设r是一个这样的结点，(j,r)wE且使c(j,r)+COST(r)収最小值COST(j)<-c(j,r)+COST(r);D(j)<-r;Repeat//向前对j-l进行决策//P(1)<-l;P(k)<-n;forj<-2tok-1do//找路径上的第j个节点//P(j)<-D(P(j-l));repeat;endFGRAPHW.实验结果(包括程序或图表、结论陈述、数据记录及分析等，可附页)1、数据的五段图见程序见附四-12、实验结果如下(程序见附四-2)：粘处J0716121175?幵始£K吻雯

6、血未体4x〈x2Aa--A

7、③B页

8、EI右高引用邮件圭阅视奁AaBI.4更改样式标题1富富X头FAaBbCcDc

9、AaBbCcD(-试卷A4・・・・无富忑11-Mier...■蕃言蛊*-1贡始S傷庁>>2Intern...•■实验三目071612117...荧面：2/6M2：1.586笛入五、实验总结（包括心得体会、问题回答及实验改进意见，可附页）通过理解最优子结构的性质和子问题重叠性质，以及理解分步决策Bellman方程，在计算机实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优，最后构造一个最优解。动态规划的思想很容易理解，但当用程序代码实现起來的时候又觉得有点困难

10、，经过我反复的调试操作，我发现我对于邻接表的程序表达不是很好，我得在课后的时间发多点时间复习一下。六、教师评语附四T11*程序中的数据以次图为标准附四一2#include#include#includenclude#defineMAX100#definen12/*顶点数*/#definek5/*段数*/intc[n][n];voidinit(intcost[])//初始化图{inti,j;for(i=0;i<13;i++){for(j=0;j<13;j++){c[i][j]二MAX

11、;c[l][2]二9;c[l][3]二