版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
7.6關(guān)鍵路徑問題提出把工程計劃表示為有向圖,用頂點表示事件,弧表示活動;每個事件表示在它之前的活動已完成,在它之后的活動可以開始例設(shè)一個工程有11項活動,9個事件事件V1——表示整個工程開始事件V9——表示整個工程結(jié)束問題:(1)完成整項工程至少需要多少時間?(2)哪些活動是影響工程進(jìn)度的關(guān)鍵?987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4定義AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖,其中頂點表示事件,弧表示活動,權(quán)表示活動持續(xù)時間路徑長度——路徑上各活動持續(xù)時間之和關(guān)鍵路徑——路徑長度最長的路徑叫~Ve(j)——表示事件Vj的最早發(fā)生時間Vl(j)——表示事件Vj的最遲發(fā)生時間e(i)——表示活動ai的最早開始時間l(i)——表示活動ai的最遲開始時間l(i)-e(i)——表示完成活動ai的時間余量關(guān)鍵活動——關(guān)鍵路徑上的活動叫~,即l(i)=e(i)的活動問題分析如何找e(i)=l(i)的關(guān)鍵活動?設(shè)活動ai用弧<j,k>表示,其持續(xù)時間記為:dut(<j,k>)則有:(1)e(i)=Ve(j)(2)l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)?(1)從Ve(1)=0開始向前遞推(2)從Vl(n)=Ve(n)開始向后遞推求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動ell-e000022660462583770770710316160141400337.7最短路徑問題提出用帶權(quán)的有向圖表示一個交通運輸網(wǎng),圖中:頂點——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線路的長度或沿此線路運輸所花的時間或費用等問題:從某頂點出發(fā),沿圖的邊到達(dá)另一頂點所經(jīng)過的路徑中,各邊上權(quán)值之和最小的一條路徑——最短路徑從某個源點到其余各頂點的最短路徑51643208562301371732913長度最短路徑<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>813192120迪杰斯特拉(Dijkstra)算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法:把V分成兩組:(1)S:已求出最短路徑的頂點的集合(2)V-S=T:尚未確定最短路徑的頂點集合將T中頂點按最短路徑遞增的次序加入到S中,保證:(1)從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度(2)每個頂點對應(yīng)一個距離值
S中頂點:從V0到此頂點的最短路徑長度
T中頂點:從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度依據(jù):可以證明V0到T中頂點Vk的最短路徑,或是從V0到Vk的直接路徑的權(quán)值;或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和(反證法可證)Dijkstra算法可描述如下:
初始化:S←{v0};
dist[j]←Edge[0][j],j=1,2,…,n-1;
//n為圖中頂點個數(shù)1、求出最短路徑的長度:
dist[k]←min{dist[i]},i
V-S;S←S
U{k
};2、
修改:
dist[i]←min{dist[i],dist[k]+Edge[k][i]},
對于每一個i
V-S;3、
判斷:若S=V,則算法結(jié)束,否則轉(zhuǎn)1。計算從單個頂點到其它各個頂點的最短路徑ShortestPath(
constint
n,
constint
v){
for(
inti=0;
i<n;
i++)
{
dist[i]=Edge[v][i];
//dist數(shù)組初始化
S[i]=0;
if(i!=v
&&
dist[i]<MAXINT)path[i]=v;
else
path[i]=-1; //path數(shù)組初始化
}
S[v]=1;
dist[v]=0; //頂點v加入頂點集合
//選擇當(dāng)前不在集合S中具有最短路徑的頂點u
for(i=0;
i<n-1;
i++){
int
min=MAXINT;
int
u=v;
for(
int
j=0;
j<n;
j++)
if(!S[j]&&
dist[j]<min)
{
u=j;
min=
dist[j];
}
S[u]=1;
//將頂點u加入集合S
for(
int
w=0;
w<n;
w++)//修改
if(!S[w]&&
Edge[u][w]<MAXINT&&
dist[u]+Edge[u][w]<
dist[w]){
dist[w]=
dist[u]+Edge[u][w];
path[w]=u;
}
}}
13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329每一對頂點之間的最短路徑方法一:每次以一個頂點為源點,重復(fù)執(zhí)行Dijkstra算法n次——T(n)=O(n3)方法二:弗洛伊德(Floyd)算法算法思想:逐個頂點試探法求最短路徑步驟初始時設(shè)置一個n階方陣,令其對角線元素為0,若存在弧<Vi,Vj>,則對應(yīng)元素為權(quán)值;否則為逐步試著在原直接路徑中增加中間頂點,若加入中間點后路徑變短,則修改之;否則,維持原值所有頂點試探完畢,算法結(jié)束對于每一對頂點u和v,看看是否存在一個頂點w使得從u到w再到v比己知的路徑更短。如果是更新它。不可思議的是,只要按排適當(dāng),就能得到結(jié)果。//dist(i,j)為從節(jié)點i到節(jié)點j的最短距離Fori←1tondoForj←1tondodist(i,j)=weight(i,j)Fork←1tondo//k為“中間節(jié)點”
if(dist(i,k)+dist(k,j)<dist(i,j))then//是否是更短的路徑?
dist(i,j)=dist(i,k)+dist(k,j)例ACB264311041160230初始:路徑:ABACBABCCA046602370加入V2:路徑:ABA
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 【語文】新課標(biāo)2024高考二輪復(fù)習(xí):專題八《文言文閱讀》
- 諸侯紛爭與變法運動課件-2024-2025學(xué)年高一上學(xué)期統(tǒng)編版(2019)必修中外歷史綱要上
- 4.2 平行線分線段成比例 九年級數(shù)學(xué)北師大版上冊課時優(yōu)化訓(xùn)練(含答案)
- 天津市濱海新區(qū)2023-2024學(xué)年高一年級下學(xué)期期末檢測語文試題(解析版)
- 小學(xué)四年級上冊語文第一單元練習(xí)題50道及答案
- 2024年全民(保護(hù)海洋環(huán)境)應(yīng)知應(yīng)會知識考試題庫與答案
- 人力資源政策在不同文化背景下的適應(yīng)性研究
- 股權(quán)激勵計劃對公司股東責(zé)任感的提升作用研究分析
- 江蘇省南通市如東縣市級名校2023-2024學(xué)年中考數(shù)學(xué)考前最后一卷含解析
- 2023年珠海市金灣區(qū)招聘職員筆試真題
- 【教學(xué)創(chuàng)新大賽】基于新工科人才培養(yǎng)的大學(xué)物理教學(xué)全域重構(gòu)
- 遵守社會規(guī)則 單元作業(yè)設(shè)計
- 初中道德與法治大單元教學(xué)中議題式教學(xué)設(shè)計的實踐探究 論文
- 中等職業(yè)學(xué)校校園消防安全管理制度
- (超全)英語動詞過去式的變化規(guī)則表
- 材料彈塑性及有限元
- 期中試卷答題卡標(biāo)準(zhǔn)形式
- 年產(chǎn)10萬噸輕鋼結(jié)構(gòu)年產(chǎn)10萬噸壓型彩板和重鋼結(jié)構(gòu)生產(chǎn)線項目可行性研究報告
- 耳鼻喉科運用PDCA循環(huán)提高新生兒聽力篩查初篩率品管圈成果匯報
- 一年級上冊數(shù)學(xué)說課稿-7.1 10的再認(rèn)識|北京版
- 繼續(xù)教育公需課答案匯總(80分以上)
評論
0/150
提交評論