中国邮递员问题matlab

%中国邮递员问题： %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：找到包含0最多的行，从该行减去最小值 function [P_cond,stepnum] = step1(P_cond) P_size = length(P_cond); for ii = 1:P_size

rmin = min(P_cond(ii,:));

P_cond(ii,:) = P_cond(ii,:)-rmin; end

stepnum = 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); for ii = 1:P_size for jj = 1:P_size

if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0 M(ii,jj) = 1; r_cov(ii) = 1; c_cov(jj) = 1; end end end

% 重初始化变量

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); if sum(c_cov) == P_size stepnum = 7; else

stepnum = 4; end

%步骤4：找一个未被覆盖的0且从这出发点搜寻星型0覆盖。如果不存在，转步骤5，否%

则转步骤6

function [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; while zflag

row = 0; col = 0; exit_flag = 1; ii = 1; jj = 1; while exit_flag

if P_cond(ii,jj) == 0 && r_cov(ii) == 0 && c_cov(jj) == 0 row = ii; col = jj;

exit_flag = 0; end

jj = jj + 1;

if jj > P_size; jj = 1; ii = ii+1; end if ii > P_size; exit_flag = 0; end end

if row == 0

stepnum = 6; zflag = 0; Z_r = 0; Z_c = 0; else

M(row,col) = 2;

if sum(find(M(row,:)==1)) ~= 0 r_cov(row) = 1;

zcol = find(M(row,:)==1); c_cov(zcol) = 0; else

stepnum = 5; zflag = 0; Z_r = row; Z_c = col;

end end end

%步骤5：

function [M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov) zflag = 1; ii = 1;

while zflag

rindex = find(M(:,Z_c(ii))==1); if rindex > 0 ii = ii+1;

Z_r(ii,1) = rindex; Z_c(ii,1) = Z_c(ii-1); else

zflag = 0; end

if zflag == 1;

cindex = find(M(Z_r(ii),:)==2); ii = ii+1;

Z_r(ii,1) = Z_r(ii-1); Z_c(ii,1) = cindex; end end

for ii = 1:length(Z_r)

if M(Z_r(ii),Z_c(ii)) == 1 M(Z_r(ii),Z_c(ii)) = 0; else

M(Z_r(ii),Z_c(ii)) = 1; end end

r_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;

function cnum = 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;

clear all; a=zeros(4);

a(1,2)=4;a(1,3)=4;a(1,4)=4; a(2,3)=5;a(2,4)=6 a(3,4)=8; a=a+a';

a(find(a==0))=inf; [M,cost]=Hung_Al(a) %step3;

%用Fleury方法求出其欧拉回路即为所求的最佳邮差回路。 %Fleury；