信息系統(tǒng)項目管理師計算題考點：動態(tài)規(guī)劃-最短路徑問題

最短路徑問題：簡單來說，就是給定—組點，給定每個點間的距離，求出點之間的最短路徑。

其實第4版信息系統(tǒng)項目管理師官方教材中關(guān)于此問題的求解有詳細的介紹，但有些考生可能看不懂，所以本文為大家詳細介紹下，但文字類的描述終究比不上有老師講解，所以講義大家還是看看視頻講解，同時刷題加深理解。

由于第4版信息系統(tǒng)項目管理師官方教材中關(guān)于最短路徑的求解方法為逆序法(624頁)，所以本文也介紹逆序法。

首先，為了解決最短路徑問題，要給出幾個定義（注：以下這些概念性的東西，第一遍看不懂也沒關(guān)系，關(guān)鍵是要會做題，通過做題就能理解了）：

1、階段：常用字母K來表示，比如第4版教程，圖21-2就有4個階段，第一階段共有2條路線即(A,B1)、(A,B2)，第二階段有6條路線，第3階段有6條路線，第4階段有2條路線。

2、狀態(tài)：各階段開始時的出發(fā)點稱作狀態(tài)。描述各階段狀態(tài)的變量，稱作狀態(tài)變量，用S_k表示。

比如第4版教程，圖21-2，第一階段的狀態(tài)為A，第二階段的狀態(tài)為B₁，B₂。所以狀態(tài)變量S₁的集合S₁={A}，S₂的集合是S₂={B₁,B₂,}，S₃的集合是S₃={C₁,C₂,C₃}，S₄的集合是S₄={D₁,D₂} 。

3、決策：當(dāng)各階段的狀態(tài)確定以后，就可以做出不同的決定或選擇，從而確定下一階段的狀態(tài)，這種決定就是決策，表示決策的變量稱為決策變量。常用X_k (S_k )表示第K階段當(dāng)狀態(tài)為S_k時的決策變量。

比如第4版教程，圖21-2中，第二階段如決定從A出發(fā)，即S₁=A，可選擇走B₁或B₂，如果我們選擇從B₁走，則此時的決策變量可表示X₁ (A)=B₁。

4、策略：在各階段決策確定以后，整個問題的決策序列就構(gòu)成了一個策略，用P_1n(S₁)表示。

比如第4版教程，圖21-2中總共可有12個策略，但最優(yōu)策略只有一個。

5、目標函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標稱作目標函數(shù)。

一個n階段的決策過程，從1到n叫作問題的原過程。

目標函數(shù)的最優(yōu)值稱為最優(yōu)目標函數(shù)，最優(yōu)目標函數(shù)記為f_k (S_k)，它表示從第K階段的狀態(tài)Sk出發(fā)采用的最優(yōu)策略。

當(dāng)K=1時，f₁(s₁)就是從初始狀態(tài)S₁到全過程結(jié)束的整體最優(yōu)目標函數(shù)。

比如第4版教程，圖21-2中，目標函數(shù)就是距離。如在第二階段，狀態(tài)為B₂時，f₂(B₂)則表示從B₂到E的最短距離。該圖的最終目標是求f₁(A)，即從A到E的最短距離。

那么怎么求呢？

這時候大家可能會想到，把12條路徑的距離全算出來，從中取一條最短路線，豈不是就能得到答案，這的確是可以的，這種方法叫做窮舉法，但這種計算方法是相當(dāng)煩瑣的，特別當(dāng)路徑比較復(fù)雜時，其計算會變得無法實現(xiàn)。所以可以使用逆序法：

逆序法的基本思路是：從終點E出發(fā)，反向求出倒數(shù)第一階段，倒數(shù)第二階段……直到起點A的各最短子路徑。最終求出從起點到終點的最短路徑。

逆序法求最短路徑步驟(同樣講解的是信息系統(tǒng)項目管理師第4版官方教材【例21-12】，圖21-2)：

【試題】計劃從A地鋪設(shè)一條輸油管道到E地，中間須經(jīng)過三個中間站。第一個中間站可設(shè)在B?或B?,第二個中間站可以有C₁、C₂、C₃三種選擇，第三個中間站可取D₁或D₂。各地之間的距離(單位為km)標在箭線旁邊，如圖21-2所示。要求確定一個方案，使得從A到E的距離最短。

第一步：先考慮最后一個階段的最短子路徑，即從K=4開始

狀態(tài)變量S₄可取兩種狀態(tài)D₁，D₂，它們到E點的距離分別為3和4，這也就是由D₁和D₂到終點E的最短距離，即f₄(D₁)=3，f₄(D₂)=4

第二步：綜合考慮后兩個階段的最短子路徑，即從K=3開始

狀態(tài)變量S₃可取3個值，即C₁，C₂和C₃。

為方便應(yīng)用，規(guī)定用d(S_k，S_k+1)表示由狀態(tài)sk出發(fā)，到達下一階段Sk+1時的兩點距離。

從C₁、C₂或C₃出發(fā)到E，要經(jīng)過中間站D，所以：

可能有些考生還是不了解上面這個公式及計算結(jié)果表示什么，其實大家認真看下前文的說明就能知道了，這里也再給大家用通俗的話說明下：

●f₃(C₁)代表從第3階段，即C-D這一段的C₁這個點出發(fā)到終點

●min代表最小值

●d(C₁,D₁)代表C₁到D₁的距離，f₄(D₁)代表從第4階段，即D到E這一段的D₁這個點出發(fā)到終點，C₁到D₁我們從圖21-2可以得知其距離為5，D₁到E為3，所以d(C₁，D₁)+f₄(D₁)代表C₁→D₁→E這一條路徑，距離為5+3=8，同理可以算出d(C₁，D₂)+f₄(D₂)，即C₁→D₂→E這條路徑的距離為6+4=10，然后取最小的那個值，8<10，所以最后取值8，也就是說從C₁出發(fā)到終點E的最小路徑為C1→D1→E，距離為8km。相應(yīng)的決策為X₃(C₁)=D₁

這樣說明，想必大家能明白了!同理，我們可以求出C₂、C₃到終點E的最短路徑：

這樣我們就可以得到從C₁、C₂、C₃出發(fā)到終點E的最短路徑分別為：

C₁→D₁→E，且f₃(C₁)=8

C₂→D₁→E，且f₃(C₂)=7

C₃→D₂→E，且f₃(C₃)=7

第三步：考慮后三個階段綜合起來的最短子路徑，即從K=2開始

前面我們已經(jīng)算出C₁，C₂，C₃到終點E的最短距離f₃(C₁)，f₃(C₂)， f₃(C₃)。

所以，我們現(xiàn)在要算從B到E的最短距離﹐只需以它們?yōu)榛A(chǔ)﹐分別加上B到達C₁，C₂，C₃的一段距離，比較之后取最短的那個即可。

進行比較，我們就得到了從B到E的最短路徑：

從B₁到E的最短路徑為：B₁→C₂→D₁→E，且f₂(B₁)=13

從B₂到E的最短路徑為：B₂→C₂→D₁→E，且f₂(B₂)=10

第四步：四個階段綜合考慮，即從A到E的距離，即K=1時

由此我們可以得到從A到E的最短路徑為：A→B₂→C₂→D₁→E，距離為14km

【真題演練】

下圖中，從A到E的最短長度是( )(圖中每條邊旁的數(shù)字為該條邊的長度)

A.17

B.18

C.19

D.20

【答案解析】：http://m.xiexiliangjiufa.com/st/42901477.html