多段图的最短路径问题.doc

广东金融学院实验报告课程名称：算法设计与分析课程设计实验编号及实验名称实验三 动态规划算法I系 别应用数学系姓 名许夏梦学 号071612117班 级0716121实验地点新电605实验日期2009-9-30实验时数2指导教师骆世广同组其他成员成 绩一、 实验目的及要求1、理解最优子结构的问题。 有一类问题的活动过程可以分成若干个阶段，而且在任一个阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，信赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题的重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2、理解分段决策Bellman方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。3、一般方法1）找出最优解的性质，并刻画其结构特征；2）递归地定义最优值（写出动态规划方程）；3）以自底向上的方式计算出最优值；4）根据计算最优值时得到的信息，构造一个最优解。 步骤13是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略， 步骤3中记录的信息也较少；若需要求出问题的一个优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。二、 实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）使用软件：C+软件；使用实验设备：计算机：Intel(R);Pentium(R) 4 CPU 2.80GHz;2.79 GHz,0.99 GB 的内存；使用系统：Microsoft Windows XP;Professional;版本 2002；Service Pack 2.三、 实验内容及步骤（包含简要的实验步骤流程）实验内容：1、 编程实现多段图的最短路径问题的动态规划算法。2、 图的数据结构采用邻接表。3、 要求用文件装5个多段图数据，编写从文件到邻接表的函数。4、 验证算法的时间复杂性。多段图算法：Procedure FGRAPH（E,k,n,P）/输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c（i，j）是边的成本。P（1：k）是最小成本路径。/real COST(n),integer(n-1),P(k),r,j,k,nCOST(n)-0for j-n-1 to 1 by -1 do /计算COST（j）/设r是一个这样的结点，（j，r）E且使c（j，r）+COST（r）取最小值COST（j）- c（j，r）+COST（r）;D(j)-r;Repeat /向前对j-1进行决策/P（1）-1; P（k）-n;for j-2 to k-1 do / 找路径上的第j个节点/ P（j）-D(P(j-1);repeat;end FGRAPH四、 实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）1、数据的五段图见程序见附四-12、实验结果如下（程序见附四-2）：五、 实验总结（包括心得体会、问题回答及实验改进意见，可附页）通过理解最优子结构的性质和子问题重叠性质，以及理解分步决策Bellman方程，在计算机实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优，最后构造一个最优解。动态规划的思想很容易理解，但当用程序代码实现起来的时候又觉得有点困难，经过我反复的调试操作，我发现我对于邻接表的程序表达不是很好，我得在课后的时间发多点时间复习一下。六、 教师评语附四11234567811100912973281111653552464421112* 程序中的数据以次图为标准7附四2#include #include #include #include #define MAX 100 #define n 12 /*顶点数*/#define k 5 /*段数*/int cnn;void init(int cost) /初始化图int i,j;for(i=0;i13;i+)for(j=0;j13;j+)cij=MAX;c12=9;c13=7;c14=3;c15=2;c26=4;c27=2;c28=1;c36=2;c37=7;c48=11;c57=11;c58=8;c69=6;c610=5;c79=4;c710=3;c810=5;c811=6;c912=4;c1012=2;c1112=5;void fgraph(int cost,int path,int d) /使用向前递推算法求多段图的最短路径int r,j,temp,min;for(j=0;j=1;j-)temp=0;min=cjtemp+costtemp; /初始化最小值for(r=0;r=n;r+) if(cjr!=MAX) if(cjr+costr)min) /找到最小的rmin=cjr+costr;temp=r;costj=cjtemp+costtemp;dj=temp;path1=1;pathk=n;for(j=2;jk;j+)pathj=dpathj-1;void bgraph(int bcost,int path1,int d) / 使用向后递推算法求多段图的最短路径int r,j,temp,min;for(j=0;j=n;j+)bcostj=0;for(j=2;j=n;j+)temp=12;min=ctempj+bcosttemp; /初始化最小值for(r=0;r=n;r+) if(crj!=MAX) if(crj+bcostr)=2;i-)path1i=dpath1i+1;void main() int cur=-1;int cost13,d12,bcost13;int pathk; int path1k;coutttt动态规划解多段图问题endl;coutnn; init(cost); fgraph(cost,path,d); cout输出使用向前递推算法后的最短路径:nn;for(int i=1;i=5;i+)coutpathi ; coutn;coutendl最短路径为长度:cos