《最优航线问题》由会员分享，可在线阅读，更多相关《最优航线问题（4页珍藏版）》请在装配图网上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流最优航线问题.精品文档.北京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的航线距离如下表： LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113由上述交通网络的数据确定最小生成树。设初始圈。（i）对于，构造新的Hamilton圈:它是由中删去边和，添加边和而得到的。若，则以代替，叫做的改良圈。（ii）转（i），直至无法改进，停止。模型建立设置两个集合和,其中用于存放的最小生成树中的顶点，集合存放的最小生成
2、树中的边。令集合的初值为（假设构造最小生成树时，从顶点出发），集合的初值为。从所有，的边中，选取具有最小权值的边，将顶点加入集合中，将边加入集合中，如此不断重复，直到时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边。用prim算法求上图的最小生成树。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下：clc,cleara(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;
3、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 for n=m+2:L-1 if a(c1(m),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 endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endif sum1sum sum=sum1; circle=c1;endcircle,sumcircle = 5 6 2 3 1 4sum = 160结果北京东京墨西哥城纽约伦敦巴黎
最优航线问题
