动态规划算法分析实验报告.doc
- 文档编号:1221967
- 上传时间:2023-04-30
- 格式:DOC
- 页数:6
- 大小:102.50KB
动态规划算法分析实验报告.doc
《动态规划算法分析实验报告.doc》由会员分享,可在线阅读,更多相关《动态规划算法分析实验报告.doc(6页珍藏版)》请在冰点文库上搜索。
动态规划算法设计
一、实验内容
编程实现图示多段图的最短路径问题的动态规划算法。
(源代码见附录A)
1
2
3
4
5
6
7
8
11
100
9
12
9
7
3
2
8
1111
6
5
3
5
5
2
4
6
4
4
2
1
11
2
7
二、实验目的及环境
实验目的:
1、理解动态规划算法的概念;
2、掌握动态规划算法的基本要素;
3、掌握设计动态规划算法的步骤;
4、通过应用范例学习动态规划算法的设计技巧与策略。
实验环境:
WIN7系统下VC++6.0环境
三、实验分析与设计
采用动态规划算法的两个基本要素:
最优子结构性质:
原问题的最优解包含了其子问题的最优解。
子问题的重叠性质:
每次产生的子问题并不总是新问题,有些子问题被反复计算多次。
实验定义:
#definen12/*定义顶点数*/
#definek5/*定义段数*/
voidinit(intcost[])//初始化图
voidfgraph(intcost[],intpath[],intd[])向前递推算法求最短路径
voidbgraph(intbcost[],intpath1[],intd[])向后递推算法求最短路径
向前递推算法实现:
{intr,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=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 path[j]=d[path[j-1]]; } 后递推算法与前递推算法类似。 四、实验结果显示 五、实验总结 通过理解最优子结构的性质和子问题重叠性质,在VC++6.0环境下实现动态规划算法。 动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优,最后构造一个最优解。 经过反复的调试操作,程序运行才得出结果。 六、附录A #include #include #include #include #defineMAX100 #definen12 #definek5 intc[n][n]; voidinit(intcost[]) { inti,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; } voidfgraph(intcost[],intpath[],intd[]) { intr,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=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 path[j]=d[path[j-1]]; } voidbgraph(intbcost[],intpath1[],intd[]) { intr,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]) { min=c[r][j]+bcost[r]; temp=r; } } } bcost[j]=c[temp][j]+bcost[temp]; d[j]=temp; } path1[1]=1; path1[k]=n; for(inti=4;i>=2;i--) { path1[i]=d[path1[i+1]]; } } voidmain() { intcur=-1; intcost[13],d[12],bcost[13]; intpath[k]; intpath1[k]; init(cost); fgraph(cost,path,d); cout<<"使用向前递推算法后的最短路径: \n\n"; for(inti=1;i<=5;i++) { cout< } cout<<"\n"; cout< "< cout<<"\n"; cout<<"\n使用向后递推算法后的最短路径: \n\n"; bgraph(bcost,path1,d); for(i=1;i<=5;i++) { cout< } cout<<"\n"; cout< "< cout<<"\n"; } 第6页共6页
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 算法 分析 实验 报告