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

动态规划算法设计 一、实验内容 编程实现多段图的最短路径问题的动态规划算法。 二、实验目的及环境 实验目的： 1、理解动态规划算法的概念； 2、掌握动态规划算法的基本要素； 3、掌握设计动态规划算法的步骤； 4、通过应用范例学习动态规划算法的设计技巧与策略。 实验环境 WIN7 系统下VC++6.0环境 实验分析与设计 采用动态规划算法的两个基本要素 最优子结构性质：原问题的最优解包含了其子问题的最优解。 子问题的重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。 实验定义： #define n 12 /*定义顶点数*/ #define k 5 /*定义段数*/ void init(int cost [ ]) //初始化图 void fgraph(int cost [ ],int path[ ],int d[ ])向前递推算法求最短路径void bgraph(int bcost[ ],int path1[ ],int d[ ])向递推算法求最短路径向前递推算法： { int r,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]]; } 后递推算法前递推算法。 实验总结 通过理解最优子结构的性质和子问题重叠性质，在实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优，最后构造一个最优解。经过反复的调试操作，程序运行得出结果。 #include stdio.h #include stdlib.h #include conio.h #include iostream.h #define MAX 100 #define n 12 #define k 5 int c[n][n]; void init(int cost[]) { int i,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; } void fgraph(int cost[],int path[],int d[]) { int r,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) { 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]]; } void bgraph(int bcost