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

这篇具有很好参考价值的文章主要介绍了【动态规划】多段图最短路径(动图演示)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

📃个人主页:个人主页

🔥系列专栏:数据结构与算法

💬推荐一款模拟面试、刷题神器,从基础到大厂面试题👉点击跳转刷题网站进行注册学习

写在前面:

多段图是一个有向的无环图。求解从起始点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。 

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

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;
}

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

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

下标

1

2

3

4

5

6

7

8

9

cost[n]

元素值

4

2

3

8

7

10

13

13

16

path[n]

状态

0→1

0→2

0→3

2→4

3→5

2→6

4→7

5→8

8→9

 代码:文章来源地址https://www.toymoban.com/news/detail-404113.html

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];
}

到了这里,关于【动态规划】多段图最短路径(动图演示)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 动态规划 状态压缩DP 最短Hamilton路径

    给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数 n 。 接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[

    2024年02月19日
    浏览(40)
  • Python 图算法,图最短路径,图广度优先搜索,图深度优先搜索,图排序

    一、图数据库相关算法 图数据库是一种专门用来存储和处理图数据的数据库系统。它使用图结构来表示数据之间的关联关系,以及节点和边之间的属性信息。以下是一些常用的图数据库算法: 1. 最短路径算法:最短路径算法用于计算图中两个节点之间的最短路径,例如Dijk

    2024年02月15日
    浏览(36)
  • 迪杰斯特拉(Dijkstra's )算法——解决带权有向无向图最短路径

    迪杰斯特拉算法(Dijkstra\\\'s Algorithm),又称为狄克斯特拉算法,是一种用于解决带权重有向图或无向图最短路径问题的算法。该算法由荷兰计算机科学家艾兹赫尔·狄克斯特拉在1956年发明,是一种广泛应用于网络路由和其他领域的算法。 在 2001 年的一次采访中,Dijkstra 博士透露

    2024年02月03日
    浏览(48)
  • 最短路径 matlab 动态规划

    数模培训,遇到了上个暑假没有解决的动态规划,唉,看来出来混迟早得还: 如图,给定一个线路网络,两点之间连线上的数字表示两点之间的距离(或费用),试求一条由A到F的铺管线路,使总距离为最短(或总费用最少)。 matlab代码模板如下: 该模板可以适用于无约束

    2024年02月12日
    浏览(36)
  • 动态规划求最短路径(matlab代码)

    此题目来源于算法分析与设计课程中,老师给的一个练习题。 设计一个动态规划算法求解下述多段图问题,计算从第一段源点(示例图中节点0)到最后一段目标节点(示例图中节点15)的最短路径: 关于动态规划的思想,b站上有位老师讲得比较清晰易懂(链接视频)。本解

    2024年02月04日
    浏览(34)
  • 简短通俗理解动态规划算法--最短路径问题

    问题:从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径——最短路径。在博客动态规划算法中介绍了动态规划的基本思想已经建立动态规划模型的步骤,下面将其中的方法分析最短路径问题。 最短路径有一个重要特性: 如果由起点A经

    2024年02月08日
    浏览(49)
  • 算法:动态规划---斐波那契和最短路径

    从本篇开始总结的是动态规划的一些内容,动态规划是算法中非常重要的一个版块,因此也是学习算法中的一个重点,在学习动态规划前应当要把动态规划的基础知识学习一下 动态规划既然是一个新的算法,这个名字也是新名字,那么就要首先明确这个算法的名字代表什么含

    2024年01月25日
    浏览(57)
  • Python 动态规划 实现机器人躲避障碍物获取最短路径

    要设计一种算法来寻找机器人从左上角移动到右下角的路径,可以使用动态规划来解决这个问题。下面是一种可能的算法: 创建一个处理机器人运动的函数 find_path ,函数接受一个矩阵 grid 作为参数,用于表示机器人移动的网格环境,该矩阵一个由 0 和 1 组成的二位列表,其

    2024年04月09日
    浏览(47)
  • 【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

    视频算法专题 动态规划汇总 广度优先搜索 状态压缩 存在一个由 n 个节点组成的无向连通图,图中的节点按从 0 到 n - 1 编号。 给你一个数组 graph 表示这个图。其中,graph[i] 是一个列表,由所有与节点 i 直接相连的节点组成。 返回能够访问所有节点的最短路径的长度。你可

    2024年01月23日
    浏览(41)
  • AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维

    我写了好多注释,一看就能看懂,这个题目我想了6,7个小时,一开始忽略了船的位置和要把船安置的位置一致的情况,补上就对了。

    2024年02月14日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包