




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
本文格式為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=[
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 設(shè)定明確的工作優(yōu)先級(jí)計(jì)劃
- 財(cái)務(wù)分析在企業(yè)評(píng)估中的應(yīng)用計(jì)劃
- 教學(xué)創(chuàng)新與成果分享機(jī)制計(jì)劃
- 防止職業(yè)倦怠的小技巧計(jì)劃
- 醫(yī)學(xué)影像科醫(yī)生工作計(jì)劃
- 建立員工反饋與建議機(jī)制計(jì)劃
- 2025年電動(dòng)晾衣機(jī)項(xiàng)目合作計(jì)劃書
- 景區(qū)承包合同
- 珠寶定制服務(wù)特殊條款協(xié)議
- 農(nóng)產(chǎn)品電商項(xiàng)目開發(fā)合作框架協(xié)議
- (完整版)中心醫(yī)院心血管學(xué)科的專科建設(shè)與發(fā)展規(guī)劃
- 勞動(dòng)合同法草案的立法背景與創(chuàng)新黎建飛中國(guó)人民大學(xué)法學(xué)院教授
- 第三章 檢測(cè)儀表與傳感器
- 服裝QC尾期查貨報(bào)告(中英雙語(yǔ))
- 冷庫(kù)噴涂施工工藝(詳細(xì))
- 電機(jī)學(xué)辜承林(第三版)第1章
- 醫(yī)療機(jī)構(gòu)停業(yè)(歇業(yè))申請(qǐng)書
- Counting Stars 歌詞
- 肩鎖關(guān)節(jié)脫位的分型及其endobutton手術(shù)治療
- 管理系統(tǒng)中計(jì)算機(jī)應(yīng)用PPT課件
- 企業(yè)辦公自動(dòng)化系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)
評(píng)論
0/150
提交評(píng)論