詹澤梅

摘要：數(shù)據(jù)結(jié)構(gòu)是計算機(jī)及其相關(guān)專業(yè)的一門重要專業(yè)課。在數(shù)據(jù)結(jié)構(gòu)課程中，關(guān)鍵路徑是一個難點(diǎn)問題。本文首先概述了關(guān)鍵路徑問題，接著介紹了動態(tài)規(guī)劃法，分析其求解關(guān)鍵路徑的可行性，最后重點(diǎn)描述了采用十字鏈表存儲有向圖時的一種基于動態(tài)規(guī)劃法的關(guān)鍵路徑求解算法。

關(guān)鍵詞：關(guān)鍵路徑;動態(tài)規(guī)劃法;十字鏈表;AOE-網(wǎng)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）31-0215-03

1關(guān)鍵路徑

有向無環(huán)圖可用于描述一項工程的施工流程。在有向無環(huán)圖中，既可用頂點(diǎn)表示子工程（又稱活動），也可用有向邊表示子工程。當(dāng)用有向邊表示子工程時，邊上的權(quán)值可表示完成子工程所需的時間、價錢等信息。這種邊表示子工程活動的有向無環(huán)圖就稱為AOE-網(wǎng)（ActiviIy On Edge），即邊表示活動的網(wǎng)。在AOE-網(wǎng)中，有且僅有一個人度為零的頂點(diǎn)，它稱為源點(diǎn)，代表工程的開始點(diǎn);有且僅有一個出度為零的頂點(diǎn)，它稱為匯點(diǎn)，代表工程的結(jié)束點(diǎn)。

對于一項工程，人們通常要估算完成工程所必須的最短時間。當(dāng)在計算機(jī)中用AOE-網(wǎng)描述工程施工流程時，完成工程所必須的最短時間就等于AOE-網(wǎng)中源點(diǎn)到匯點(diǎn)最長路徑的長度。此處路徑長度是指路徑上各活動持續(xù)時間之和，即各有向邊上的權(quán)值之和。路徑長度最長的路徑叫作關(guān)鍵路徑。估算整個工程完成所必須的最短時間，實(shí)際上就是要求AOE-網(wǎng)中的關(guān)鍵路徑。

例如，圖1是一個AOE-網(wǎng)，它表示該工程可分為8個子工程活動?；顒又g的施工先后關(guān)系是：工程一開始就可執(zhí)行活動a1、a2、a3，活動a1完成后可開始執(zhí)行活動a5，活動a3完成后可開始執(zhí)行活動a4、a7，活動a2、a4完成后可開始執(zhí)行活動a6，活動a5、a6完成后可開始執(zhí)行活動a8，活動a7、a8完成后則整個工程完成。有向邊上的權(quán)值表示完成活動所需要的時間。頂點(diǎn)A是工程開始點(diǎn)（源點(diǎn)），頂點(diǎn)F是工程結(jié)束點(diǎn)（匯點(diǎn)）。完成該工程所需要的最短時間等于源點(diǎn)A到匯點(diǎn)F的最長路徑的長度。此AOE-網(wǎng)的最長路徑有兩條：ABEF和ADCEF，路徑長度為10，即完成整個工程的最短時間是10。這兩條路徑都是關(guān)鍵路徑。

2動態(tài)規(guī)劃法

動態(tài)規(guī)劃法是求解多階段決策最優(yōu)化問題的一種常用方法。它所解決的問題需要滿足最優(yōu)性原理。最優(yōu)性原理簡單地說就是原問題的最優(yōu)解由各個子問題的最優(yōu)解構(gòu)成。

關(guān)鍵路徑問題就是求AOE-網(wǎng)中源點(diǎn)到匯點(diǎn)的最長路徑，假定AOE-網(wǎng)的源點(diǎn)s到匯點(diǎn)t的最長路徑是s，x1，X2，…，Xp，t，則路徑s，x1，X2，…，Xp一定是源點(diǎn)s到頂點(diǎn)Xp的最長路徑?？捎梅醋C法證明關(guān)鍵路徑問題滿足最優(yōu)性原理。如果路徑s，x1，x2，…，Xp不是源點(diǎn)s到頂點(diǎn)xp的最長路徑，存在另一條路徑s，Yl，Y2，…，Xp的長度大于路徑s，x1，x2，…，xp的長度，則路徑s，Y1，Y2，…，Xp，t的長度就大于路徑s，x1，X2，…，Xp，t的長度，這就與最初的假設(shè)“假定AOE-網(wǎng)的源點(diǎn)s到匯點(diǎn)t的最長路徑是s，x1，X2，…，Xp，t”相矛盾。所以關(guān)鍵路徑問題滿足最優(yōu)性原理，可用動態(tài)規(guī)劃法求解。

動態(tài)規(guī)劃法將待求解問題分解成為若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段。該方法的求解過程通?？煞譃槿齻€階段：劃分子問題、設(shè)定動態(tài)規(guī)劃函數(shù)、計算各個子問題并填寫表格。

