动态规划求解多段图问题
2021/12/23 23:15:51
本文主要是介绍动态规划求解多段图问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
动态规划求解多段图问题(非递归)
- 问题描述
- 求解思路
- 动态规划逆序解法
- 逆序实现代码
- 动态规划逆序解法
- 顺序实现代码
问题描述
如图所示,在A处有一水库,现需要从A点铺设一条管道到E点,边上的数字表示与其相连的两个地点之间所需修建的管道长度用c数组表示, 例如c(A,B1)=2。现要找出一条从A到E的修建线路,使得所需修建的管道长度最短。
求解思路
对于有k个阶段的动态规划问题,从第k阶段到第1阶段的求解过程称为逆序解法,从第1阶段到第k阶段的求解过程称为顺序解法。
动态规划逆序解法
给出图的状态转移方程f(s)的递推顺序是从后向前,即E-→A,对应逆序解法。
用next表示路径.上一个顶点的后继顶点,其求解A到E最短路径的过程如下
逆序实现代码
#include <iostream> #include <cstring> using namespace std; #define INF 0x3f3f3f3f #define MAX 21 int n=10; int c[MAX][MAX]; int pre[MAX]; int dp[MAX]; void Init(){ memset(c,0,sizeof(c)); memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre)); for(int j=0;j<n;j++){ c[j][j]=0; } c[0][1]=2;c[0][2]=4;c[0][3]=3; c[1][4]=7;c[1][5]=4; c[2][4]=3;c[2][5]=2;c[2][6]=4; c[3][4]=6;c[3][5]=2;c[3][6]=5; c[4][7]=3;c[4][8]=4; c[5][7]=6;c[5][8]=3; c[6][7]=3;c[6][8]=3; c[7][9]=3; c[8][9]=4; } int main() { Init(); for(int i=n-2;i>=0;i--){ dp[i]=INF; for(int j=i;j<n;j++){ if(c[i][j]!=0){ if(c[i][j]+dp[j]<dp[i]){ pre[i]=j; dp[i]=c[i][j]+dp[j]; } } } } cout<<dp[0]<<endl; cout<<"最短路径为"<<endl; int i=0; cout<<"0-->"; while(true){ cout<<pre[i]; i=pre[i]; if(i==9) break; cout<<"-->"; } return 0; }
动态规划逆序解法
对于图8. 4,顺序解法是从源点出发,求出到达当前状态的最短路径,再考虑下一个阶段,直到终点E。对应的状态转移方程如下:
pre 表示路径,上一个顶点的前驱顶点,其求解 A到E最短路径的过程 如下。
顺序实现代码
#include <iostream> #include <cstring> using namespace std; #define INF 0x3f3f3f3f int main() { int n=10,k=1,j=1; int c[n][n]; int pre[n]; int dp[n]; memset(c,0,sizeof(c)); memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre)); int cost=0; dp[0]=0; c[0][1]=2;c[0][2]=4;c[0][3]=3; c[1][4]=7;c[1][5]=4; c[2][4]=3;c[2][5]=2;c[2][6]=4; c[3][4]=6;c[3][5]=2;c[3][6]=5; c[4][7]=3;c[4][8]=4; c[5][7]=6;c[5][8]=3; c[6][7]=3;c[6][8]=3; c[7][9]=3; c[8][9]=4; for(k=1;k<n;k++){//先算和0连着的3个点,不用比大小,所以可以先算 if(c[0][k]!=0){ dp[k]=dp[0]+c[0][k]; } else{ break; } } int mini;//记录最小点的序号 for(j=k;j<n;j++){ int mincost=INF;//记录最短距离 for(int i=1;i<n;i++){ if(c[i][j]!=0){ cost=dp[i]+c[i][j];//计算每两个链接点的距离 if(mincost>cost){//替换最小距离 mincost=cost; mini=i; } } } dp[j]=mincost;//记录到节点j的最小距离 pre[j]=mini;//记录到节点j最近的点 } cout<<dp[9]<<endl; int i=9; cout<<"9<--"; while(true){ cout<<pre[i]; i=pre[i]; if(i==0) break; cout<<"<--"; } return 0; }
这篇关于动态规划求解多段图问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?