中國郵遞員問題matlab

1、精選優(yōu)質(zhì)文檔-傾情為你奉上%中國郵遞員問題：%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)=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);for k=1:m for i=1:m f

2、or 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 endendc, 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;%找出以奇點為頂點的完全圖的最優(yōu)匹配；%算法函數(shù)Hung_Al.mfunction Matching,Cost = Hung_Al(Matrix) Matching = zeros(size(Matrix); % 找出每行和每列相鄰的點數(shù) nu

3、m_y = sum(isinf(Matrix),1); num_x = sum(isinf(Matrix),2); % 找出每行和每列的孤立點數(shù) 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% 確保

4、存在完美匹配，計算矩陣邊集 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);%主函數(shù)程序,此處將每個步驟用switch命令進行控制調(diào)用步驟函數(shù) exit_flag = 1; stepnum = 1; whil

5、e 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,stepn

6、um = step6(P_cond,r_cov,c_cov); case 7 exit_flag = 0; end endMatching(x_con,y_con) = M(1:length(x_con),1:length(y_con);Cost = sum(sum(Matrix(Matching=1);%下面是6個步驟函數(shù)step1step6%步驟1：找到包含0最多的行，從該行減去最小值function P_cond,stepnum = step1(P_cond) P_size = length(P_cond); for ii = 1:P_size rmin = min(P_cond(ii,

7、:); P_cond(ii,:) = P_cond(ii,:)-rmin; end stepnum = 2;%步驟2：在P-cond中找一個0，并找出一個以該數(shù)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_co

8、nd(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_c

9、ov) = P_size stepnum = 7; else stepnum = 4; end%步驟4：找一個未被覆蓋的0且從這出發(fā)點搜尋星型0覆蓋。如果不存在，轉(zhuǎn)步驟5，否%則轉(zhuǎn)步驟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;while zflag row = 0; col = 0; exit_flag = 1; ii = 1; jj = 1; while exit_flag if P_cond(ii,jj) = 0 &&a

10、mp; 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; zco

11、l = find(M(row,:)=1); c_cov(zcol) = 0; else stepnum = 5; zflag = 0; Z_r = row; Z_c = col; end endend%步驟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); e

12、lse 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：fu

13、nction 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 = le