1、精選優(yōu)質(zhì)文檔-傾情為你奉上作業(yè)解答練習(xí)題2 利用matlab編程FFD算法完成下題：設(shè)有6種物品，它們的體積分別為：60、45、35、20、20和20單位體積，箱子的容積為100個單位體積。解答一：function num,s = BinPackingFFD(w,capacity)%一維裝箱問題的FFD（降序首次適應(yīng)）算法求解:先將物體按長度從大到小排序,%然后按FF算法對物體裝箱%輸入?yún)?shù)w為物品體積，capacity為箱子容量%輸出參數(shù)num為所用箱子個數(shù)，s為元胞數(shù)組，表示裝箱方案，si為第i個箱子所裝%物品體積數(shù)組%例w = 60,45,35,20,20,20; capacity =

2、100;% num=3,s=1,3,2,4,5,6;w = sort(w,'descend');n = length(w);s = cell(1,n);bin = capacity * ones(1,n);num = 1;for i = 1:n for j = 1:num + 1 if w(i) < bin(j) bin(j) = bin(j) - w(i); sj = sj,i; if j = num + 1 num = num + 1; end break; end end ends = s(1:num);解答二：clear;clc;V=100;v=60 45 35

3、20 20 20;n=length(v);v=fliplr(sort(v);box_count=1;x=zeros(n,n);V_Left=100;for i=1:n if v(i)>=max(V_Left) box_count=box_count+1; x(i,box_count)=1; V_Left=V_Left V-v(i); else j=1; while(v(i)>V_Left(j) j=j+1; end x(i,j)=1; V_Left(j)=V_Left(j)-v(i); end temp=find(x(i,:)=1); fprintf('第%d個物品放在第%

4、d個容器n',i,temp)endoutput:第1個物品放在第1個容器第2個物品放在第2個容器第3個物品放在第1個容器第4個物品放在第2個容器第5個物品放在第2個容器第6個物品放在第3個容器解答三：function box_count=FFD(x)%降序首次適應(yīng)算法v=100;x=fliplr(sort(x);%v=input('請輸入箱子的容積:');n=length(x);I=ones(n);E=zeros(1,n);box=v*I;box_count=0;for i=1:n j=1; while(j<=box_count) if x(i)>box(j

5、) j=j+1; continue; else box(j)=box(j)-x(i); E(i)=j; break; end end if j>box_count box_count=box_count+1; box(box_count)=box(box_count)-x(i); E(i)=j; endenddisp(E);在命令窗口輸入：>> x=60,45,35,20,20,20;>> FFD(x) 1 2 1 2 2 3ans = 3練習(xí)題5 “超市大贏家”提供了50種商品作為獎品供中獎顧客選擇,車的容量為1000dm3 , 獎品i占用的空間為wi dm3

6、,價值為vi 元, 具體的數(shù)據(jù)如下:vi = 220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1wi = 80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50,

7、32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1。問如何裝車才能總價值最大。解答：clear;clc;v=220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77,

8、 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1; w=80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1;totalw=1000;limitw=1000;n=leng

9、th(w);for i=1:n f(1,i)=v(i)/w(i); f(2,i)=w(i); f(3,i)=i;endfor i=1:(n-1) for j=(i+1):n if f(1,i)<f(1,j) t=f(1,i); f(1,i)=f(1,j); f(1,j)=t; t=f(2,i); f(2,i)=f(2,j); f(2,j)=t; t=f(3,i); f(3,i)=f(3,j); f(3,j)=t; end endendtotalv=0;a=;for i=1:n if f(2,i)<=limitw a=a,f(3,i); %disp(f(3,i); limitw=li

10、mitw-f(2,i); totalv=totalv+f(1,i)*f(2,i); endendatotalvtotalw=totalw-limitw結(jié)果a = Columns 1 through 21 10 40 17 25 28 16 19 35 37 8 26 20 13 11 24 27 9 23 41 1 4 Columns 22 through 27 22 6 30 14 2 47totalv = 3103totalw = 1000練習(xí)題8 對最后一個求有向圈的示例用matlab程序?qū)崿F(xiàn)。解答：H= 0 1 0 0 0; 0 0 0 1 1; 1 1 1 0 0; 0 0 1 0

11、1; 0 1 0 0 0;n=size(H,1);%頂點個數(shù)p=zeros(1,n);%存儲搜索過的頂點X=zeros(n,n);%用來設(shè)置禁止矩陣，往回返的時候設(shè)置此路已被搜索k=1;p(1)=1;%第一個點作為初始點開始搜索while p(1)<=n %每個頂點都作為初始點搜索包含p(1)的有向圈， i=p(1)+1;%當(dāng)前點k往后搜索時都是從p(1)+1開始，從而也可以搜索下標(biāo)小于k的點while i<=n %還有后續(xù)點沒有搜索（這些點有可能比當(dāng)前點k小） if (H(p(k),i)=1)&(X(p(k),i)=0)&isempty(find(p=i)%滿足三

12、個條件 k=k+1;%搜索路徑上增加一個點 p(k)=i;%搜索路徑向前延伸一個點 else i=i+1;%當(dāng)前被搜索點不滿足條件，換下一個點 endendif i>n %k點往后的所有點都被搜索 if H(p(k),p(1)=1%有圈，每次搜索的都是包含初始點的圈 disp(p(1:k);%輸出圈 end %不管有沒有圈，此時k點要往回返 if k>1%路徑上不止出發(fā)點 for j=1:n X(p(k),j)=0;%取消以前的限制通行 end X(p(k-1),p(k)=1;%增加此路已搜索 p(k)=0;%撤銷路徑上的k點 k=k-1;%返回上一個點作為當(dāng)前點 else %返回

13、到出發(fā)點了 p(1)=p(1)+1; %換下一個出發(fā)點（初始點） end endend運(yùn)行結(jié)果：1 2 4 3 2 4 5 2 4 3 2 5 3練習(xí)題9 選址問題 現(xiàn)準(zhǔn)備在7個居民點中設(shè)置一銀行，路線與距離如下圖，問設(shè)在哪個點，可使最大服務(wù)距離最??？若設(shè)兩個點呢？解答：第一步：function D,R=floyd(A)%用floyd算法實現(xiàn)求任意兩點之間的最短路程?？梢杂胸?fù)權(quán)%參數(shù)D為連通圖的權(quán)矩陣 A=0 3 inf inf inf inf inf 3 0 2 inf inf 1.5 inf inf 2 0 6 inf 2.5 4 inf inf 6 0 inf inf 3 inf inf

14、 inf inf 0 1.5 inf inf 1.5 2.5 inf 1.5 0 1.8 inf inf 4 3 inf 1.8 0 ;D=A;n=length(D);for i=1:n for j=1:n R(i,j)=i;%賦路徑初值 endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j);%更新 D(i,j)，說明通過k的路程更短 R(i,j)=R(k,j);%更新R(i,j)，需要通過k end end end hl=0; for i=1:n if D(i,i)<0 h

15、l=1; break;%跳出內(nèi)層的for循環(huán) end end if(hl=1) fprintf('有負(fù)回路') break;%跳出最外層循環(huán) endendD 運(yùn)行結(jié)果：D= 0 3.0000 5.0000 9.3000 6.0000 4.5000 6.3000 3.0000 0 2.0000 6.3000 3.0000 1.5000 3.3000 5.0000 2.0000 0 6.0000 4.0000 2.5000 4.0000 9.3000 6.3000 6.0000 0 6.3000 4.8000 3.0000 6.0000 3.0000 4.0000 6.3000 0

16、 1.5000 3.3000 4.5000 1.5000 2.5000 4.8000 1.5000 0 1.80006.3000 3.3000 4.0000 3.0000 3.3000 1.8000 0第二步：對于第一問在矩陣D中每一個取大得到一列數(shù)，再在這列數(shù)中取小，m,n=size(D);p=;for i=1:m p(i)=max(D(i,:);end for i=1:m if p(i)=min(p) disp(i); end endmin(p)在頂點6建立銀行，最大服務(wù)距離最小，最小是4.8.第三步：對于第二問任取兩個點做集合，計算每個點到這個集合的最小值，再在這個最小值中取大，即在矩陣

17、D中任取兩行，對應(yīng)比較取小得一向量，將所有這樣的向量寫成行向量構(gòu)成一矩陣，然后用問題一的算法程序即可。a=0;b=;n=size(D,1);for i=1:(n-1) for j=(i+1):n a=a+1; for k=1:n sa=i j; b(a,k)=min(D(i,k),D(j,k); end endendm=size(b,1);p=;for i=1:m p(i)=max(b(i,:);end for i=1:m if p(i)=min(p) disp(si); end end min(p)結(jié)果，在頂點2,4或2,7點建立銀行都使得最大服務(wù)距離最小，最小值是3練習(xí)題10 貨物調(diào)運(yùn) 已

18、知該地區(qū)有生產(chǎn)該物資的企業(yè)三家，大小物資倉庫八個，國家級儲備庫兩個，其分布情況見下面的附件1。經(jīng)核算該物資的運(yùn)輸成本為高等級公路2元/公里百件，普通公路1.2元/公里百件，假設(shè)各企業(yè)、物資倉庫及國家級儲備庫之間的物資可以通過公路運(yùn)輸互相調(diào)運(yùn)，請給出各個倉庫應(yīng)該從哪個企業(yè)調(diào)運(yùn)。解答：首先建立各個交匯點的距離矩陣m。然后建立函數(shù)文件。%各倉庫到各企業(yè)的最小運(yùn)費(fèi)function min_spend(m)c=28,23,35,31,22,36,29,38; %倉庫cc=27,30; %國家儲存庫C=c,cc;g=8,15,11,27,7,10,17,14,28,16,18,25,6,5,39,35,1

19、3,40,4,29;%高級公路上的點n=length(g);A=zeros(42);for i=1:42 for j=1:42 if m(i,j)=0 A(i,j)=1.2*m(i,j); %普通公路上每百件的運(yùn)費(fèi) else A(i,j)=inf; end endendfor i=1:n for j=1:n A(g(i),g(j)=2*A(g(i),g(j)/1.2; %高級公路上每百件的運(yùn)費(fèi) endendfor i=1:42 A(i,i)=0;endD,R=floyd(A);for i=1:10 for j=1:3 X(i,j)=D(C(i),q(j); end endXX,INDEX=mi

20、n(X')在命令窗口輸入：>> min_spend(m)XX =69.6000 150.0000 147.6000 90.0000 156.0000 174.0000 189.6000 111.6000 120.0000 122.4000INDEX = 2 1 3 3 1 3 2 3 1 3XX為從各個倉庫到三個企業(yè)中的最小費(fèi)用，INDEX為最小費(fèi)用的企業(yè)。練習(xí)題14 最小代價流 將上題容量網(wǎng)絡(luò)的邊上增加另一個權(quán)數(shù)-代價，變?yōu)榫哂写鷥r的容量網(wǎng)絡(luò)，單位代價為容量數(shù)的十位上的數(shù)字，求比最大流少30單位的最小代價流。由上題結(jié)果可知，最大流為142，則最小代價流的流量應(yīng)該為112。

21、用迭代算法，預(yù)定流量值wf0=112。方法一：C=0 25 0 56 61 0 0 0 0; 0 0 71 0 0 36 0 0 0; 0 0 0 0 0 0 0 34 0; 0 0 0 0 49 0 74 0 0; 0 24 0 0 0 72 57 0 0; 0 0 38 0 0 0 0 53 45; 0 0 0 0 0 38 0 0 67; 0 0 0 0 0 0 0 0 74; 0 0 0 0 0 0 0 0 0;%弧容量b=0 2 0 5 6 0 0 0 0; 0 0 7 0 0 3 0 0 0; 0 0 0 0 0 0 0 3 0; 0 0 0 0 4 0 7 0 0; 0 2 0

22、0 0 7 5 0 0; 0 0 3 0 0 0 0 5 4; 0 0 0 0 0 3 0 0 6; 0 0 0 0 0 0 0 0 7; 0 0 0 0 0 0 0 0 0;%弧上單位流量的費(fèi)用n=9;wf=0;wf0=112; %wf表示最大流量, wf0表示預(yù)定的流量值for(i=1:n) for(j=1:n) f(i,j)=0;end;end%取初始可行流f為零流while(1)for(i=1:n)for(j=1:n)if(j=i)a(i,j)=Inf;end;end;end%構(gòu)造有向賦權(quán)圖for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)=0)

23、a(i,j)=b(i,j);elseif(C(i,j)>0&f(i,j)=C(i,j)a(j,i)=-b(i,j);elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;endfor(i=2:n)p(i)=Inf;s(i)=i;end%用Ford算法求最短路, 賦初值for(k=1:n)pd=1;%求有向賦權(quán)圖中vs到vt的最短路for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i)p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;endif(pd)break;end;

24、end%求最短路的Ford算法結(jié)束if(p(n)=Inf)break;end%不存在vs到vt的最短路, 算法終止. 注意在求最小費(fèi)用最大流時構(gòu)造有向賦權(quán)圖中不會含負(fù)權(quán)回路, 所以不會出現(xiàn)k=ndvt=Inf;t=n;%進(jìn)入調(diào)整過程, dvt表示調(diào)整量while(1)%計算調(diào)整量if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t);%前向弧調(diào)整量elseif(a(s(t),t)<0)dvtt=f(t,s(t);end%后向弧調(diào)整量if(dvt>dvtt)dvt=dvtt;endif(s(t)=1)break;end%當(dāng)t的標(biāo)號為vs時, 終止計算調(diào)整

25、量t=s(t);end%繼續(xù)調(diào)整前一段弧上的流fpd=0;if(wf+dvt>wf0) dvt=wf0-wf;pd=1;end%如果最大流量大于或等于預(yù)定的流量值t=n;while(1)%調(diào)整過程if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt;%前向弧調(diào)整elseif(a(s(t),t)<0)f(t,s(t)=f(t,s(t)-dvt;end%后向弧調(diào)整if(s(t)=1)break;end%當(dāng)t的標(biāo)號為vs時, 終止調(diào)整過程t=s(t);endif(pd)break;end%如果最大流量達(dá)到預(yù)定的流量值wf=0; for(j=1:n)wf=wf

26、+f(1,j);end;end%計算最大流量zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%計算最小費(fèi)用f%顯示最小費(fèi)用最大流wf%顯示最小費(fèi)用最大流量zwf%顯示最小費(fèi)用運(yùn)行結(jié)果：>> f = 0 25 0 26 61 0 0 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 26 0 0 0 11 0 0 0 9 41 0 0 0 0 0 0 0 0 0 0 45 0 0 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

27、 0 0 0wf = 112zwf = 1708由程序運(yùn)行結(jié)果可得：比最大流少30單位的最小代價流為f，最小代價為1708。方法二在已知流量上限情況下的Lingo最小費(fèi)用求解sets: nodes/1.9/:; arcs(nodes, nodes): c,b,f; !f為流，c為網(wǎng)絡(luò)容量，b為費(fèi)用;endsetsdata:fmax = 112; !流量上界; c=0 25 0 56 61 0 0 0 0 0 0 71 0 0 36 0 0 0 0 0 0 0 0 0 0 34 0 0 0 0 0 49 0 74 0 0 0 24 0 0 0 72 57 0 0 0 0 38 0 0 0 0 5

28、3 45 0 0 0 0 0 38 0 0 67 0 0 0 0 0 0 0 0 74 0 0 0 0 0 0 0 0 0;b= 0 2 0 5 6 0 0 0 0 0 0 7 0 0 3 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 4 0 7 0 0 0 2 0 0 0 7 5 0 0 0 0 3 0 0 0 0 5 4 0 0 0 0 0 3 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0;enddatamin=sum(arcs:b*f);for(nodes(i) | i #ne# 1 #and# i #ne# size(nodes)

29、: sum(arcs(i,j):f(i,j) - sum(arcs(j,i):f(j,i)=0);sum(arcs(i,j)|i #eq# 1 : f(i,j)=fmax;for(arcs:bnd(0,f,c);練習(xí)題20 現(xiàn)在有8個城市，已知兩個城市之間的路費(fèi)如下表，現(xiàn)在有一個人從A城市出發(fā)旅行，應(yīng)該選擇怎樣的路線才能剛好每個城市都到達(dá)一次又回到A城市，其總路費(fèi)最少？A B C D E F G HABCDEFG 56 35 21 51 60 43 39 21 57 78 70 64 49 36 68 - 70 60 51 61 65 26 13 45 62 53 26 50解答：方法一建立規(guī)

30、劃模型：先將一般加權(quán)連通圖轉(zhuǎn)化成一個等價的加權(quán)完全圖，設(shè)當(dāng)從到時，否則，則得如下模型：利用lingo求解：model:!TSP問題;sets: cities/A,B,C,D,E,F,G,H/:level; link(cities, cities)|&1#ne#&2: w, x;!W距離矩陣;endsetsdata: w= 56 35 21 51 60 43 39 56 21 57 78 70 64 49 35 21 36 68 1000 70 60 21 57 36 51 61 65 26 51 78 68 51 13 45 61 60 70 1000 61 13 53 26

31、43 64 70 65 45 53 50 39 49 60 26 61 26 50;enddatan=size(cities); min=sum(link(i,j)|i #ne# j: w(i,j)*x(i,j);for(cities(i) : sum(cities(j)| j #ne# i: x(j,i)=1; sum(cities(j)| j #ne# i: x(i,j)=1; for(cities(j)| j #gt# 1 #and# j #ne# i : level(j) >= level(i) + x(i,j) - (n-2)*(1-x(i,j) + (n-3)*x(j,i);

32、 ););for(link : bin(x);for(cities(i) | i #gt# 1 : level(i)<=n-1-(n-2)*x(1,i); level(i)>=1+(n-2)*x(i,1););end由程序運(yùn)行結(jié)果可得，從A城市出發(fā)旅行，剛好每個城市都到達(dá)一次又回到A城市，且總路費(fèi)最少的路線為：。最少費(fèi)用為251。方法二（參考）求一個Hamilton圈，構(gòu)造新圈：由中刪掉邊和，添加邊和而得到，判斷：若+<+，則以新圈代替舊圈，稱為改良圈。cleara(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(1,7)=

33、43;a(1,8)=39;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(2,7)=64;a(2,8)=49;a(3,4)=36;a(3,5)=68;a(3,6)=Inf;a(3,7)=70;a(3,8)=60;a(4,5)=51;a(4,6)=61;a(4,7)=65;a(4,8)=26;a(5,6)=13;a(5,7)=45;a(5,8)=62;a(6,7)=53;a(6,8)=26;a(7,8)=50;a(8,:)=0;a=a+a'c1= 1 3 2 5:8 4;L=length(c1);flag=1;while flag>0 flag=

34、0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endsum1=sum1+a(c1(8),c1(1)circle=c1;sum=sum1;c1=1 4 3 2 5:8 ;%改變初始圈，該算法的最后一個頂點不動flag=1;while flag>0 flag=0;

35、 for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<. a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endsum1=sum1+a(c1(8),c1(1)if sum1<sum sum=sum1; circle=c1;endcircle,sum練習(xí)題21 某街道布局如下，在0點處停放有一輛灑水車，每天灑水車都要給每

36、條街道灑水，請給灑水車優(yōu)化一條路線。解答（參考）：以下版本方法正確，應(yīng)可以簡化。該題為中國郵遞員問題，故先使用floyd算法求出奇點間的最短距離，并建立以奇點為頂點的完全圖，調(diào)用jidianjvzhen.m文件clear; c=inf 5 inf 6 inf inf inf inf inf inf 5 inf 5 inf 6 inf inf inf inf inf inf 5 inf inf inf 2 inf inf inf inf 6 inf inf inf 3 inf 4 inf inf inf inf 6 inf 3 inf 6 inf 4 inf inf inf inf 2 inf

37、6 inf inf inf 4 inf inf inf inf 4 inf inf inf 4 inf 2 inf inf inf inf 4 inf 4 inf 3 inf inf inf inf inf inf 4 inf 3 inf inf inf inf inf inf inf inf 2 inf inf 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 h

38、1=c(2,4); h2=c(2,6); h3=c(2,7); h4=c(2,8); h5=c(2,10);h6=c(4,6);h7=c(4,7);h8=c(4,8);h9=c(4,10); h10=c(6,7); h11=c(6,8); h12=c(6,10); h13=c(7,8); h14=c(7,10); h15=c(8,10);disp(c(2,6);disp(c(4,8);disp(c(7,10);a=zeros(6); a(1,2)=h1;a(1,3)=h2;a(1,4)=h3;a(1,5)=h4;a(1,6)=h5; a(2,3)=h6;a(2,4)=h7 ;a(2,5)=h8

39、;a(2,6)=h9;a(3,4)=h10; a(3,5)=h11;a(3,6)=h12;a(4,5)=h13;a(4,6)=h14;a(5,6)=h15;a=a+a' a(find(a=0)=inf;Hung_Al(a);%原矩陣的2，4，6，7，8，10分別對應(yīng)于奇點矩陣的1，2，3，4，5，6頂點%接著調(diào)用Hung_Al.m文件找出以奇點為頂點的完全圖的最優(yōu)匹配function Matching,Cost = Hung_Al(Matrix) Matrix=a; Matching = zeros(size(Matrix); % 找出每行和每列相鄰的點數(shù)num_y = sum(isi

40、nf(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 % 確保存在完美匹配，計算矩陣邊

41、集 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 命令進(jìn)行控制調(diào)用步驟函數(shù) exit_flag = 1; stepnum = 1; while exit_flag

42、 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(

43、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); Matching Cost%下面是 6 個步驟函數(shù) step1step6 %步驟 1：找到包含 0 最多的行，從該行減去最小值 function P_cond,stepnum=step1(P_cond)P_size = length(P_cond); for ii = 1:P_size rmin = min(

44、P_cond(ii,:); 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

45、 = 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; endend end % 重初始化變量 r_cov = zeros(P_size,1); c_cov = zeros(P_size,1);stepnum = 3;%步驟 3：每列都用一個 0 構(gòu)成的星型覆蓋，如果每列都存在這樣的覆蓋，則 M 為最大匹配 function c_cov,stepnum = step3(M,P_size) c_cov

46、 = sum(M,1); if sum(c_cov) = P_size stepnum = 7; else stepnum = 4; end%步驟 4：找一個未被覆蓋的 0 且從這出發(fā)點搜尋星型 0 覆蓋。如果不存在，轉(zhuǎn)步驟 5，否% 則轉(zhuǎn)步驟 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 =