中国邮递员问题matlab

%中国邮递员问题：%step1；%求出奇点之间的距离；%求各个点之间的最短距离；%floyd算法；clearall;clc;A=zeros(9);A(1,2)=3;A(1,4)=1;A(2,4)=7;A(2,5)=4;A(2,6)=9;A(2,3)=2;A(3,6)=2A(4,7)=2;A(4,8)=3;A(4,5)=5;A(5,6)=8;A(6,9)=1;A(6,8)=6;A(7,8)=2;A(8,9)=2;c=A+A';c(find(c==0))=inf;m=length(c);Path=zeros(m);fork=1:mfori=1:mforj=1:mifc(i,j)c(i,k)+c(k,j)c(i,j)=c(i,k)+c(k,j);Path(i,j)=k;endendendendc,Pathh1=c(2,4);h2=c(2,6);h3=c(2,5);h4=c(4,6);h5=c(4,5);h6=c(6,5);h=[h1,h2,h3,h4,h5,h6]%step2;%找出以奇点为顶点的完全图的最优匹配；%算法函数Hung_Al.mfunction[Matching,Cost]=Hung_Al(Matrix)Matching=zeros(size(Matrix));%找出每行和每列相邻的点数num_y=sum(~isinf(Matrix),1);num_x=sum(~isinf(Matrix),2);%找出每行和每列的孤立点数x_con=find(num_x~=0);y_con=find(num_y~=0);%将矩阵压缩、重组P_size=max(length(x_con),length(y_con));P_cond=zeros(P_size);P_cond(1:length(x_con),1:length(y_con))=Matrix(x_con,y_con);ifisempty(P_cond)Cost=0;returnend%确保存在完美匹配，计算矩阵边集Edge=P_cond;Edge(P_cond~=Inf)=0;cnum=min_line_cover(Edge);Pmax=max(max(P_cond(P_cond~=Inf)));P_size=length(P_cond)+cnum;P_cond=ones(P_size)*Pmax;P_cond(1:length(x_con),1:length(y_con))=Matrix(x_con,y_con);%主函数程序,此处将每个步骤用switch命令进行控制调用步骤函数exit_flag=1;stepnum=1;whileexit_flagswitchstepnumcase1[P_cond,stepnum]=step1(P_cond);case2[r_cov,c_cov,M,stepnum]=step2(P_cond);case3[c_cov,stepnum]=step3(M,P_size);case4[M,r_cov,c_cov,Z_r,Z_c,stepnum]=step4(P_cond,r_cov,c_cov,M);case5[M,r_cov,c_cov,stepnum]=step5(M,Z_r,Z_c,r_cov,c_cov);case6[P_cond,stepnum]=step6(P_cond,r_cov,c_cov);case7exit_flag=0;endendMatching(x_con,y_con)=M(1:length(x_con),1:length(y_con));Cost=sum(sum(Matrix(Matching==1)));%下面是6个步骤函数step1~step6%步骤1：找到包含0最多的行，从该行减去最小值function[P_cond,stepnum]=step1(P_cond)P_size=length(P_cond);forii=1:P_sizermin=min(P_cond(ii,:));P_cond(ii,:)=P_cond(ii,:)-rmin;endstepnum=2;%步骤2：在P-cond中找一个0，并找出一个以该数0为星型的覆盖function[r_cov,c_cov,M,stepnum]=step2(P_cond)%定义变量r-cov，c-cov分别表示行或列是否被覆盖P_size=length(P_cond);r_cov=zeros(P_size,1);c_cov=zeros(P_size,1);M=zeros(P_size);forii=1:P_sizeforjj=1:P_sizeifP_cond(ii,jj)==0&&r_cov(ii)==0&&c_cov(jj)==0M(ii,jj)=1;r_cov(ii)=1;c_cov(jj)=1;endendend%重初始化变量r_cov=zeros(P_size,1);c_cov=zeros(P_size,1);stepnum=3;%步骤3：每列都用一个0构成的星型覆盖，如果每列都存在这样的覆盖，则M为最大匹配function[c_cov,stepnum]=step3(M,P_size)c_cov=sum(M,1);ifsum(c_cov)==P_sizestepnum=7;elsestepnum=4;end%步骤4：找一个未被覆盖的0且从这出发点搜寻星型0覆盖。如果不存在，转步骤5，否%则转步骤6function[M,r_cov,c_cov,Z_r,Z_c,stepnum]=step4(P_cond,r_cov,c_cov,M)P_size=length(P_cond);zflag=1;whilezflagrow=0;col=0;exit_flag=1;ii=1;jj=1;whileexit_flagifP_cond(ii,jj)==0&&r_cov(ii)==0&&c_cov(jj)==0row=ii;col=jj;exit_flag=0;endjj=jj+1;ifjjP_size;jj=1;ii=ii+1;endifiiP_size;exit_flag=0;endendifrow==0stepnum=6;zflag=0;Z_r=0;Z_c=0;elseM(row,col)=2;ifsum(find(M(row,:)==1))~=0r_cov(row)=1;zcol=find(M(row,:)==1);c_cov(zcol)=0;elsestepnum=5;zflag=0;Z_r=row;Z_c=col;endendend%步骤5：function[M,r_cov,c_cov,stepnum]=step5(M,Z_r,Z_c,r_cov,c_cov)zflag=1;ii=1;whilezflagrindex=find(M(:,Z_c(ii))==1);ifrindex0ii=ii+1;Z_r(ii,1)=rindex;Z_c(ii,1)=Z_c(ii-1);elsezflag=0;endifzflag==1;cindex=find(M(Z_r(ii),:)==2);ii=ii+1;Z_r(ii,1)=Z_r(ii-1);Z_c(ii,1)=cindex;endendforii=1:length(Z_r)ifM(Z_r(ii),Z_c(ii))==1M(Z_r(ii),Z_c(ii))=0;elseM(Z_r(ii),Z_c(ii))=1;endendr_cov=r_cov.*0;c_cov=c_cov.*0;M(M==2)=0;stepnum=3;%步骤6：function[P_cond,stepnum]=step6(P_cond,r_cov,c_cov)a=find(r_cov==0);b=find(c_cov==0);minval=min(min(P_cond(a,b)));P_cond(find(r_cov==1),:)=P_cond(find(r_cov==1),:)+minval;P_cond(:,find(c_cov==0))=P_cond(:,find(c_cov==0))-minval;stepnum=4;functioncnum=min_line_cover(Edge)[r_cov,c_cov,M,stepnum]=step2(Edge);[c_cov,stepnum]=step3(M,length(Edge));[M,r_cov,c_cov,Z_r,Z_c,stepnum]=step4(Edge,r_cov,c_cov,M);cnum=length(Edge)-sum(r_cov)-sum(c_cov);%主程序；clc;clearall;a=zeros(4);a(1,2)=4;a(1,3)=4;a(1,4)=4;a(2,3)=5;a(2,4)=6a(3,4)=8;a=a+a';a(find(a==0))=inf;[M,cost]=Hung_Al(a)%step3;%用Fleury方法求出其欧拉回路即为所求的最佳邮差回路。%Fleury；