动态规划算法分析实验报告

第1页共6页动态规划算法设计一、实验内容编程实现图示多段图的最短路径问题的动态规划算法。（源代码见附录A）二、实验目的及环境实验目的：1、理解动态规划算法的概念；2、掌握动态规划算法的基本要素；3、掌握设计动态规划算法的步骤；4、通过应用范例学习动态规划算法的设计技巧与策略。实验环境：WIN7系统下VC++6.0环境121314151617181111001911297328111165355246442111271第2页共6页三、实验分析与设计采用动态规划算法的两个基本要素：最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题的重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。实验定义：#definen12/*定义顶点数*/#definek5/*定义段数*/voidinit(intcost[])//初始化图voidfgraph(intcost[],intpath[],intd[])向前递推算法求最短路径voidbgraph(intbcost[],intpath1[],intd[])向后递推算法求最短路径向前递推算法实现：{intr,j,temp,min;for(j=0;j=n;j++)cost[j]=0;for(j=n-1;j=1;j--){temp=0;min=c[j][temp]+cost[temp];//初始化最小值for(r=0;r=n;r++){if(c[j][r]!=MAX){if((c[j][r]+cost[r])min)//找到最小的r{min=c[j][r]+cost[r];temp=r;}}}cost[j]=c[j][temp]+cost[temp];d[j]=temp;}path[1]=1;path[k]=n;for(j=2;jk;j++)path[j]=d[path[j-1]];}后递推算法与前递推算法类似。第3页共6页四、实验结果显示五、实验总结通过理解最优子结构的性质和子问题重叠性质，在VC++6.0环境下实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优，最后构造一个最优解。经过反复的调试操作，程序运行才得出结果。第4页共6页六、附录A#includestdio.h#includestdlib.h#includeconio.h#includeiostream.h#defineMAX100#definen12#definek5intc[n][n];voidinit(intcost[]){inti,j;for(i=0;i13;i++){for(j=0;j13;j++){c[i][j]=MAX;}}c[1][2]=9;c[1][3]=7;c[1][4]=3;c[1][5]=2;c[2][6]=4;c[2][7]=2;c[2][8]=1;c[3][6]=2;c[3][7]=7;c[4][8]=11;c[5][7]=11;c[5][8]=8;c[6][9]=6;c[6][10]=5;c[7][9]=4;c[7][10]=3;c[8][10]=5;c[8][11]=6;c[9][12]=4;c[10][12]=2;c[11][12]=5;}voidfgraph(intcost[],intpath[],intd[]){intr,j,temp,min;for(j=0;j=n;j++)cost[j]=0;for(j=n-1;j=1;j--){temp=0;min=c[j][temp]+cost[temp];for(r=0;r=n;r++){if(c[j][r]!=MAX)第5页共6页{if((c[j][r]+cost[r])min){min=c[j][r]+cost[r];temp=r;}}}cost[j]=c[j][temp]+cost[temp];d[j]=temp;}path[1]=1;path[k]=n;for(j=2;jk;j++)path[j]=d[path[j-1]];}voidbgraph(intbcost[],intpath1[],intd[]){intr,j,temp,min;for(j=0;j=n;j++)bcost[j]=0;for(j=2;j=n;j++){temp=12;min=c[temp][j]+bcost[temp];for(r=0;r=n;r++){if(c[r][j]!=MAX){if((c[r][j]+bcost[r])min){min=c[r][j]+bcost[r];temp=r;}}}bcost[j]=c[temp][j]+bcost[temp];d[j]=temp;}path1[1]=1;path1[k]=n;for(inti=4;i=2;i--){path1[i]=d[path1[i+1]];}第6页共6页}voidmain(){intcur=-1;intcost[13],d[12],bcost[13];intpath[k];intpath1[k];init(cost);fgraph(cost,path,d);cout使用向前递推算法后的最短路径:\n\n;for(inti=1;i=5;i++){coutpath[i];}cout\n;coutendl最短路径为长度:cost[1]endl;cout\n;cout\n使用向后递推算法后的最短路径:\n\n;bgraph(bcost,path1,d);for(i=1;i=5;i++){coutpath1[i];}cout\n;coutendl最短路径为长度:bcost[12]endl;cout\n;}