动态规划求最短路径(matlab代码)

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

此题目来源于算法分析与设计课程中,老师给的一个练习题。

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

简单说一下解题思路。从目的端(15节点)开始,往上走,到13、14节点那一层,记录下该层节点(即13、14)到下一层节点(即15)的最短路径值。以此类推,再往上走,同样记录下该层节点到下一层的最段路径,直到走到源端(即上图中的0)。如下图所示,记录下的最短路径值:
动态规划求最短路径(matlab代码)
由上图可知,通过手算,得到该图的最短路径值为18。当然此处数据量不算太大,手算当然可以,但是当数据量更大时就很费劲了。

这里给出该图的matlab求解程序。

此处对于原问题中,各个路径的值用cell数据结构来存储。cell数据结构还真挺好用的,我也是前段时间频繁接触它。本程序对cell的使用还比较浅。cell相当于一个容器,按本程序来理解,容器里装了一些对象,这里设置了6个对象,对应图的6层(不包含最后一层),这里将倒数第二层作为第1个对象。

为什么说cell好用,就是因为cell对于每个对象的大小没有统一的限制。这里每个对象就是一个矩阵,矩阵的大小根据本层节点数(作为行数)和下层节点数+1(作为列数)来决定,这里列数加1,是为了存最短路径。当某节点到下一层节点没有路径时,将其初始化为999(一个比较大的值)。

这里要注意cell结构中对象赋值、元素存取等,看得多了就理解了。

Path_w=cell(6);
Path_w{6}=[5,3,0];%第一层1个节点,所以1行,下一层2个节点,所以列数是2+1,最后一个用来存最短路径
Path_w{5}=[1,3,6,999,0;999,8,7,6,0];
Path_w{4}=[6,8,999,0;3,5,999,0;999,3,3,0;999,8,4,0];
Path_w{3}=[2,2,999,0;999,1,2,0;999,3,3,0];
Path_w{2}=[3,5,0;5,2,0;6,6,0];
Path_w{1}=[4,4;3,3];
%Not include last layer

flag=cell(6);%这是为了存储最终的最短路径都经过了哪些节点
flag{1}=[1,1];

for i=2:length(Path_w)
    if size(Path_w{i-1},1)==1%前一层的节点只有1个时。本题中未将最后一层节点放进来,所以按逻辑,此if应该不会进来。
        for m=1:size(Path_w{i},1)
            Path_w{i}(m,end)=Path_w{i}(m,1)+Path_w{i-1}(1,end);
        end          
    else
        for m=1:size(Path_w{i},1)%size(Path_w{i},1)表示第i个对象矩阵的行数 即第i层节点数
            current_min=99999;
            for n=1:size(Path_w{i},2)-1
                if Path_w{i}(m,n)+Path_w{i-1}(n,end)<current_min
                    current_min=Path_w{i}(m,n)+Path_w{i-1}(n,end);
                    flag{i}(m,1)=n;
                end
            end
            Path_w{i}(m,end)=current_min;
        end
    end
end
disp("shortest path cost:");disp(Path_w{6}(1,end));
disp("从左到右每层选择的节点是:")
result=flag{length(flag)};
disp(result);
for i=length(flag)-1:-1:1
    result=flag{i}(result);
    disp(result);
end

得到结果如下:
动态规划求最短路径(matlab代码)
每层选择的节点如下:
动态规划求最短路径(matlab代码)
即选择节点为:0,1,4,7,11,14,15。文章来源地址https://www.toymoban.com/news/detail-444532.html

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

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

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

相关文章

  • 基于智能优化算法实现自动泊车的路径动态规划(Matlab代码实现)

    目录 💥1 概述 📚2 运行结果 🎉3 参考文献 👨‍💻4 Matlab代码 作为一种方便、快捷的交通工具,汽车已成为人们生活和工作的重要组成部分。随着汽车数量的逐年增加,有限的城市空间显得日趋拥挤,车辆平均分配到的停放空间也日趋缩小,车辆泊车入位困难问题在人们生

    2024年02月07日
    浏览(45)
  • 【配送路径规划】停靠点的NIA算法单卡车协同单无人机多客户外卖配送路径规划(目标函数:最短时间)【含Matlab源码 3987期】

    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划

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

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

    2024年02月12日
    浏览(34)
  • 【路径规划】基于matlab火鹰算法栅格地图机器人最短路径规划【含Matlab源码 3679期】

    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划

    2024年02月02日
    浏览(52)
  • 【路径规划】基于matlab帝企鹅算法栅格地图机器人最短路径规划【含Matlab源码 3630期】

    1 帝企鹅算法 帝企鹅优化(Emperor Penguin Optimizer,EPO)算法是Dhiman G和Kumar V于2018年提出的一种新型群智能算法,该算法具有参数少、收敛精度高等特点。帝企鹅从事各种活动,如狩猎、群体觅食,是群居性动物。每当恶劣的气候来临,它们会挤在一起防风御寒。帝企鹅在南极极端

    2024年02月03日
    浏览(47)
  • 【路径规划】鲸鱼算法栅格地图机器人最短路径规划【含Matlab源码 3613期】

    1 鲸鱼算法 一种元启发式优化算法,模拟座头鲸狩猎行为的元启发式优化算法。目前的工作与其他群优化算法相比的主要区别在于,采用随机或最佳搜索代理来模拟捕猎行为,并使用螺旋来模拟座头鲸的泡泡网攻击机制。该算法具有机制简单、参数少、寻优能力强等优点,在

    2024年02月04日
    浏览(55)
  • 【路径规划】自适应遗传算法机器人栅格地图最短路径规划【含Matlab源码 3570期】

    1 遗传算法 遗传算法是一种基于生物进化论模型的优化算法,通过模拟生物进化的过程,通过复制、交叉、突变等操作产生下一代的解,并逐步淘汰掉适应度函数值低的解,增加适应度函数值高的解。遗传算法可以用于解决各种优化问题,如函数优化、组合优化、机器学习等

    2024年02月03日
    浏览(72)
  • 【路径规划】萤火虫算法栅格地图机器人最短路径规划【含Matlab源码 3662期】

    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划

    2024年02月20日
    浏览(98)
  • 【路径规划】(1) Dijkstra 算法求解最短路,附python完整代码

    好久不见,我又回来了, 这段时间把路径规划的一系列算法整理一下 ,感兴趣的点个关注。今天介绍一下机器人路径规划算法中最基础的 Dijkstra 算法,文末有 python 完整代码,那我们开始吧。 1959 年,荷兰计算机科学家 ·EdsgerWybe·Dijkstra 发表了论文《 A note on two problems in c

    2023年04月08日
    浏览(44)
  • 【路径规划】(2) A* 算法求解最短路,附python完整代码

    大家好,今天和各位分享一下机器人路径规划中非常经典的 A* 算法,感兴趣的点个关注,文末有 python 代码,那我么开始吧。 A* 算法是 1968 年 P.E.Hart[1]等人所提出的 在全局地图环境中所有已知情形下求解最短路径问题的方法,由于其简洁高效,容易实施 等 优点 而受到人们

    2024年02月03日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包