【动态规划】多段图最短路径(动图演示)

简介: 多段图是一个有向的无环图。求解从起始点v0到终止点的最短路径的长度, 首先看一下这个问题是否具有最优子结构的性质。对于每一点来说,从v0 到它的最短路径有两种可能,分别是从v0直接到该点或者是从最短的前驱 节点开始到该节点。从这里可以看出有递归的性质,所以使用回溯的方法 也是可以解决的。即从终点开始,依次向前找到最短的路径。由于递归本 身所用的时间较长,并且在回溯的过程中存在重复的工作,所以使用动态规划更好。

写在前面:


多段图是一个有向的无环图。求解从起始点v0到终止点的最短路径的长度, 首先看一下这个问题是否具有最优子结构的性质。对于每一点来说,从v0 到它的最短路径有两种可能,分别是从v0直接到该点或者是从最短的前驱 节点开始到该节点。从这里可以看出有递归的性质,所以使用回溯的方法 也是可以解决的。即从终点开始,依次向前找到最短的路径。由于递归本 身所用的时间较长,并且在回溯的过程中存在重复的工作,所以使用动态规划更好。


动图演示:


多段图: 假设图G=(V,E)是一个带权的有向图,如果可以把顶点集合V划分为k(2<=k<=n)个互不相交的子集Vi(1<=i<=k),其中V1和Vk分别只有一个顶点s(源点)和一个顶点t(终点)。每组子集的顶点都互不相交,即u∈Vi(始点)与v∈Vi+1(终点)互不相交,且边(u,v)有一个正权重值,这种图称为多段图。 多段图的最短路径问题:


🍓一.创建多段图


1.根据邻接矩阵创建多段图。


2.划分子集:因为多段图可以将顶点划分为k个互不相交的子集,所以将它划分为k段,每段都包含顶点,且每段的顶点互不相交。


3.为每个顶点编号,同一子集的顶点顺序无关紧要。源点s为0,终点t为n-1。


🍇二.证明满足最优性原理


设s,s,s1,s2,……,sp,t是s到t的一条最短路径,且s到s1的路径已经求出,则问题转为s1到t的最短路径,因此s1,s2,……,sp,t构成一条最短路径,如果不是,则设s1,r1,r2,……,rp,t是一条从s1到t的最短路径,则s,s1,r1,r2,……,rp,t是一条从s到t的最短路径且比s,s1,s2,……,sp,t短,因此矛盾,则满足最优性原理。


🍒三.设置子问题


自顶向下 对多段图的边(u,v),用c表示边上的权值,将从源点s到终点t的最短路径记为d(s,t),则从源点0到终点9的最短路径d(0,9)由下式确定:


d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}


这是最后一个阶段的决策,它依赖于d(1,9)、d(2,9)和d(3,9)的计算结果。


d(1,9)=min{c14+d(4,9),c15+d(5,9)}


d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}


d(3,9)=min{c35+d(5,9),c36+d(6,9)}


这一阶段的决策又依赖于d(4,9)、d(5,9)和d(6,9)的计算结果。


d(4,9)=min{c47+d(7,9),c48+d(8,9)}


d(5,9)=min{c57+d(7,9),c58+d(8,9)}


d(6,9)=min{c67+d(7,9),c68+d(8,9)}


这一阶段的决策依赖于d(7,9)和d(8,9)的计算。


d(7,9)和d(8,9)可以直接获得(括号中给出了决策产生的状态转移):


d(7,9)=c79=7(7→9)


d(8,9)=C89=3(8→9)


自底向上 反向求解出最短的路径,得到:最短路径为0→3→5→8→9,长度为16。


🍑建立多段图的邻接矩阵:



动图演示:多段图: 假设图G=(V,E)是一个带权的有向图,如果可以把顶点集合V划分为k(2<=k<=n)个互不相交的子集Vi(1<=i<=k),其中V1和Vk分别只有一个顶点s(源点)和一个顶点t(终点)。每组子集的顶点都互不相交,即u∈Vi(始点)与v∈Vi+1(终点)互不相交,且边(u,v)有一个正权重值,这种图称为多段图。 多段图的最短路径问题:



目录


🍓一.创建多段图


🍇二.证明满足最优性原理


🍒三.设置子问题


🍓一.创建多段图

1.根据邻接矩阵创建多段图。


2.划分子集:因为多段图可以将顶点划分为k个互不相交的子集,所以将它划分为k段,每段都包含顶点,且每段的顶点互不相交。


3.为每个顶点编号,同一子集的顶点顺序无关紧要。源点s为0,终点t为n-1。


🍇二.证明满足最优性原理

设s,s,s1,s2,……,sp,t是s到t的一条最短路径,且s到s1的路径已经求出,则问题转为s1到t的最短路径,因此s1,s2,……,sp,t构成一条最短路径,如果不是,则设s1,r1,r2,……,rp,t是一条从s1到t的最短路径,则s,s1,r1,r2,……,rp,t是一条从s到t的最短路径且比s,s1,s2,……,sp,t短,因此矛盾,则满足最优性原理。


🍒三.设置子问题


