數(shù)學(xué)建模程序必用

本文格式為Word版，下載可任意編輯——數(shù)學(xué)建模程序必用圖論算法及其MATLAB程序代碼

求賦權(quán)圖G=(V,E,F)中任意兩點(diǎn)間的最短路的Warshall-Floyd算法：

設(shè)A=(aij)n×n為賦權(quán)圖G=(V,E,F)的矩陣,當(dāng)vivj∈E時(shí)aij=F(vivj),否則取aii=0,aij=+∞(i≠j),dij表示從vi到vj點(diǎn)的距離,rij表示從vi到vj點(diǎn)的最短路中一個(gè)點(diǎn)的編號(hào).①賦初值.對(duì)所有i,j,dij=aij,rij=j.k=1.轉(zhuǎn)向②

②更新dij,rij.對(duì)所有i,j,若dik+dkj＜dij,則令dij=dik+dkj,rij=k,轉(zhuǎn)向③.

③終止判斷.若dii＜0,則存在一條含有頂點(diǎn)vi的負(fù)回路,終止;或者k=n終止;否則令k=k+1,轉(zhuǎn)向②.最短路線可由rij得到.

例1求圖6-4中任意兩點(diǎn)間的最短路.

解：用Warshall-Floyd算法,MATLAB程序代碼如下：

n=8;A=[0281InfInfInfInf206Inf1InfInfInf8607512Inf1Inf70InfInf9InfInf15Inf03Inf8InfInf1Inf3046InfInf29Inf403

InfInfInfInf8630];%MATLAB中,Inf表示∞D(zhuǎn)=A;%賦初值

for(i=1:n)for(j=1:n)R(i,j)=j;end;end%賦路徑初值

for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)0)x(k)=A(i,j);%數(shù)組x記錄A中不同的正數(shù)kk=1;%臨時(shí)變量

for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end%排除一致的正數(shù)k=k+kk;end;end;end

k=k-1%顯示A中所有不同正數(shù)的個(gè)數(shù)

for(i=1:k-1)for(j=i+1:k)%將x中不同的正數(shù)從小到大排序if(x(j)0)kk=kk+1;zz=z;end;end%尋覓TT中的樹枝if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end%砍掉TT中的樹枝if(pd)break;end;end%已砍掉了TT中所有的樹枝pd=0;%判斷TT中是否有圈

for(y=1:n-1)for(z=y+1:n)if(TT(y,z)>0)pd=1;break;end;end;endif(pd)T(i,j)=0;T(j,i)=0;%假使TT中有圈elseq=q+1;end;end;end;end;endT%顯示近似最小生成樹T,程序終止

求二部圖G的最大匹配的算法(匈牙利算法),其基本思想是：從G的任意匹配M開始,對(duì)X中所有M的非飽和點(diǎn),尋覓M?增廣路.若不存在M?增廣路,則M為最大匹配;若存在M?增廣路P,則將P中M與非M的邊互換得到比M多一邊的匹配M1,再對(duì)M1重復(fù)上述過(guò)程.

設(shè)G=(X,Y,E)為二部圖,其中X={x1,x2,?,xn},Y={y1,y2,?,yn}.任取G的一初始匹配M(如任取e∈E,則M={e}是一個(gè)匹配).①令S=f,T=f,轉(zhuǎn)向②.

②若M飽和X\\S的所有點(diǎn),則M是二部圖G的最大匹配.否則,任取M的非飽和點(diǎn)u∈X\\S,令S=S∪{u},轉(zhuǎn)向③.

③記N(S)={v|?u∈S,uv∈E}.若N(S)=T,轉(zhuǎn)向②.否則取y∈N(S)\\?T.若y是M的飽和點(diǎn),轉(zhuǎn)向④,否則轉(zhuǎn)向⑤.

④設(shè)xy∈M,則令S=S∪{x},T=T∪{y},轉(zhuǎn)向③.

⑤u??y路是M?增廣路,設(shè)為P,并令M=M⊕P,轉(zhuǎn)向①.這里M⊕P=M∪P\\?M∩P,是對(duì)稱差.

由于計(jì)算M?增廣路P比較麻煩,因此將迭代步驟改為：

①將X中M的所有非飽和點(diǎn)(不是M中某條邊的端點(diǎn))都給以標(biāo)號(hào)0和標(biāo)記*,轉(zhuǎn)向②.②若X中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記*,則M是G的最大匹配.否則任取X中一個(gè)既有標(biāo)號(hào)又有標(biāo)記*的點(diǎn)xi,去掉xi的標(biāo)記*,轉(zhuǎn)向③.

③找出在G中所有與xi鄰接的點(diǎn)yj(即xiyj∈E),若所有這樣的yj都已有標(biāo)號(hào),則轉(zhuǎn)向②,否則轉(zhuǎn)向④.

