2022年最小生成树最短路径算法定义 .pdf

《2022年最小生成树最短路径算法定义 .pdf》由会员分享，可在线阅读，更多相关《2022年最小生成树最短路径算法定义 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、假设图G权的邻接矩阵为0A，nnnnnnaaaaaaaaaA2122221112110来存放各边长度，其中：0iiani,2,1；ijaji,之间没有边，在程序中以各边都不可能达到的充分大的数代替；ijijwaijw是ji,之间边的长度，nji,2,1,。对于无向图，0A是对称矩阵，jiijaa。Floyd 算法的基本思想是：递推产生一个矩阵序列nkAAAA,10，其中),(jiAk表示从顶点iv到顶点jv的路径上所经过的顶点序号不大于k的最短路径长度。计算时用迭代公式：),(),(),(min(),(111jkAkiAjiAjiAkkkkk是迭代次数，nkji,2,1,。最后，当nk时，nA

2、即是各顶点之间的最短通路值。例10 用 Floyd算法求解例 1。矩阵 path 用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd 算法的 Matlab程序如下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);b=a+a;path=zeros(length(b);for k=1:6 for i=1:6 for j=1

3、:6 if b(i,j)b(i,k)+b(k,j)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -b(i,j)=b(i,k)+b(k,j);path(i,j)=k;end end end end b,path Floyd 最短路算法的MATLAB程序%floyd.m%采用 floyd 算法计算图a中每对顶点最短路%d 是矩离矩阵%r 是路由矩阵function d,r=floyd(a)n=size(a,1);d=a;for i=1:n for j=1:n r(i,j)=j;end end r for k=1:n for i=1:n for j=1:n if d(i,k

4、)+d(k,j)d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k)end end end k d r end 两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数)(ew直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点00,vu间的具最小名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -权的轨。这条轨叫做00,vu间

5、的最短路，它的权叫做00,vu间的距离，亦记作),(00vud。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距0u从近到远为顺序，依次求得0u到G的各顶点的最短路和距离，直至0v（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。(i)令0)(0ul，对0uv，令)(vl，00uS，0i。(ii)对每个iSv（iiSVS），用)()(),(minuvwulvliSu代替)(vl。计算)(minvliSv，把达到这个最小值的一个顶点记为1iu，令11iiiuSS。(iii).若1|Vi，停止；若1|Vi，用1i代替i，转

6、(ii)。算法结束时，从0u到各顶点v的距离由v的最后一次的标号)(vl给出。在v进入iS之前的标号)(vl叫 T 标号，v进入iS时的标号)(vl叫 P 标号。算法就是不断修改各项点的T标号，直至获得P 标号。若在算法运行过程中，将每一顶点获得P 标号所由来的边在图上标明，则算法结束时，0u至各项点的最短路也在图上标示出来了。例 9 某公司在六个城市621,ccc中有分公司，从ic到jc的直接航程票价记在下述矩阵的),(ji位置上。（表示无直接航路），请帮助该公司设计一张城市1c到其它城市间的票价最便宜的路线图。0552525105501020252510010204020100152520

7、15050102540500用矩阵nna（n为顶点个数）存放各边权的邻接矩阵，行向量pb、1index、2index、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量顶点未标号当第顶点已标号当第iiipb01)(；)(2iindex存放始点到第i点最短通路中第i顶点前一顶点的序号；名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -)(id存放由始点到第i点最短通路的值。求第一个城市到其它城市的最短路径的Matlab 程序如下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),

8、15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);a=a+a;pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1);end index2(temp)=index;endd,index1,index2 4.2.1prim 算法构造最小生成树设置两个集合P和Q,其中P用

9、于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为1vP（假设构造最小生成树时，从顶点1v出发），集合Q的初值为Q。prim 算法的思想是，从所有Pp，PVv的边中，选取具有最小权值的边pv，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到VP时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。prim 算法如下：（i）1vP，Q；名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -（ii）while VP,m i n(PVvPpwpvpvvPP pvQQend 例 11 用 prim 算法求右图的最小生成树。我们用nr

10、esult3的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:);d=min(temp);jb,kb=

