數學建模程序必用

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

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

設A=(aij)n×n為賦權圖G=(V,E,F)的矩陣,當vivj∈E時aij=F(vivj),否則取aii=0,aij=+∞(i≠j),dij表示從vi到vj點的距離,rij表示從vi到vj點的最短路中一個點的編號.①賦初值.對所有i,j,dij=aij,rij=j.k=1.轉向②

②更新dij,rij.對所有i,j,若dik+dkj＜dij,則令dij=dik+dkj,rij=k,轉向③.

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

例1求圖6-4中任意兩點間的最短路.

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

n=8;A=[0281InfInfInfInf206Inf1InfInfInf8607512Inf1Inf70InfInf9InfInf15Inf03Inf8InfInf1Inf3046InfInf29Inf403

InfInfInfInf8630];%MATLAB中,Inf表示∞D=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);%數組x記錄A中不同的正數kk=1;%臨時變量

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

k=k-1%顯示A中所有不同正數的個數

for(i=1:k-1)for(j=i+1:k)%將x中不同的正數從小到大排序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開始,對X中所有M的非飽和點,尋覓M?增廣路.若不存在M?增廣路,則M為最大匹配;若存在M?增廣路P,則將P中M與非M的邊互換得到比M多一邊的匹配M1,再對M1重復上述過程.

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

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

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

④設xy∈M,則令S=S∪{x},T=T∪{y},轉向③.

⑤u??y路是M?增廣路,設為P,并令M=M⊕P,轉向①.這里M⊕P=M∪P\\?M∩P,是對稱差.

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

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

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

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

⑤將yj在M中與之鄰接的點xk(即xkyj∈M),給以標號j和標記*,轉向②.例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中點的標號和標記*for(i=1:n)y(i)=0;end%將記錄Y中點的標號和標記*

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

if(pd)x(i)=-n-1;end;end%將X中M的所有非飽和點都給以標號0和標記*,程序中用n+1表示0標號,標號為負數時表示標記*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中與之鄰接的點xk(即xkyj∈M),給以標號j和標記*if(pdd)break;end;end

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

while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j)));%任取M的一個非飽和點yj,逆向返回if(j==n+1)break;end%找到X中標號為0的點時終止,獲得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中出現的邊去掉

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

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

利用可行點標記求最正確匹配的算法步驟如下：

設G=(X,Y,E,F)為完備的二部賦權圖,L是其一個初始可行點標記,尋常取

.,()0,

()max{()|},yYxXLy

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

????

M是GL的一個匹配.

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

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

③調整可行點標記,計算

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

,(),(),(),vTvSLvLvaLva

LL

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

令L=H,GL=GH,重新給出GL的一個匹配M,轉向①.

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

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

n=4;A=[