北京（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 由上述交通网络的数据确定最小生成树。 设初始圈C?v1v2?vnv1。
（i）对于1?i?1?j?n，构造新的Hamilton圈: Cij?v1v2?vivjvj?1vj?2?vi?1vj?1vj?2?vnv1,
它是由C中删去边vivi?1和vjvj?1，添加边vivj和vi?1vj?1而得到的。若
w(vivj)?w(vi?1vj?1)?w(vivi?1)?w(vjvj?1)，则以Cij代替C，Cij叫做C的改良圈。
（ii）转（i），直至无法改进，停止。
clb借鉴 1
模型建立
设置两个集合P和Q,其中P用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P?{v1}（假设构造最小生成树时，从顶点v1出发），集合Q的初值为Q??。
从所有p?P，v?V?P的边中，选取具有最小权值的边pv，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到P?V时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。
用prim算法求上图的最小生成树。
我们用result3?n的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下： 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 flag>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)) 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)); clb借鉴 2 end circle=c1; sum=sum1; c1=[5 6 1:4]; flag=1; while flag>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 sum1 circle,sum circle = 5 6 2 3 1 4 sum = 160 结果 北京?东京?墨西哥城?纽约?伦敦?巴黎 clb借鉴 3 clb借鉴 4
最优航线问题(稻谷文书)
