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

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

ID:52684430

大小:110.49 KB

页数:6页

时间:2020-03-29

动态规划算法分析实验报告.doc_第1页
动态规划算法分析实验报告.doc_第2页
动态规划算法分析实验报告.doc_第3页
动态规划算法分析实验报告.doc_第4页
动态规划算法分析实验报告.doc_第5页
资源描述:

《动态规划算法分析实验报告.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、动态规划算法设计一、实验内容编程实现图示多段图的最短路径问题的动态规划算法。(源代码见附录A)12345678111009129732811116535524644211127二、实验目的及环境实验目的:1、理解动态规划算法的概念;2、掌握动态规划算法的基本要素;3、掌握设计动态规划算法的步骤;4、通过应用范例学习动态规划算法的设计技巧与策略。实验环境:WIN7系统下VC++6.0环境第6页共6页三、实验分析与设计采用动态规划算法的两个基本要素:最优子结构性质:原问题的最优解包含了其子问题的最优解。子问题的重叠性质:每次产生的子问题并不总是新问题,有些子问题被反复计算多次

2、。实验定义:#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;

3、r<=n;r++){if(c[j][r]!=MAX){if((c[j][r]+cost[r])

4、的决策最优,最后构造一个最优解。经过反复的调试操作,程序运行才得出结果。第6页共6页三、附录A#include#include#include#include#defineMAX100#definen12#definek5intc[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;

5、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]

6、[temp]+cost[temp];for(r=0;r<=n;r++){if(c[j][r]!=MAX)第6页共6页{if((c[j][r]+cost[r])

7、cost[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])=2;i--){path1[i]=d[path1[i+1]];}

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。