动态规划算法分析实验报告.doc
第PAGE7页共NUMPAGES7页
动态规划算法设计
一、实验内容
编程实现图示多段图的最短路径问题的动态规划算法。(源代码见附录A)
1
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)//找到最小的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;jk;j++)
path[j]=d[path[j-1]];
}
后递推算法与前递推算法类似。
实验结果显示
实验总结
通过理解最优子结构的性质和子问题重叠性质,在VC++6.0环境下实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优,最后构造一个最优解。经过反复的调试操作,程序运行才得出结果。
{
if((c[j][r]+cost[r])min)
{
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;jk;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)
{
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使用向前递推算法后的最