简短通俗理解动态规划算法--最短路径问题

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

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

最短路径有一个重要特性:
如果由起点A经过P点和H点而到达终点G是一条最短路线,则由点P出发经过H点到达终点G的这条子路线,对于从点P出发到达终点的所有可能选择的不同路线来说,必定也是最短路线。如下图:
简短通俗理解动态规划算法--最短路径问题
例题分析:求从A到G的最短路径。
简短通俗理解动态规划算法--最短路径问题
如上图,采用反向阶段编号,采用反向递推,状态为各阶段初始位置,目标函数:
简短通俗理解动态规划算法--最短路径问题
第一阶段:k = 1,s1有F1、F2两种可能状态,最优决策表如下
目标函数:

简短通俗理解动态规划算法--最短路径问题
简短通俗理解动态规划算法--最短路径问题
第二阶段:k = 2,s2有E1、E2、E3三种可能状态,最优决策表如下
目标函数:

简短通俗理解动态规划算法--最短路径问题
简短通俗理解动态规划算法--最短路径问题
第三阶段:k = 3,s3有D1、D2、D3三种可能状态,最优决策表如下
目标函数:

简短通俗理解动态规划算法--最短路径问题
简短通俗理解动态规划算法--最短路径问题
第四阶段:k = 4,s4有C1、C2、C3、C4四种可能状态,最优决策表如下
目标函数:

简短通俗理解动态规划算法--最短路径问题
简短通俗理解动态规划算法--最短路径问题
第五阶段:k = 5,s5有B1、B2两种可能状态,最优决策表如下
目标函数:

简短通俗理解动态规划算法--最短路径问题
简短通俗理解动态规划算法--最短路径问题
第六阶段:k = 6,s6有一种状态,最优决策表如下
目标函数:

简短通俗理解动态规划算法--最短路径问题
简短通俗理解动态规划算法--最短路径问题
最短路径长度:18,最优策略:
简短通俗理解动态规划算法--最短路径问题
上面只是提供一种求解最短路径问题的方法,后续我还会编程实现最短路径问题的求解。文章来源地址https://www.toymoban.com/news/detail-480425.html

到了这里,关于简短通俗理解动态规划算法--最短路径问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索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日
    浏览(38)
  • 动态规划:理解并掌握算法的艺术

    动态规划(Dynamic Programming,DP)是一种算法设计技术,它将一个复杂问题分解成更小的子问题,并将这些子问题的解存储起来,以避免重复计算。这种方法能够有效地解决各种优化问题,特别是在计算机科学、运筹学、经济学和工程学等领域。 在深入探讨动态规划之前,我们

    2024年02月03日
    浏览(35)
  • 算法通关第十九关-青铜挑战理解动态规划

    大家好我是苏麟 , 今天聊聊动态规划 . 动态规划是最热门、最重要的算法思想之一,在面试中大量出现,而且题目整体都偏难一些对于大部人来说,最大的问题是不知道动态规划到底是怎么回事。很多人看教程等,都被里面的状态子问题、状态转移方程等等劝退了。 其实,所

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

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

    2024年02月12日
    浏览(29)
  • 【算法专题】动态规划之路径问题

    题目链接 - Leetcode -62.不同路径 Leetcode -62.不同路径 题目:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示

    2024年01月24日
    浏览(47)
  • 【算法-动态规划】0-1 背包问题

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(43)
  • 算法沉淀 —— 动态规划篇(路径问题)

    几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此 1.、状态表示:通常状态表示分为基本分为以下两种,其中更是以第一种为甚。 以i为结尾 ,dp[i] 表示什么,通常为代求问题(具体依题目而定) 以i为开始 ,dp[i]表示什么,通常为代求问题(具

    2024年04月17日
    浏览(42)
  • 【算法 - 动态规划】找零钱问题Ⅲ

    在前面的动态规划系列文章中,关于如何对递归进行分析的四种基本模型都介绍完了,再来回顾一下: 从左到右模型 : arr[index ...] 从 index 之前的不用考虑, 只考虑后面的该如何选择 。 范围尝试模型 :思考 [L ,R] 两端,即 开头和结尾 处分别该如何取舍。 样本对应模型 :

    2024年04月09日
    浏览(41)
  • 通俗易懂 快速理解 JDK动态代理 和 cglib动态代理

    动态代理的实现方案有两种, JDK动态代理 和 CGLIB动态代理 ,区别在于JDK自带的动态代理,必须要有接口,而CGLIB动态代理有没有接口都可以。 JDK动态代理 :JDK原生的实现方式,需要被代理的目标类必须实现接口。因为这个技术要求 代理对象和目标对象实现同样的接口 (兄

    2024年02月08日
    浏览(47)
  • 【算法】动态规划(dp问题),持续更新

    介绍本篇之前,我想先用人话叙述一般解决动态规划问题的思路: 动态规划的问题,本身有许多产生结果的可能,需要在具体题目下得到满足某个条件的解。 如何得到呢? 我们就需要根据这个具体问题,建立一个状态表( dp 表 ),在这张 dp 表中的每一个位置的数据都有明

    2024年02月04日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包