lingo动态规划实验报告 [动态规划算法分析实验报告x]

动态规划算法设计

、实验内容

编程实现图示多段图的最短路径问题的动态规划算法。 （源代码见附录A）

、实验目的及环境

实验目的：

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<=n ;j++)

cost[j]=0;

for(j=n_1;j>=1;j__)

{ temp=0;

mi n=c[j][temp]+cost[temp]; // 初始化最小值

for(r=0;r<=n ;r++)

{ if(c[j][r]!=MAX)

{ if((c[j][r]+cost[r])<mi n) 〃找到最小的 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<k;j++)

path[j]=d[path[j-1]];

}

后递推算法与前递推算法类似

四、实验结果显示

五、实验总结

通过理解最优子结构的性质和子问题重叠性质，在 VC++6.0环境下实现动态 规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优， 最

后构造一个最优解。经过反复的调试操作，程序运行才得出结果。

六、 附录 A

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <iostream.h>

#define MAX 100

#define n 12

#define k 5

int c[n][n];

void init(int cost[])

{

int i,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;

}

void fgraph(int cost[],int path[],int d[])

{

int r,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)

{

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<k;j++)

path[j]=d[path[j-1]];

}

void bgraph(int bcost[],int path1[],int d[])

{

int r,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(int i=4;i>=2;i--)

{

path1[i]=d[path1[i+1]];

}

void main()

{

int cur=-1;

int cost[13],d[12],bcost[13];

int path[k];

int path1[k];

init(cost);

fgraph(cost,path,d);

cout<<" 使用向前递推算法后的最短路径 :\n\n";

for(int i=1;i<=5;i++)

{

cout<<path[i]<<" ";

}

cout<<"\n";

cout<<endl<<" 最短路径为长度 :"<<cost[1]<<endl;

cout<<"\n";

cout<<"\n 使用向后递推算法后的最短路径 :\n\n";

bgraph(bcost,path1,d);

for(i=1;i<=5;i++)

{

cout<<path1[i]<<" ";

}

cout<<"\n";

cout<<endl<<" 最短路径为长度 :"<<bcost[12]<<endl; cout<<"\n";

}