数学建模中,给出非常多的节点,求这些节点的最短路径（类似一条线的路径）,应该用什么算法好?老师说不要用蚁群算法,遗传算法之类太悬的算法
2人问答
问题描述：
数学建模中,给出非常多的节点,求这些节点的最短路径（类似一条线的路径）,应该用什么算法好?
老师说不要用蚁群算法,遗传算法之类太悬的算法
郭盛回答：
下面是我自己编写的一段代码,用来求过包含两千多个点的最短路,速度很快,比遗传、蚁群快而且最短路更短.你可以试试看,有问题再问我.
function[S,len]=short(P)
%此程序用来求相同类型点间的最短路
%P表示某一类型的点的坐标矩阵
%p是最短路径
%d是路径权值和
%建立权值矩阵
n=length(P);%求该类型点的数量
W=zeros(n,n);
fori=1:n%计算权值并填充权值矩阵,由于各点联通,此权值矩阵就是该图的最短路矩阵
forj=(i+1):n
W(i,j)=sqrt((P(i,1)-P(j,1))^2+(P(i,2)-P(j,2))^2);
end
end
fori=2:n
forj=1:(i-1)
W(i,j)=W(j,i);
end
end
%求通过所有点的最短路
%先求从i点至j点,必须通过指定其他n-2个点的最短路,选出其中的的最短路
S=zeros(1,n);
S(1)=1;%先插入1,2点,以此为基准,每次插进一个新点
S(2)=2;
d1=2*W(1,2);
fori=3:n%新加入的点的标号
d1i=zeros(1,i);%插入第i个点,有i中可能的距离,其中最小值将为该轮的d1
forj=1:i%新加入点的位置,插入第i个点是有i个空位可供选择
ifj==1%在第一个空位插入
d1i(j)=d1+W(i,S(1))+W(i,S(i-1))-W(S(1),S(i-1));%插入点在首端时,距离为原距离与第i点与上一次插入后的第1位置的点之间距离之和
end
ifj>1&j
数学推荐
数学推荐
最新更新
精品分类
优秀数学推荐
热门数学
邮箱： 