11、find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;end result 4.2.1Kruskal 算法构造最小生成树科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下:(i)选)(1GEe，使得min)(1ew。(ii)若ieee,21已选好，则从,)(21ieeeGE中选取1ie，使得,121iieeeeG中无圈，且min)(1iew。(iii)直到选得1e为止。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 10 页 -例 12 用 Kruskal 算

12、法构造例3 的最小生成树。我们用nindex2存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号u改记为此边的另一序号v，同时把后面边中所有序号为u的改记为v。此方法的几何意义是：将序号u的这个顶点收缩到v顶点，u顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。Matlab 程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;i,j=fi

13、nd(a=0)&(a=M);b=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;while length(result)v2 index(find(index=v1)=v2;else index(find(index=v2)=v1;end data(:,flag)=;index(:,flag)=;end result 一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就

14、是在一个赋权完全图中，找出一个有最小权的Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。一个可行的办法是首先求一个Hamilton 圈C，然后适当修改C以得到具有较小权的另一个 Hamilton 圈。修改的方法叫做改良圈算法。设初始圈121vvvvCn。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 10 页 -（i）对于nji11，构造新的Hamilton 圈:12112121vvvvvvvvvvvCnjjijjjiij,它 是 由C中 删 去 边1iivv和1jjvv，

15、添 加 边jivv和11jivv而 得 到 的。若)()()()(1111jjiijijivvwvvwvvwvvw，则以ijC代替C，ijC叫做C的改良圈。（ii）转（i），直至无法改进，停止。用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。这个算法的优劣程度有时能用Kruskal 算法加以说明。假设C是G中的最优圈。则对于任何顶点v，vC是在vG中的 Hamilton 轨，因而也是vG的生成树。由此推知：若T是vG中的最优树，同时e和f是和v关联的两条边，并使得)()(fwew尽可能小，则)()()(fwewTw

16、将是)(Cw的一个下界。这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不利了。例 13 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：L M N Pa Pe T L 56 35 21 51 60 M 56 21 57 78 70 N 35 21 36 68 68 Pa 21 57 36 51 61 Pe 51 78 68 51 13 T 60 70 68 61 13 解：编写程序如

17、下：clc,clear a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a(6,:)=0;a=a+a;c1=5 1:4 6;L=length(c1);flag=1;while flag0 flag=0;for m=1:L-3 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -for n=m+2:L-1 if a(c1(m)

18、,c1(n)+a(c1(m+1),c1(n+1)0 flag=0;for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1).a(c1(m),c1(m+1)+a(c1(n),c1(n+1)flag=1;c1(m+1:n)=c1(n:-1:m+1);end end end end sum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);end if sum1sum sum=sum1;circle=c1;end circle,sum 已知非线性整数规划为：5432125242322212328243Ma

19、x xxxxxxxxxxz名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 10 页 -s.t.200520062800622400)5,1(9905433215432154321xxxxxxxxxxxxxxxxixi对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算10510)100(个点，其计算量非常之大。然而应用蒙特卡洛去随机计算610个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？下面就分析随机取样采集610个点计算时，应用概率理论来估计一下可信度。不失一般性，假定一个整数规划的最优点不是孤立的奇点。假设目标函数落在高值区的概率分别为0.01，0.000

20、01，则当计算610个点后，有任一个点能落在高值区的概率分别为多位）100(9999.099.011000000，999954602.099999.011000000。解（i）首先编写M 文件 mente.m 定义目标函数f 和约束向量函数g，程序如下：function f,g=mengte(x);f=x(1)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)-8*x(1)-2*x(2)-3*x(3).-x(4)-2*x(5);g(1)=sum(x)-400;g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;g(3)=2*x(1)+x(2)+6*x(3)

21、-200;g(4)=x(3)+x(4)+5*x(5)-200;（ii）编写如下程序求问题的解：rand(state,sum(clock);p0=0;tic for i=1:105 x=99*rand(5,1);x1=floor(x);x2=ceil(x);f,g=mengte(x1);if sum(g=0)=4 if p0=f x0=x1;p0=f;end end f,g=mengte(x2);名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -if sum(g=0)=4 if p0=f x0=x2;p0=f;end end end x0,p0toc 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -