搜索
中国邮递员问题的matlabchengxuclear;clc;M=inf;a(1,1)=0;a(1,36)=10.3;a(1,37)=5.9;a(1,38)=11.2;a(1,50)=6.0;a(2,2)=0;a(2,50)=9.2;a(2,5)=8.3;a(2,3)=4.8;a(3,3)=0;a(3,39)=8.2;a(3,38)=7.9;a(4,4)=0;a(4,39)=12.7;a(4,8)=20.4;a(5,5)=0;a(5,6)=9.7;a(5,39)=11.3;a(5,48)=11.4;a(6,6)=0;a(6,7)=7.3;a(6,47)=11.8;a(6,48)=9.5;a(7,7)=0;a(7,47)=14.5;a(7,40)=7.2;a(7,39)=15.1;a(8,8)=0;a(8,40)=8.0;a(9,9)=0;a(9,40)=7.8;a(9,41)=5.6;a(10,10)=0;a(10,41)=10.8;a(11,11)=0;a(11,42)=6.8;a(11,45)=13.2;a(11,40)=14.2;a(12,12)=0;a(12,43)=10.2;a(12,42)=7.8;a(12,41)=12.2;a(13,13)=0;a(13,45)=9.8;a(13,44)=16.4;a(13,42)=8.6;a(13,14)=8.6;a(14,14)=0;a(14,43)=9.9;a(14,15)=15.0;a(15,15)=0;a(15,44)=8.8;a(16,16)=0;a(16,17)=6.8;a(16,44)=11.8;a(17,17)=0;a(17,22)=6.7;a(17,46)=9.8;a(18,18)=0;a(18,46)=9.2;a(18,45)=8.2;a(18,44)=8.2;a(19,19)=0;a(19,20)=9.3;a(19,45)=8.1;a(19,47)=7.2;a(20,20)=0;a(20,21)=7.9;a(20,25)=6.5;a(20,47)=5.5;a(21,21)=0;a(21,23)=9.1;a(21,25)=7.8;a(21,46)=4.1;a(22,22)=0;a(22,23)=10.0;a(22,46)=10.1;a(23,23)=0;a(23,24)=8.9;a(23,49)=7.9;a(24,24)=0;a(24,27)=18.8;a(24,49)=13.2;a(25,25)=0;a(25,49)=8.8;a(25,48)=12.0;a(26,26)=0;a(26,27)=7.8;a(26,49)=10.5;a(26,51)=10.5;a(27,27)=0;a(27,28)=7.9;a(28,28)=0;a(28,52)=8.3;a(28,51)=12.1;a(29,29)=0;a(29,52)=7.2;a(29,51)=15.2;a(29,53)=7.9;a(30,30)=0;a(30,32)=10.3;a(30,52)=7.7;a(31,31)=0;a(31,33)=7.3;a(31,32)=8.1;a(31,53)=9.2;a(32,32)=0;a(32,33)=19;a(32,35)=14.9;a(33,33)=0;a(33,35)=20.3;a(33,36)=7.4;a(34,34)=0;a(34,35)=8.2;a(34,36)=11.5;a(34,37)=17.6;a(35,35)=0;a(36,36)=0;a(36,53)=8.8;a(36,37)=12.2;a(37,37)=0;a(37,38)=11.0;a(38,38)=0;a(38,50)=11.5;a(39,39)=0;a(41,41)=0;a(42,42)=0;a(43,43)=0;a(44,44)=0;a(44,45)=15.8;a(45,45)=0;a(46,46)=0;a(47,47)=0;a(48,48)=0;a(48,49)=14.2;a(48,50)=19.8;a(49,49)=0;a(50,50)=0;a(50,53)=12.9;a(50,51)=10.1;a(51,51)=0;a(52,52)=0;a(53,53)=0;%用1、2、3……35表示35个村：用36、37……53表示各乡镇。其中50表示的是县政府。b=a+a';b(find(b==0))=M;fori=1:53b(i,i)=0;end[mn]=size(b);k=1;fori=1:mforj=1:nif(b(i,j)==0)||(b(i,j)==inf)elsex1(k)=i;y(k)=j;z(k)=b(i,j);k=k+1;endendendQ=[x1;y;z]';k=0;d=zeros(1,n);fori=1:mforj=1:nif(b(i,j)==0)||(b(i,j)==inf)elsed(i)=d(i)+1;x2(i)=i;endendendk=1;t=mod(d,2);fori=1:mift(i)==1x3(k)=i;k=k+1;endend[mn]=size(x3);fori=1:nforj=1:nE(i,j)=b(x3(i),x3(j));endendk=1;[D,path]=floyd(b);fori=1:nforj=1:nifi==jelse[L,R]=router(D,path,x3(i),x3(j));x4(k)=x3(i);y4(k)=x3(j);z41(k)=max(L(:));z4(k)=150-z41(k);k=k+1;endendendY1=[x4;y4;z41]';Y=[x4;y4;z4]';nMM=grMaxMatch(Y);fori=1:13A(i,:)=Y1(nMM(i),:);endfori=1:13j=1;k=2;disp('需要加的边为：')[l,r]=router(D,path,A(i,j),A(i,k));rlende=hujuzhen(b);f=[234.8;104110.8;11426.8;124310.2;43149.9;18448.2;19458.1;22176.7;244913.2;494814.2;264910.5;27287.9;29527.2;31357.3;35367.4;34358.2];e=[e;f];E=[e(:,1)e(:,2)];[eu,cEu]=grIsEulerian(E);ifeu==1disp('找到了最短路');[mn]=size(cEu);shortrouter=zeros(m,3);fori=1:mshortrouter(i,:)=e(cEu(i),:);juli=sum(shortrouter(:,3));endjuli[m,n]=size(shortrouter);t=0;fori=2:mifshortrouter(i,1)==shortrouter(i-1,2)elset=shortrouter(i,1);shortrouter(i,1)=shortrouter(i,2);shortrouter(i,2)=t;endendzx=[shortrouter(1,1)shortrouter(:,2)']';[m,n]=size(zx);n=sqrt(m);n=floor(n);t=[0];k=1;g=1;l=n;j=2;whilej=m-1fori=k:lx1=g;t=[tx1];j=j+1;ifjm-1breakendendg=g+1;k=l;l=l+n-1;endt=[tg]';v=[n/2];fori=1:nx=1:n;v=[vx];endj=m-n*n-1;ifj0x=1:j-1;endvl=[vxn/2]';Q=[tvlzx];c1=[1:107]';c2=[2:108]';c3=shortrouter(:,3);C=[c1c2c3];grPlot(Q,C,'g','%d','');title('\bf最短路径为：');elsedisp('没有最短路');endloaddatav=[x-y];grPlot(v,shortrouter,'g','%d','');title('\bf最短路径为：');邻接矩阵的弧表示：functionA=hujuzhen(e)[mn]=size(e);k=1;fori=1:mforj=i:nif(e(i,j)==0)||(e(i,j)==inf)elsex(k)=i;y(k)=j;z(k)=e(i,j);k=k+1;endendendA=[x;y;z]';弧表示话为邻接矩阵a=[11234455];b=[23423534];w=[11111111];n=5;m=5;k=length(a);x1=zeros(m,n);fori=1:kx1(a(i),b(i))=w(i);end