3基于動態(tài)規(guī)劃法的關(guān)鍵路徑算法

3.1算法分析

動態(tài)規(guī)劃法求解問題時首先是劃分子問題。對于關(guān)鍵路徑問題如何劃分子問題呢？假設(shè)我們用Cxy表示有向邊上的權(quán)值，用Dis（s，v）表示源點(diǎn)s到頂點(diǎn)v的最長路徑長度。假設(shè)頂點(diǎn)u是頂點(diǎn)v的前驅(qū)頂點(diǎn)，則源點(diǎn)s到頂點(diǎn)v的最長路徑長度應(yīng)為Csv和Dis（s，u）+Cuv中的最大值。即有以下等式成立。

由于源點(diǎn)s到頂點(diǎn)v的最長路徑與源點(diǎn)s到頂點(diǎn)v的前驅(qū)頂點(diǎn)u的最長路徑相關(guān)，所以子問題可設(shè)定為求源點(diǎn)到某頂點(diǎn)的最長路徑。動態(tài)規(guī)劃函數(shù)可使用上述等式。

動態(tài)規(guī)劃法的第三個步驟是計算各子問題并填表。此問題中就是要計算源點(diǎn)到各頂點(diǎn)的最長路徑。對于AOE-網(wǎng)中的各頂點(diǎn)，應(yīng)按什么順序求解子問題呢？顯然前驅(qū)頂點(diǎn)的最長路徑應(yīng)先求，所以應(yīng)按照圖中有向邊指示的先后順序求各頂點(diǎn)的最長路徑，對于沒有先后順序的頂點(diǎn)可按任意順序求解。換句話就是要按圖中頂點(diǎn)拓?fù)溆行蛐蛄兄械南群箜樞蚯蠼庠袋c(diǎn)到各頂點(diǎn)的最長路徑。

3.2圖的存儲表示

關(guān)鍵路徑算法的設(shè)計與圖的存儲結(jié)構(gòu)密切相關(guān)。本問題中的有向圖如何存儲呢？由于在求源點(diǎn)到各頂點(diǎn)的最長路徑時，要按拓?fù)溆行蛐蛄兄械捻旤c(diǎn)順序求，那么就要對有向圖中頂點(diǎn)進(jìn)行拓?fù)渑判颉Ｔ谕負(fù)渑判蜻^程中，需要知道從各頂點(diǎn)出去的有向邊（弧），所以在圖的存儲結(jié)構(gòu)中，應(yīng)能方便找到從各頂點(diǎn)出去的弧。又由于源點(diǎn)到某頂點(diǎn)v的最長路徑與源點(diǎn)到v的前驅(qū)頂點(diǎn)的最長路徑相關(guān)，所以在圖的存儲結(jié)構(gòu)中，要能方便找到任意一頂點(diǎn)的前驅(qū)頂點(diǎn)。十字鏈表存儲結(jié)構(gòu)能很好地滿足這兩個要求，所以我們以十字鏈表作為本問題中圖的存儲結(jié)構(gòu)。圖1所示有向圖的十字鏈表存儲結(jié)構(gòu)如圖2所示。

3.3關(guān)鍵路徑算法

求關(guān)鍵路徑之前，首先要求出AOE-網(wǎng)的一個拓?fù)溆行蛐蛄校僭O(shè)用數(shù)組TopoV存儲拓?fù)溆行蛐蛄兄懈黜旤c(diǎn)的位置下標(biāo)?？砂赐?fù)渑判虻姆椒ㄇ骉opoV數(shù)組值。求解步驟如下：（1）找AOE-網(wǎng)中入度為0的頂點(diǎn)并存儲在數(shù)組TopoV中;（2）刪除以該頂點(diǎn)為弧尾的弧。重復(fù)執(zhí)行（1）（2）兩步，直至找不到人度為0的頂點(diǎn)為止。

然后按算法1求AOE-網(wǎng)的源點(diǎn)到各頂點(diǎn)的最長路徑信息，最后按算法2輸出關(guān)鍵路徑和其長度。

算法1中MaxLenV數(shù)組存儲源點(diǎn)到每個頂點(diǎn)的最長路徑信息，其中MaxLenV[i1記錄源點(diǎn)到拓?fù)湫蛄兄械趇+1個頂點(diǎn)的最長路徑信息，該頂點(diǎn)在有向圖的十字鏈表的vertices數(shù)組中的位置下標(biāo)為TopoV[i]。頂點(diǎn)的最長路徑信息類型定義如下：

4總結(jié)

動態(tài)規(guī)劃法是求解最優(yōu)化問題的一種常用算法設(shè)計技術(shù)。關(guān)鍵路徑問題的解滿足最優(yōu)性原理，因此可用動態(tài)規(guī)劃法求解。本文在有向圖采用十字鏈表存儲方式下，設(shè)計了一種基于動態(tài)規(guī)劃法的關(guān)鍵路徑算法，該算法能正確的輸出源點(diǎn)到匯點(diǎn)的關(guān)鍵路徑及其長度。