活動(dòng)網(wǎng)絡(luò)-(Activity-Network)-精選課件

活動(dòng)網(wǎng)絡(luò)(ActivityNetwork)計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV網(wǎng)絡(luò))1精

C1

高等數(shù)學(xué)

C2

程序設(shè)計(jì)基礎(chǔ)

C3

離散數(shù)學(xué)C1,C2

C4

數(shù)據(jù)結(jié)構(gòu)

C3,C2C5

高級(jí)語言程序設(shè)計(jì)C2C6

編譯方法C5,C4C7

操作系統(tǒng)C4,C9C8

普通物理C1C9

計(jì)算機(jī)原理

C8

課程代號(hào)課程名稱先修課程2精學(xué)生課程學(xué)習(xí)工程圖C8C3C5C4C9C6C7C1C23精可以用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊<Vi,Vj>表示活動(dòng)Vi必須先于活動(dòng)Vj

進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò)(ActivityOnVertices)。在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路,即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。因此，對(duì)給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。4精檢測(cè)有向環(huán)的一種方法是對(duì)AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個(gè)頂點(diǎn)(代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判?。如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄?則該網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)。5精如果AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。例如,對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判?得到的拓?fù)溆行蛐蛄袨?/p>

C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C26精進(jìn)行拓?fù)渑判虻姆椒á?/p>

輸入AOV網(wǎng)絡(luò)。令n為頂點(diǎn)個(gè)數(shù)。

②

在AOV網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn),并輸出之;

③

從圖中刪去該頂點(diǎn),同時(shí)刪去所有它發(fā)出的有向邊;④

重復(fù)以上

②、③步,直到

全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿?；?/p>

圖中還有未輸出的頂點(diǎn),但已跳出處理循環(huán)。說明圖中還剩下一些頂點(diǎn),它們都有直接前驅(qū)。這時(shí)網(wǎng)絡(luò)中必存在有向環(huán)。7精C0C1C2C3C4C5拓?fù)渑判虻倪^程(a)有向無環(huán)圖C2C5C1C0C3(b)輸出頂點(diǎn)C4C1C2C5C3(c)輸出頂點(diǎn)C0C4C0C2C5C1C3(d)輸出頂點(diǎn)C38精C1C2C5(e)輸出頂點(diǎn)C2C5C1(f)輸出頂點(diǎn)C1C5(g)輸出頂點(diǎn)C5

最后得到的拓?fù)溆行蛐蛄袨?/p>

C4,C0,C3,C2,C1,C5

。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對(duì)于本來沒有這種關(guān)系的頂點(diǎn)，如C4和C2，也排出了先后次序關(guān)系。(h)拓?fù)渑判蛲瓿?精AOV網(wǎng)絡(luò)及其鄰接表表示C0C1C2C3C4C5C0C1C2C30C4C50012345countdataadj

1301031

destlink305150015010精在鄰接表中增設(shè)一個(gè)數(shù)組count[

]，記錄各頂點(diǎn)入度。入度為零的頂點(diǎn)即無前驅(qū)頂點(diǎn)。在輸入數(shù)據(jù)前,頂點(diǎn)表NodeTable[]和入度數(shù)組count[]全部初始化。在輸入數(shù)據(jù)時(shí),每輸入一條邊<j,k>,就需要建立一個(gè)邊結(jié)點(diǎn),并將它鏈入相應(yīng)邊鏈表中,統(tǒng)計(jì)入度信息：

Edge<int>*

p=newEdge<int>(k);

//建立邊結(jié)點(diǎn),dest

域賦為k

p->link=NodeTable[j].adj;

NodeTable[j].adj=p;

//鏈入頂點(diǎn)j

的邊鏈表的前端

count[k]++;

//頂點(diǎn)

k

入度加一

11精在算法中,使用一個(gè)存放入度為零的頂點(diǎn)的鏈?zhǔn)綏?供選擇和輸出無前驅(qū)的頂點(diǎn)。拓?fù)渑判蛩惴擅枋鋈缦拢航⑷攵葹榱愕捻旤c(diǎn)棧;當(dāng)入度為零的頂點(diǎn)棧不空時(shí),重復(fù)執(zhí)行

從頂點(diǎn)棧中退出一個(gè)頂點(diǎn),并輸出之;

從AOV網(wǎng)絡(luò)中刪去這個(gè)頂點(diǎn)和它發(fā)出的邊,邊的終頂點(diǎn)入度減一;

如果邊的終頂點(diǎn)入度減至0,則該頂點(diǎn)進(jìn)入度為零的頂點(diǎn)棧;