自顶向下 对多段图的边(u,v),用c表示边上的权值,将从源点s到终点t的最短路径记为d(s,t),则从源点0到终点9的最短路径d(0,9)由下式确定:


d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}


这是最后一个阶段的决策,它依赖于d(1,9)、d(2,9)和d(3,9)的计算结果。


d(1,9)=min{c14+d(4,9),c15+d(5,9)}


d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}


d(3,9)=min{c35+d(5,9),c36+d(6,9)}


这一阶段的决策又依赖于d(4,9)、d(5,9)和d(6,9)的计算结果。


d(4,9)=min{c47+d(7,9),c48+d(8,9)}


d(5,9)=min{c57+d(7,9),c58+d(8,9)}


d(6,9)=min{c67+d(7,9),c68+d(8,9)}


这一阶段的决策依赖于d(7,9)和d(8,9)的计算。


d(7,9)和d(8,9)可以直接获得(括号中给出了决策产生的状态转移):


d(7,9)=c79=7(7→9)


d(8,9)=C89=3(8→9)


自底向上 反向求解出最短的路径,得到:最短路径为0→3→5→8→9,长度为16。


🍑建立多段图的邻接矩阵:

int CreatGraph()
{
  int i, j, k;
  int weight;
  int vnum, arcnum;
  printf("请输入顶点的个数:");
  scanf_s("%d", &vnum);
  printf("请输入边的个数:");
  scanf_s("%d",&arcnum);
  for (i= 0; i < vnum; i++)
    for (j = 0; j < vnum; j++)
      arc[i][j] = MAX;
  for (k = 0; k < arcnum; k++)
  {
    printf("请输入边的两个顶点和权值:");
    scanf_s("%d,%d,%d", &i, &j, &weight);
    arc[i][j] = weight;
  }
  return vnum;
}




代码:

int BackPath(int n)
{
  int i, j;
  int cost[N], path[N];
  for (i = 1; i < n; i++)
  {
    cost[i] = MAX;
    path[i] = -1;
  }
  cost[0] = 0;
  path[0] = -1;
for (j = 1; j < n; j++)
  {
    for (i = j - 1; i >= 0; i--)
    {
      if (arc[i][j] + cost[i] < cost[j])
      {
        cost[j] = arc[i][j] + cost[i];
        path[j] = i;
      }
    }
  }
printf("%d", n - 1);
i = n - 1;
while (path[i] >= 0)
{
printf("<-%d", path[i]);
i = path[i];
}
return cost[n - 1];
}


相关文章
|
算法 定位技术 C++
基本算法-回溯法(迷宫问题)
基本算法-回溯法(迷宫问题)
1364 0
|
存储 自然语言处理 算法
【编译原理】LR(1)分析法:C/C++实现
【编译原理】LR(1)分析法:C/C++实现
1425 0
|
Linux Perl
Linux centos7升级内核(两种方法:内核编译和yum更新)
Linux centos7升级内核(两种方法:内核编译和yum更新)
3689 1
Linux centos7升级内核(两种方法:内核编译和yum更新)
|
NoSQL 数据可视化 关系型数据库
推荐几个好用的redis可视化工具
推荐几个好用的redis可视化工具
16569 1
|
缓存 Linux 开发工具
CentOS 7- 配置阿里镜像源
阿里镜像官方地址http://mirrors.aliyun.com/ 1、点击官方提供的相应系统的帮助 :2、查看不同版本的系统操作: 下载源1、安装wget yum install -y wget2、下载CentOS 7的repo文件wget -O /etc/yum.
254873 0
|
存储 算法 大数据
算法设计与分析 实验三 回溯法求解地图填色问题(下)
算法设计与分析 实验三 回溯法求解地图填色问题
1093 0
算法设计与分析 实验三 回溯法求解地图填色问题(下)
|
9月前
|
数据安全/隐私保护
思科模拟器Cisco Packet Tracer 8.2.1注册、下载和安装教程(正确+详细)
本文详细总结了思科模拟器Cisco Packet Tracer 8.2.1注册、下载和安装教程(正确+详细),看这一篇就够啦~
27733 5
思科模拟器Cisco Packet Tracer 8.2.1注册、下载和安装教程(正确+详细)
|
11月前
|
并行计算 异构计算
卸载原有的cuda,更新cuda
本文提供了一个更新CUDA版本的详细指南,包括如何查看当前CUDA版本、检查可安装的CUDA版本、卸载旧版本CUDA以及安装新版本的CUDA。
8897 3
卸载原有的cuda,更新cuda
|
11月前
论多段图的最短路径问题(我认为本质上还是暴力枚举法)
本文讨论了多段图最短路径问题的解决方法,认为本质上是使用暴力枚举法,通过逐步计算每个阶段点的最短距离来确定从起点到终点的最短路径。
163 2
论多段图的最短路径问题(我认为本质上还是暴力枚举法)
|
11月前
|
Java Maven Spring
如何在idea中创建Springboot项目? 手把手带你创建Springboot项目,稳!
文章详细介绍了在IDEA中创建Spring Boot项目的过程,包括选择Spring Initializr、配置项目属性、选择Spring Boot版本、导入依赖、等待依赖下载以及项目结构简介。
11153 1

热门文章

最新文章