④對(duì)與xi鄰接且尚未給標(biāo)號(hào)的yj都給定標(biāo)號(hào)i.若所有的yj都是M的飽和點(diǎn),則轉(zhuǎn)向⑤,否則逆向返回.即由其中M的任一個(gè)非飽和點(diǎn)yj的標(biāo)號(hào)i找到xi,再由xi的標(biāo)號(hào)k找到y(tǒng)k,?,最終由yt的標(biāo)號(hào)s找到標(biāo)號(hào)為0的xs時(shí)終止,獲得M?增廣路xsyt?xiyj,記P={xsyt,?,xiyj},重新記M為M⊕P,轉(zhuǎn)向①.

⑤將yj在M中與之鄰接的點(diǎn)xk(即xkyj∈M),給以標(biāo)號(hào)j和標(biāo)記*,轉(zhuǎn)向②.例1求圖6-9中所示的二部圖G的最大匹配.

匈牙利算法的MATLAB程序代碼如下：

m=5;n=5;A=[0110011011011000110000011];M(m,n)=0;

for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end%求初始匹配Mif(M(i,j))break;end;end%獲得僅含一條邊的初始匹配Mwhile(1)

for(i=1:m)x(i)=0;end%將記錄X中點(diǎn)的標(biāo)號(hào)和標(biāo)記*for(i=1:n)y(i)=0;end%將記錄Y中點(diǎn)的標(biāo)號(hào)和標(biāo)記*

for(i=1:m)pd=1;%尋覓X中M的所有非飽和點(diǎn)for(j=1:n)if(M(i,j))pd=0;end;end

if(pd)x(i)=-n-1;end;end%將X中M的所有非飽和點(diǎn)都給以標(biāo)號(hào)0和標(biāo)記*,程序中用n+1表示0標(biāo)號(hào),標(biāo)號(hào)為負(fù)數(shù)時(shí)表示標(biāo)記*pd=0;while(1)xi=0;

for(i=1:m)if(x(i)1)k=k-1;for(j=1:k)pdd=1;

for(i=1:m)if(M(i,yy(j)))x(i)=-yy(j);pdd=0;break;end;end%將yj在M中與之鄰接的點(diǎn)xk(即xkyj∈M),給以標(biāo)號(hào)j和標(biāo)記*if(pdd)break;end;end

if(pdd)k=1;j=yy(j);%yj不是M的飽和點(diǎn)

while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j)));%任取M的一個(gè)非飽和點(diǎn)yj,逆向返回if(j==n+1)break;end%找到X中標(biāo)號(hào)為0的點(diǎn)時(shí)終止,獲得M-增廣路Pk=k+1;end

for(i=1:k)if(M(P(i,1),P(i,2)))M(P(i,1),P(i,2))=0;%將匹配M在增廣路P中出現(xiàn)的邊去掉

elseM(P(i,1),P(i,2))=1;end;end%將增廣路P中沒(méi)有在匹配M中出現(xiàn)的邊參與到匹配M中break;end;end;end

if(pd)break;end;end%假使X中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記*,算法終止M%顯示最大匹配M,程序終止圖6-9

利用可行點(diǎn)標(biāo)記求最正確匹配的算法步驟如下：

設(shè)G=(X,Y,E,F)為完備的二部賦權(quán)圖,L是其一個(gè)初始可行點(diǎn)標(biāo)記,尋常取

.,()0,

()max{()|},yYxXLy

LxFxyyY????????????

????

M是GL的一個(gè)匹配.

①若X的每個(gè)點(diǎn)都是M的飽和點(diǎn),則M是最正確匹配.否則取M的非飽和點(diǎn)u∈X,令S={u},T=f,轉(zhuǎn)向②.

②記NL(S)={v|?u∈S,uv∈EL}.若NL(S)=T,則GL沒(méi)有完美匹配,轉(zhuǎn)向③.否則轉(zhuǎn)向④.

③調(diào)整可行點(diǎn)標(biāo)記,計(jì)算

aL=min{L(x)+L(y)??F(xy)|x∈S,y∈Y\\T}.由此得新的可行頂點(diǎn)標(biāo)記H(v)=,

,(),(),(),vTvSLvLvaLva

LL

????????????????

令L=H,GL=GH,重新給出GL的一個(gè)匹配M,轉(zhuǎn)向①.

④取y∈NL(S)\\T,若y是M的飽和點(diǎn),轉(zhuǎn)向⑤.否則,轉(zhuǎn)向⑥.⑤設(shè)xy∈M,則令S=S∪{x},T=T∪{y},轉(zhuǎn)向②.

⑥在GL中的u??y路是M?增廣路,記為P,并令M=M⊕P,轉(zhuǎn)向①.利用可行點(diǎn)標(biāo)記求最正確匹配算法的MATLAB程序代碼如下：

n=4;A=[