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

动态规划算法设计 一、实验内容 编程实现图示多段图的最短路径问题的动态规划算法。（源代码见附录A） 24 6 2 699 7 1 34 2 74 5 73 41 3 5 102 5 12 2 511 8 1186 11 二、实验目的及环境 实验目的： 1、理解动态规划算法的概念； 2、掌握动态规划算法的基本要素； 3、掌握设计动态规划算法的步骤； 4、通过应用范例学习动态规划算法的设计技巧与策略。 实验环境： WIN7 系统下VC++6.0环境 第 1 页 共 6 页

三、 实验分析与设计 采用动态规划算法的两个基本要素： 最优子结构性质：原问题的最优解包含了其子问题的最优解。 子问题的重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。 实验定义： #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])

六、 附录 A

#include #include #include #include #define MAX 100 #define n 12 #define k 5 int c[n][n];

void init(int cost[]) { int i,j; for(i=0;i<13;i++) { for(j=0;j<13;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)

第 4 页 共 6 页

{ if((c[j][r]+cost[r])

void bgraph(int bcost[],int path1[],int d[]) { int r,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])=2;i--) { path1[i]=d[path1[i+1]]; }

第 5 页 共 6 页