圖論習(xí)題及答案

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

4、d個(gè)容器n',i,temp)endoutput:第1個(gè)物品放在第1個(gè)容器第2個(gè)物品放在第2個(gè)容器第3個(gè)物品放在第1個(gè)容器第4個(gè)物品放在第2個(gè)容器第5個(gè)物品放在第2個(gè)容器第6個(gè)物品放在第3個(gè)容器解答三：function box_count=FFD(x)%降序首次適應(yīng)算法v=100;x=fliplr(sort(x);%v=input('請(qǐng)輸入箱子的容積:');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種商品作為獎(jiǎng)品供中獎(jiǎng)?lì)櫩瓦x擇,車(chē)的容量為1000dm3 , 獎(jiǎng)品i占用的空間為wi dm3

6、,價(jià)值為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。問(wèn)如何裝車(chē)才能總價(jià)值最大。解答：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 對(duì)最后一個(gè)求有向圈的示例用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);%頂點(diǎn)個(gè)數(shù)p=zeros(1,n);%存儲(chǔ)搜索過(guò)的頂點(diǎn)X=zeros(n,n);%用來(lái)設(shè)置禁止矩陣，往回返的時(shí)候設(shè)置此路已被搜索k=1;p(1)=1;%第一個(gè)點(diǎn)作為初始點(diǎn)開(kāi)始搜索while p(1)<=n %每個(gè)頂點(diǎn)都作為初始點(diǎn)搜索包含p(1)的有向圈， i=p(1)+1;%當(dāng)前點(diǎn)k往后搜索時(shí)都是從p(1)+1開(kāi)始，從而也可以搜索下標(biāo)小于k的點(diǎn)while i<=n %還有后續(xù)點(diǎn)沒(méi)有搜索（這些點(diǎn)有可能比當(dāng)前點(diǎn)k?。?if (H(p(k),i)=1)&(X(p(k),i)=0)&isempty(find(p=i)%滿足三

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

13、到出發(fā)點(diǎn)了 p(1)=p(1)+1; %換下一個(gè)出發(fā)點(diǎn)（初始點(diǎn)） end endend運(yùn)行結(jié)果：1 2 4 3 2 4 5 2 4 3 2 5 3練習(xí)題9 選址問(wèn)題 現(xiàn)準(zhǔn)備在7個(gè)居民點(diǎn)中設(shè)置一銀行，路線與距離如下圖，問(wèn)設(shè)在哪個(gè)點(diǎn)，可使最大服務(wù)距離最小？若設(shè)兩個(gè)點(diǎn)呢？解答：第一步：function D,R=floyd(A)%用floyd算法實(shí)現(xiàn)求任意兩點(diǎ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)，說(shuō)明通過(guò)k的路程更短 R(i,j)=R(k,j);%更新R(i,j)，需要通過(guò)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第二步：對(duì)于第一問(wèn)在矩陣D中每一個(gè)取大得到一列數(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)在頂點(diǎn)6建立銀行，最大服務(wù)距離最小，最小是4.8.第三步：對(duì)于第二問(wèn)任取兩個(gè)點(diǎn)做集合，計(jì)算每個(gè)點(diǎn)到這個(gè)集合的最小值，再在這個(gè)最小值中取大，即在矩陣

17、D中任取兩行，對(duì)應(yīng)比較取小得一向量，將所有這樣的向量寫(xiě)成行向量構(gòu)成一矩陣，然后用問(wèn)題一的算法程序即可。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é)果，在頂點(diǎn)2,4或2,7點(diǎn)建立銀行都使得最大服務(wù)距離最小，最小值是3練習(xí)題10 貨物調(diào)運(yùn) 已

