最短路径 matlab 动态规划-Toy模板网

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

数模培训，遇到了上个暑假没有解决的动态规划，唉，看来出来混迟早得还：

如图，给定一个线路网络，两点之间连线上的数字表示两点之间的距离（或费用），试求一条由A到F的铺管线路，使总距离为最短（或总费用最少）。

matlab最短路径算法代码,matlab,matlab,动态规划,开发语言

matlab代码模板如下：

clc,clear
now=[3,5,4,0,0,0,0,0,0
    9,5,0,4,3,5,0,1,7
    1,5,0,8,4,6,4,4,2
    4,2,0,6,9,0,7,5,0
    1,0,0,2,0,0,0,0,0
    0,0,0,0,0,0,0,0,0];  %路程矩阵，第i行表示第i个阶段(最后一个阶段默认全为0)；n*m列，n个起点，m种不同走法，隔m个数开始下一个起点
h=6 ;        %阶段数
a=3   ;      %起点数
b=3;         %决策数(决策数一般等于起点数)
%%只需修改上面的代码，就可以嵌套进其他的最短路径求解%%


now(now==0)=inf;    %先把他写成全矩阵，没有路的用00补充，之后吧0转换成无穷大
road_sum=zeros(h,a*b);   %保存每个阶段的最短路程长

for i=h-1:-1:1      %不同阶段
    for n=1:a       %不同阶段下的几个不同起点
        for k=1:b   %不同起点下的几个不同决策
            road_sum(i,(n-1)*a+k)=now(i,(n-1)*a+k)+min(road_sum(i+1,(k-1)*a+1:k*a));   %当前路径加上上个阶段下的最短路径
        end
    end
end

road=[];                %用来保存选择的起点
for i=1:h-1
    if i==1
        start=find(road_sum(1,:)==min(road_sum(1,:)));       %找到起点之后的第一个点
    else
        start=find(road_sum(i,(start-1)*a+1:start*a)==min(road_sum(i,(start-1)*a+1:start*a))) ;      %找到起点之后的第一个点
    end
    if length(start)>0
        disp('注意该问题存在多条最优解，已自动帮您规划了一条路径')
        start=start(1);
    end
    road=[road,start] ;  %保存
end

disp(['最短路径和为：' num2str(min(road_sum(1,:)))])
disp('其中一条对应的路径选择为：从起点出发，')
for i=road
    disp(['选下一个阶段的起点' num2str(i) ','])
end

该模板可以适用于无约束的最短路径这一类问题文章来源地址https://www.toymoban.com/news/detail-523847.html

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