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

1、第 1 页 共 6 页动态规划算法 设计一、实验内容编程实现图示多段图的最短路径问题的动态规划算法。（源代码见附录a）二、实验目的及环境实验目的：1、理解动态规划算法的概念；2、掌握动态规划算法的基本要素；3、掌握设计动态规划算法的步骤；4、通过应用范例学习动态规划算法的设计技巧与策略。实验环境：win7 系统下 vc+6 。0 环境1 234567811 10912 9 7 3 2 8 116 5 3 5 5 2 4 6 4 4 2 1 11 2 7第 2 页 共 6 页三、 实验分析与设计采用动态规划算法的两个基本要素: 最优子结构性质 ：原问题的最优解包含了其子问题的最优解. 子问题的重

2、叠性质 :每次产生的子问题并不总是新问题，有些子问题被反复计算多次。实验定义：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+) costj=0；for(j=n-1;j =1；j-) temp=0; min=cj temp

3、+cost temp ；/初始化最小值for（ r=0；r include stdlib。h #include conio。h include iostream 。h define max 100 #define n 12 define k 5 int cn n ; void init(int cost) int i,j ；for（i=0;i 13；i+) for(j=0 ；j13;j+) ci j=max; c12=9 ； c13=7;c1 4=3 ； c15=2；c2 6 =4； c2 7=2； c2 8=1 ；c36=2; c 3 7=7; c48 =11; c57 =11;c5 8=8

4、；c69 =6; c6 10=5; c7 9=4； c710=3; c8 10=5;c8 11=6；c9 12=4; c10 12=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=cj temp+costtemp ；for（r=0;r =n;r+) if(cj r ！=max ）第 5 页 共 6 页 if( （cj r+costr ）min） min=cj r+costr ；temp=r； costj=c j temp+cost temp;

5、dj=temp； path1=1；pathk=n; for(j=2 ；jk;j+ ）pathj=dpath j1 ；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=ctemp j +bcosttemp ；for(r=0;r=n ；r+) if(c r j!=max) if（ （c rj +bcostr ）min） min=cr j +bcostr; temp=r；bcostj=ctemp j+bcosttemp

6、 ；dj=temp; path11=1; path1k=n ；for(int i=4 ； i=2；i ) path1 i=d path1i+1; 第 6 页 共 6 页void main() int cur=-1 ；int cost13,d 12， bcost13 ；int pathk ; int path1k；init(cost） ; fgraph（cost,path,d); cout ”使用向前递推算法后的最短路径：nn; for(int i=1 ； i=5；i+ ） coutpathi ” ；coutn” ; coutendl最短路径为长度：cost1 endl；cout n; cout n 使用向后递推算法后的最短路径：n” ；bgrap