中国邮递员问题matlab.doc

%中国邮递员问题： %step1； %求出奇点之间的距离； %求各个点之间的最短距离； %floyd算法； clear all; 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)=2 A(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); for k=1:m for i=1:m for j=1:m if c(i,j)c(i,k)+c(k,j) c(i,j)=c(i,k)+c(k,j); Path(i,j)=k; end end end end c, Path h1=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.m function [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); if isempty(P_cond) Cost = 0; return end % 确保存在完美匹配，计算矩阵边集 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; while exit_flag switch stepnum case 1 [P_cond,stepnum] = step1(P_cond); case 2 [r_cov,c_cov,M,stepnum] = step2(P_cond); case 3 [c_cov,stepnum] = step3(M,P_size); case 4 [M,r_cov,c_cov,Z_r,Z_c,stepnum] = step4(P_cond,r_cov,c_cov,M); case 5 [M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov); case 6 [P_cond,stepnum] = step6(P_cond,r_cov,c_cov); case 7 exit_flag = 0; end end Matching(x_con,y_con) = M(1:length(x_con),1:length(y_con)); Cost = sum(sum(Matrix(Matching==1))); %下面是6个步骤函数step1~step6 %步骤1：找