如果輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù),則報(bào)告網(wǎng)絡(luò)中存在有向環(huán)。12精在算法實(shí)現(xiàn)時(shí),為了建立入度為零的頂點(diǎn)棧,可以不另外分配存儲(chǔ)空間,直接利用入度為零的頂點(diǎn)的count[]數(shù)組元素。設(shè)立一個(gè)棧頂指針top,指示當(dāng)前棧頂位置,即某一個(gè)入度為零的頂點(diǎn)。棧初始化時(shí)置top

=-1。將頂點(diǎn)i

進(jìn)棧時(shí)執(zhí)行以下指針的修改：

count[i]=top;top=i;

//top指向新棧頂i,原棧頂元素在count[i]中退棧操作可以寫成：

j=top;top=count[top];

//位于棧頂?shù)捻旤c(diǎn)記于

j,top退到次棧頂13精拓?fù)渑判驎r(shí)入度為零的頂點(diǎn)棧在count[]中的變化C0C1C2C3C4C513010313-112322-112221-1222012345012345012345012345toptoptoptop建棧toptop頂點(diǎn)4出棧toptop頂點(diǎn)0出棧14精拓?fù)渑判驎r(shí)入度為零的頂點(diǎn)棧在count[]中的變化C0C1C2C3C4C521-12222-1-12212-1-122-12-1-122-1012345012345012345012345toptoptoptoptop頂點(diǎn)1出棧top頂點(diǎn)5出棧頂點(diǎn)3出棧頂點(diǎn)2出棧15精用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE網(wǎng)絡(luò))如果在無有向環(huán)的帶權(quán)有向圖中,用有向邊表示一個(gè)工程中的活動(dòng)(Activity),

用邊上權(quán)值表示活動(dòng)持續(xù)時(shí)間(Duration),

用頂點(diǎn)表示事件(Event),

則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò),簡(jiǎn)稱AOE(ActivityOnEdges)網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?16精為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)? 從源點(diǎn)到各個(gè)頂點(diǎn),以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長(zhǎng)度也可能不同。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同,但只有各條路徑上所有活動(dòng)都完成了,整個(gè)工程才算完成。因此,完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度,即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑(CriticalPath)。17精a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng),即不按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)。關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。因此,只要找到了關(guān)鍵活動(dòng),就可以找到關(guān)鍵路徑。例如,下圖就是一個(gè)AOE網(wǎng)。18精定義幾個(gè)與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量：①

事件Vi

的最早可能開始時(shí)間Ve(i)

是從源點(diǎn)V0

到頂點(diǎn)Vi的最長(zhǎng)路徑長(zhǎng)度。②

事件Vi的最遲允許開始時(shí)間Vl[i]

是在保證匯點(diǎn)Vn-1

在Ve[n-1]

時(shí)刻完成的前提下，事件Vi

的允許的最遲開始時(shí)間。③

活動(dòng)ak的最早可能開始時(shí)間

e[k]

設(shè)活動(dòng)ak

在邊<

Vi,Vj>上,則e[k]是從源點(diǎn)V0到頂點(diǎn)Vi

的最長(zhǎng)路徑長(zhǎng)度。因此,

e[k]=Ve[i]。④

活動(dòng)ak

的最遲允許開始時(shí)間

l[k]

19精

l[k]是在不會(huì)引起時(shí)間延誤的前提下,該活動(dòng)允許的最遲開始時(shí)間。

l[k]=Vl[j]-dur(<i,j>)。

其中,dur(<i,j>)是完成

ak所需的時(shí)間。⑤

時(shí)間余量

l[k]-e[k]

表示活動(dòng)

ak

的最早可能開始時(shí)間和最遲允許開始時(shí)間的時(shí)間余量。l[k]==e[k]

表示活動(dòng)

ak

是沒有時(shí)間余量的關(guān)鍵活動(dòng)。為找出關(guān)鍵活動(dòng),需要求各個(gè)活動(dòng)的e[k]

與l[k]，以判別是否

l[k]==e[k]。20精為求得e[k]與l[k],需要先求得從源點(diǎn)V0

到各個(gè)頂點(diǎn)Vi的Ve[i]

和Vl[i]。求Ve[i]的遞推公式

從

Ve[0]=0開始，向前遞推

<Vj,Vi>S2,i=1,2,,n-1

S2

是所有指向Vi的有向邊<

Vj

,Vi

>的集合。

從Vl[n-1]=Ve[n-1]開始，反向遞推

<Vi,Vj

>S1,i=n-2,n-3,,0S1是所有源自Vi的有向邊<

Vi

,Vj

>的集合。21精這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚣澳嫱負(fù)溆行虻那疤嵯逻M(jìn)行。設(shè)活動(dòng)ak

(k=1,2,…,e)在帶權(quán)有向邊<

Vi

,Vj

>

上,其持續(xù)時(shí)間用dur(<Vi

,Vj

>)

表示,則有

e[k]=Ve[i]；

l[k]=Vl[j]-dur(<Vi

,Vj

>)；k