信息系统项目管理师计算题考点：动态规划-最短路径问题

最短路径问题：简单来说，就是给定—组点，给定每个点间的距离，求出点之间的最短路径。

其实第4版信息系统项目管理师官方教材中关于此问题的求解有详细的介绍，但有些考生可能看不懂，所以本文为大家详细介绍下，但文字类的描述终究比不上有老师讲解，所以讲义大家还是看看视频讲解，同时刷题加深理解。

由于第4版信息系统项目管理师官方教材中关于最短路径的求解方法为逆序法(624页)，所以本文也介绍逆序法。

首先，为了解决最短路径问题，要给出几个定义（注：以下这些概念性的东西，第一遍看不懂也没关系，关键是要会做题，通过做题就能理解了）：

1、阶段：常用字母K来表示，比如第4版教程，图21-2就有4个阶段，第一阶段共有2条路线即(A,B1)、(A,B2)，第二阶段有6条路线，第3阶段有6条路线，第4阶段有2条路线。

2、状态：各阶段开始时的出发点称作状态。描述各阶段状态的变量，称作状态变量，用S_k表示。

比如第4版教程，图21-2，第一阶段的状态为A，第二阶段的状态为B₁，B₂。所以状态变量S₁的集合S₁={A}，S₂的集合是S₂={B₁,B₂,}，S₃的集合是S₃={C₁,C₂,C₃}，S₄的集合是S₄={D₁,D₂} 。

3、决策：当各阶段的状态确定以后，就可以做出不同的决定或选择，从而确定下一阶段的状态，这种决定就是决策，表示决策的变量称为决策变量。常用X_k (S_k )表示第K阶段当状态为S_k时的决策变量。

比如第4版教程，图21-2中，第二阶段如决定从A出发，即S₁=A，可选择走B₁或B₂，如果我们选择从B₁走，则此时的决策变量可表示X₁ (A)=B₁。

4、策略：在各阶段决策确定以后，整个问题的决策序列就构成了一个策略，用P_1n(S₁)表示。

比如第4版教程，图21-2中总共可有12个策略，但最优策略只有一个。

5、目标函数：用于衡量所选定策略优劣的数量指标称作目标函数。

一个n阶段的决策过程，从1到n叫作问题的原过程。

目标函数的最优值称为最优目标函数，最优目标函数记为f_k (S_k)，它表示从第K阶段的状态Sk出发采用的最优策略。

当K=1时，f₁(s₁)就是从初始状态S₁到全过程结束的整体最优目标函数。

比如第4版教程，图21-2中，目标函数就是距离。如在第二阶段，状态为B₂时，f₂(B₂)则表示从B₂到E的最短距离。该图的最终目标是求f₁(A)，即从A到E的最短距离。

那么怎么求呢？

这时候大家可能会想到，把12条路径的距离全算出来，从中取一条最短路线，岂不是就能得到答案，这的确是可以的，这种方法叫做穷举法，但这种计算方法是相当烦琐的，特别当路径比较复杂时，其计算会变得无法实现。所以可以使用逆序法：

逆序法的基本思路是：从终点E出发，反向求出倒数第一阶段，倒数第二阶段……直到起点A的各最短子路径。最终求出从起点到终点的最短路径。

逆序法求最短路径步骤(同样讲解的是信息系统项目管理师第4版官方教材【例21-12】，图21-2)：

【试题】计划从A地铺设一条输油管道到E地，中间须经过三个中间站。第一个中间站可设在B₁或B₂,第二个中间站可以有C₁、C₂、C₃三种选择，第三个中间站可取D₁或D₂。各地之间的距离(单位为km)标在箭线旁边，如图21-2所示。要求确定一个方案，使得从A到E的距离最短。

第一步：先考虑最后一个阶段的最短子路径，即从K=4开始

状态变量S₄可取两种状态D₁，D₂，它们到E点的距离分别为3和4，这也就是由D₁和D₂到终点E的最短距离，即f₄(D₁)=3，f₄(D₂)=4

第二步：综合考虑后两个阶段的最短子路径，即从K=3开始

状态变量S₃可取3个值，即C₁，C₂和C₃。

为方便应用，规定用d(S_k，S_k+1)表示由状态sk出发，到达下一阶段Sk+1时的两点距离。

从C₁、C₂或C₃出发到E，要经过中间站D，所以：

可能有些考生还是不了解上面这个公式及计算结果表示什么，其实大家认真看下前文的说明就能知道了，这里也再给大家用通俗的话说明下：

●f₃(C₁)代表从第3阶段，即C-D这一段的C₁这个点出发到终点

●min代表最小值

●d(C₁,D₁)代表C₁到D₁的距离，f₄(D₁)代表从第4阶段，即D到E这一段的D₁这个点出发到终点，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₁出发到终点E的最小路径为C1→D1→E，距离为8km。相应的决策为X₃(C₁)=D₁

这样说明，想必大家能明白了!同理，我们可以求出C₂、C₃到终点E的最短路径：

这样我们就可以得到从C₁、C₂、C₃出发到终点E的最短路径分别为：

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

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

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

第三步：考虑后三个阶段综合起来的最短子路径，即从K=2开始

前面我们已经算出C₁，C₂，C₃到终点E的最短距离f₃(C₁)，f₃(C₂)， f₃(C₃)。

所以，我们现在要算从B到E的最短距离﹐只需以它们为基础﹐分别加上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的最短长度是( )(图中每条边旁的数字为该条边的长度)

A.17

B.18

C.19

D.20

【答案解析】：https://www.cnitpm.com/st/42901477.html