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

动态规划算法设计一、实验内容编程实现图示多段图的最短路径问题的动态规划算法。（源代码见附录A）12345678111009129732811116535524644211127二、实验目的及环境 实验目的：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=1;j-) temp=0; min=cjtemp+costtemp; /初始化最小值for(r=0;r=n;r+) if(cjr!=MAX) if(cjr+costr)min) /找到最小的r min=cjr+costr; temp=r; costj=cjtemp+costtemp; dj=temp; path1=1; pathk=n; for(j=2;jk;j+) pathj=dpathj-1; 后递推算法与前递推算法类似。四、 实验结果显示五、 实验总结通过理解最优子结构的性质和子问题重叠性质，在VC+6.0环境下实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优，最后构造一个最优解。经过反复的调试操作，程序运行才得出结果。六、 附录 A#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) min=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; init(cost); fgraph(cost,path,d); cout使用向前递推算法后的最短路径:nn; for(int i=1;i=5;i+) coutpathi ; coutn; coutendl最短路径为长度:cost1endl; coutn; coutn使用向后递推算法后的最短路径:nn; bgraph(bco