资源描述：
《中国邮递员问题matlab.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、%中国邮递员问题：%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:mf
2、ori=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
3、(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);ifi
4、sempty(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);%主函数程序,此处将每个步骤用s
5、witch命令进行控制调用步骤函数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,
6、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,stepnu
7、m]=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
8、);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(
