詹澤梅

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

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

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

文章編號(hào)：1009-3044（2019）31-0215-03

1關(guān)鍵路徑

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

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

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

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

動(dòng)態(tài)規(guī)劃法是求解多階段決策最優(yōu)化問題的一種常用方法。它所解決的問題需要滿足最優(yōu)性原理。最優(yōu)性原理簡單地說就是原問題的最優(yōu)解由各個(gè)子問題的最優(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)性原理，可用動(dòng)態(tài)規(guī)劃法求解。

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

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

3.1算法分析

動(dòng)態(tài)規(guī)劃法求解問題時(shí)首先是劃分子問題。對(duì)于關(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)的最長路徑。動(dòng)態(tài)規(guī)劃函數(shù)可使用上述等式。

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

3.2圖的存儲(chǔ)表示

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

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

求關(guān)鍵路徑之前，首先要求出AOE-網(wǎng)的一個(gè)拓?fù)溆行蛐蛄?，假設(shè)用數(shù)組TopoV存儲(chǔ)拓?fù)溆行蛐蛄兄懈黜旤c(diǎn)的位置下標(biāo)?？砂赐?fù)渑判虻姆椒ㄇ骉opoV數(shù)組值。求解步驟如下：（1）找AOE-網(wǎng)中入度為0的頂點(diǎn)并存儲(chǔ)在數(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ù)組存儲(chǔ)源點(diǎn)到每個(gè)頂點(diǎn)的最長路徑信息，其中MaxLenV[i1記錄源點(diǎn)到拓?fù)湫蛄兄械趇+1個(gè)頂點(diǎn)的最長路徑信息，該頂點(diǎn)在有向圖的十字鏈表的vertices數(shù)組中的位置下標(biāo)為TopoV[i]。頂點(diǎn)的最長路徑信息類型定義如下：

4總結(jié)

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