动态规划求解多段图问题

您所在的位置：网站首页 › python动态规划求解最短路径问题 › 动态规划求解多段图问题

动态规划求解多段图问题

2024-07-16 00:34| 来源: 网络整理| 查看: 265

动态规划求解多段图问题（非递归）问题描述求解思路动态规划逆序解法逆序实现代码动态规划逆序解法顺序实现代码

问题描述

如图所示,在A处有一水库,现需要从A点铺设一条管道到E点,边上的数字表示与其相连的两个地点之间所需修建的管道长度用c数组表示, 例如c(A,B1)=2。现要找出一条从A到E的修建线路,使得所需修建的管道长度最短。在这里插入图片描述

求解思路

对于有k个阶段的动态规划问题,从第k阶段到第1阶段的求解过程称为逆序解法,从第1阶段到第k阶段的求解过程称为顺序解法。

动态规划逆序解法

给出图的状态转移方程f(s)的递推顺序是从后向前,即E-→A,对应逆序解法。在这里插入图片描述用next表示路径.上一个顶点的后继顶点,其求解A到E最短路径的过程如下

逆序实现代码 #include #include 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=0;i--){ dp[i]=INF; for(int j=i;j

【本文地址】

动态规划求解多段图问题

动态规划求解多段图问题

今日新闻

推荐新闻