文档详情

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

发布:2024-05-04约2.35千字共6页下载文档
文本预览下载声明

第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使用向前递推算法后的最

显示全部
相似文档