2010軟件水平考試軟件設(shè)計(jì)師重點(diǎn)難點(diǎn)輔導(dǎo)(3)

　　關(guān)鍵路徑這個(gè)知識(shí)點(diǎn)在軟件設(shè)計(jì)師考試中，是一個(gè)難點(diǎn)。

　　說(shuō)到關(guān)鍵路徑這個(gè)概念，大家應(yīng)該多少有些印象，可能都知道它是“最長(zhǎng)路徑”而不是“最短路徑”，但說(shuō)到它為什么是最長(zhǎng)路徑，提出這個(gè)概念的用意何在，它有什么應(yīng)用，在計(jì)算機(jī)中關(guān)鍵路徑是如何求的等問(wèn)題卻沒(méi)有幾個(gè)人能真正搞清楚，甚至?xí)�上給出了完整的例子，都有很多人看不懂。下面我先會(huì)簡(jiǎn)單的說(shuō)明基本概念，然后以一個(gè)例子，結(jié)合平時(shí)學(xué)員的疑問(wèn)，對(duì)這個(gè)知識(shí)點(diǎn)進(jìn)行詳細(xì)的分析。

　　在AOV網(wǎng)絡(luò)中，如果邊上的權(quán)表示完成該活動(dòng)所需的時(shí)間，則稱(chēng)這樣的AOV為AOE網(wǎng)絡(luò)。例如，圖1表示一個(gè)具有10個(gè)活動(dòng)的某個(gè)工程的AOE網(wǎng)絡(luò)。圖中有7個(gè)頂點(diǎn)，分別表示事件1～7，其中1表示工程開(kāi)始狀態(tài)，7表示工程結(jié)束狀態(tài)，邊上的權(quán)表示完成該活動(dòng)所需的時(shí)間。

　　下面我們來(lái)理解一下關(guān)鍵路徑的思想，圖1雖節(jié)點(diǎn)不多，但是為了讓問(wèn)題變得更為簡(jiǎn)單、直觀，我們畫(huà)另一個(gè)AOE網(wǎng)絡(luò)，如圖2所示。

　　從圖2中我們可以看出，關(guān)鍵路路徑實(shí)際上是從源點(diǎn)到目的地的最長(zhǎng)路徑。為什么是最長(zhǎng)路徑呢?因?yàn)閳D中的某些事件是可以并發(fā)執(zhí)行的。如圖2所示，當(dāng)?shù)竭_(dá)V1后，可以同時(shí)往V2，V3，V4三個(gè)方向走，而V2，V3，V4都有到Vk的路徑，且長(zhǎng)度都為1，并且Vk是終點(diǎn)，則關(guān)鍵路徑是V1->V2->Vk。因?yàn)檫@條路徑最長(zhǎng)，只要這條路徑到目的地Vk時(shí)其他的都已經(jīng)到達(dá)Vk。而在這條關(guān)鍵路徑上的活動(dòng)a2，a5稱(chēng)為關(guān)鍵活動(dòng)。