18、知該地區(qū)有生產(chǎn)該物資的企業(yè)三家，大小物資倉(cāng)庫(kù)八個(gè)，國(guó)家級(jí)儲(chǔ)備庫(kù)兩個(gè)，其分布情況見(jiàn)下面的附件1。經(jīng)核算該物資的運(yùn)輸成本為高等級(jí)公路2元/公里百件，普通公路1.2元/公里百件，假設(shè)各企業(yè)、物資倉(cāng)庫(kù)及國(guó)家級(jí)儲(chǔ)備庫(kù)之間的物資可以通過(guò)公路運(yùn)輸互相調(diào)運(yùn)，請(qǐng)給出各個(gè)倉(cāng)庫(kù)應(yīng)該從哪個(gè)企業(yè)調(diào)運(yùn)。解答：首先建立各個(gè)交匯點(diǎn)的距離矩陣m。然后建立函數(shù)文件。%各倉(cāng)庫(kù)到各企業(yè)的最小運(yùn)費(fèi)function min_spend(m)c=28,23,35,31,22,36,29,38; %倉(cāng)庫(kù)cc=27,30; %國(guó)家儲(chǔ)存庫(kù)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;%高級(jí)公路上的點(diǎn)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; %高級(jí)公路上每百件的運(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為從各個(gè)倉(cāng)庫(kù)到三個(gè)企業(yè)中的最小費(fèi)用，INDEX為最小費(fèi)用的企業(yè)。練習(xí)題14 最小代價(jià)流 將上題容量網(wǎng)絡(luò)的邊上增加另一個(gè)權(quán)數(shù)-代價(jià)，變?yōu)榫哂写鷥r(jià)的容量網(wǎng)絡(luò)，單位代價(jià)為容量數(shù)的十位上的數(shù)字，求比最大流少30單位的最小代價(jià)流。由上題結(jié)果可知，最大流為142，則最小代價(jià)流的流量應(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)用最大流時(shí)構(gòu)造有向賦權(quán)圖中不會(huì)含負(fù)權(quán)回路, 所以不會(huì)出現(xiàn)k=ndvt=Inf;t=n;%進(jìn)入調(diào)整過(guò)程, dvt表示調(diào)整量while(1)%計(jì)算調(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)號(hào)為vs時(shí), 終止計(jì)算調(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)整過(guò)程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)號(hào)為vs時(shí), 終止調(diào)整過(guò)程t=s(t);endif(pd)break;end%如果最大流量達(dá)到預(yù)定的流量值wf=0; for(j=1:n)wf=wf

26、+f(1,j);end;end%計(jì)算最大流量zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%計(jì)算最小費(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單位的最小代價(jià)流為f，最小代價(jià)為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個(gè)城市，已知兩個(gè)城市之間的路費(fèi)如下表，現(xiàn)在有一個(gè)人從A城市出發(fā)旅行，應(yīng)該選擇怎樣的路線才能剛好每個(gè)城市都到達(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)化成一個(gè)等價(jià)的加權(quán)完全圖，設(shè)當(dāng)從到時(shí)，否則，則得如下模型：利用lingo求解：model:!TSP問(wèn)題;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ā)旅行，剛好每個(gè)城市都到達(dá)一次又回到A城市，且總路費(fèi)最少的路線為：。最少費(fèi)用為251。方法二（參考）求一個(gè)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 ;%改變初始圈，該算法的最后一個(gè)頂點(diǎn)不動(dòng)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點(diǎn)處停放有一輛灑水車(chē)，每天灑水車(chē)都要給每

36、條街道灑水，請(qǐng)給灑水車(chē)優(yōu)化一條路線。解答（參考）：以下版本方法正確，應(yīng)可以簡(jiǎn)化。該題為中國(guó)郵遞員問(wèn)題，故先使用floyd算法求出奇點(diǎn)間的最短距離，并建立以奇點(diǎn)為頂點(diǎn)的完全圖，調(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分別對(duì)應(yīng)于奇點(diǎn)矩陣的1，2，3，4，5，6頂點(diǎn)%接著調(diào)用Hung_Al.m文件找出以奇點(diǎn)為頂點(diǎn)的完全圖的最優(yōu)匹配function Matching,Cost = Hung_Al(Matrix) Matrix=a; Matching = zeros(size(Matrix); % 找出每行和每列相鄰的點(diǎn)數(shù)num_y = sum(isi

40、nf(Matrix),1); num_x = sum(isinf(Matrix),2); % 找出每行和每列的孤立點(diǎn)數(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 % 確保存在完美匹配，計(jì)算矩陣邊

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ù)程序,此處將每個(gè)步驟用 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 個(gè)步驟函數(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 中找一個(gè) 0，并找出一個(gè)以該數(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：每列都用一個(gè) 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：找一個(gè)未被覆蓋的 0 且從這出發(fā)點(diǎn)搜尋星型 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 =