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

三、 实验分析与设计 采用动态规划算法的两个基本要素: 最优子结构性质：原问题的最优解包含了其子问题的最优解. 子问题的重叠性质:每次产生的子问题并不总是新问题，有些子问题被反复计算多次。 实验定义： ＃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；j〈k；j++） path［j]=d[path［j-1]]; } 后递推算法与前递推算法类似. 第 2 页 共 6 页 四、 实验结果显示 五、 实验总结 通过理解最优子结构的性质和子问题重叠性质,在VC++6。0环境下实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优,最后构造一个最优解。经过反复的调试操作，程序运行才得出结果. 第 3 页 共 6 页

六、 附录 A

＃include 〈stdio。h> ＃include 〈stdlib。h> #include 〈conio。h> ＃include 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］）第 5 页 共 6 页

｝

void main() {

int cur=-1； int cost[13],d［12]，bcost[13]； int path[k］; int path1［k]； init(cost）; fgraph（cost,path,d); cout<<”使用向前递推算法后的最短路径：\\n\\n\"; for(int i=1；i〈=5；i++） { cout<第 6 页 共 6 页