基于动态规划的最短路线问题研究

罗鑫 深圳市科学高中

引言：动态规划从1951年提出由贝尔曼先生提出以来，经过几十年的发展，动态规划已经成为运筹学研究中必不可少的一个部分。并广泛应用于管理科学，生产规划等领域。经验表明，应用动态规划法对这些复杂问题进行求解，比起其他方法能取得更好的效果。

最短路线问题则是图和网络中一个非常经典的问题，前人做了很多相关的研究工作，最短路径问题能够涵盖现实生活中的很多方面，比如研究网络图中每个点间的最短路线，或者研究所有的点到某一个点的最短路线。而构成这些网络图的可以是有向图，也可以是无向图，并且还可以带有负的权值。而最短路线的解法也多种多样，有动态规划法，0-1整数规划法，Floyd法等。本文主要对动态规划法怎样求解有向图无负权值的最短路线问题进行研究。

众多研究当中，蒋琦玮等在解决最短路径问题时，将整个求解问题分为若干个阶段，利用贝尔曼方程和状态方程求得当前阶段的最优决策，并将最优决策代入下一个阶段继续求解，如此类推得到最优路径。经过标号法验证，求得的结论正确，此方法思路清晰，也比较简便[1]。孙晓燕等基于运输路径问题建立了一个数学模型，将实际问题分为恰当的阶段，设置状态变量，列出决策变量，根据变量写出具有可分离性和递推性的指标函数，最后利用动态规划函数基本方程求得最优决策[2]。

本文也将利用LINGO对动态规划求解最短路线问题进行建模，并且对比我们手工计算的过程，可以看出软件的计算效率远远高于手工计算。

一、动态规划

动态规划法用于求解最短路径问题的过程如下：

（1）首先是将整个问题恰当地划分为多个阶段，每个阶段都是同类型的子问题，并且定义每个阶段的状态变量，选择合适的决策变量和定义最短路线函数。

（2）多阶段决策中，我们从最后一个阶段开始进行决策的选择，依次递推到第一个阶段。每个阶段的最优决策都要代入到上一个阶段的决策过程中去，递推到第一阶段，即初始阶段的最优决策就是整个问题的最优解。

（3）动态规划的多阶段决策过程和每一个单独的阶段决策过程相联系，这样可以使得求出的最后结果得到的是全局最优值，而不是单独的局部最优值。这也是动态规划法得以广泛应用的一大原因。动态规划的基本形式可以简写成：

其中i表示网络图中的任意一点，j表示从i出发的到终点n的点，1表示是起点，且终点。比如在最后一个阶段中，。i为与终点n相连接的点。表示这一阶段的阶段指标或者叫做这一阶段状态取某一决策时的指标函数值。最短路问题中最优函数取最小值。

二、最短路问题

（一）最短路问题定义

最短路问题常在物流配送问题，运输问题等领域出现，由于时间空间或成本的限制，需要选择一条最优路线，通常就是最短路线，因此，选择最短路线是提高商品货物时空价值的重要环节。关于最短路问题，Dijstra算法和Floyd算法相对来说求解比较简单，而且思路也很清晰。但是随着节点的增加，求解的复杂程度也会大大增加，有着一定的局限性。本文基于动态规划法研究了最短路线的求解问题，并使用了计算机软件LINGO，思路清晰，方法简便且不复杂。如下将会用一个例子来说明这类问题。

（二）最短路问题举例

如下图1所示，A,B,…K,L表示已知的10个城市，连线表示城市间有路直接相通，其中的数字表示路的长度，用Wij表示。假设有一个旅客，要从城市A到L，请求找出一条最短路线。

图1 10个城市之间的道路网络图

分析：可以将该复杂问题分为四个简单的阶段，第一阶段从A到B,C或D，属于一类同质问题，第二阶段到E,F或G，第三阶段到H或K，最后一阶段到达终点G。现在我们从终点L向前递推。

解法：

第四阶段：从H,K到G的最短路分别为8，10，记为f(H)=8，f(K)=10；

第三阶段：与H,K有连线的出发点为E,F,G，从E出发分别经过H,K，至终点L的里程分别为：

WEH+f(H)=18+8=26；

WEK+f(K)=10+10=20;

第二阶段：与E,F,G相连的出发点有B,C,D，从B出发可以经过E,F,G到达终点L的长度为：

故B到终点L的最短路是上述三者的最小值29，可以用f(B)=min{WBj+f(j) }=29表示；从C出发经过E,G到终点L的里程分别为：

故C到终点L的最短路是上述二者的最小值27，可以用f(C)=min{WCj+f(j) }=27表示；从D出发经过E,F,G到终点L的里程分别为：

故D到终点L的最短路是上述三者的最小值3 0，可用f(D)=min{WDj+f(j) }=30表示, j是上一步考察过的三个点E,F,G；

第一阶段，现在的出发点只剩下A，则从A开始可以经过B,C,D到达终点L的路线长度分别为：

故A到L的最短路是上述三者的最小值3 6，可以写成f(A)=min{WAj+f(j) }=36， j是第二阶段考察过的三个点B,C,D。则综上，从A到L的最短路为36。

三、LINGO软件

（一）LINGO软件介绍

LINGO软件是Lindo软件公司开发，用于求解最优化问题的规划工具。它最初开发的目的是用于求解整数规划问题，这是许多其他软件都不能求解的。随着时间的发展，它还可以用于求解其他的规划问题，比如非线性规划等。并且内置多个函数，无需使用者自己开发这些函数，并且能和其他软件进行数据交互，这些特点，使得LINGO成为了广受欢迎的数学计算软件之一。

（二）动态规划的代码求解过程

model：

sets：

cities/A,B,C,D,E,F,G H K L/：FL; !定义10个城市;

roads(cities,cities)/A,B A,C A,D B,E B,F B,G C,E C,G D,E D,F D,G E,H E,K F,H F,K G,H G,K H,L K,L/：W,P;!列举出所有的城市间相连的路径，其中W表示路的长度，P用来存放最短路的路径;

endsets

data：

W=11 9 7 9 16 20 7 7 12 8 10 18 10 15 12 20 22 8 10;

enddata

N=@size(cities);

FL(N)=0;!终点的F值为0;

@for(cities(i)|i#LT#N：FL(i)=@min(roads(i,j)：W(i,j)+FL(j)));!由此，我们可以计算出最短路;

@for(roads(i,j)：P(i,j)=@if(FL(i) #EQ# W(i,j)+FL(j),1,0));

end

由于不是每一个城市到其余的城市都有路直接连通，因此我们需要在代码中特别标明这些连通的路径，得到的矩阵也就是一个稀疏的矩阵。

最后得到的计算结果如下表所示：

表1 求解结果

一行的N在这个问题中表示城市A,B,…,K,L，后面的数字表示城市个数;FL(N)表示出发点到终点的里程，第三列为两个城市之间的路线，后面的数字说明是否最优决策，即指标函数值，如P(D,E)的指标函数值为0，则该路线不是最优决策，不代入下一阶段，而P(D,F)的指标函数值取1，就代入到下一阶段求解。P(A,C)中A为起始点，其指标函数值为1，则可一一推出最佳路线为A→C→E→K→L，FL(A)的值为从A到L的最短里程。

四、结论

本文以动态规划原理为基础对最短路问题进行研究，利用了计算机软件LINGO结合动态规划法建立相关的数学求解模型。该模型思路清晰，方法简便，容易理解。实际生活中有很多类型的最短路问题，很多都转换成多阶段的决策问题，然后再利用动态规划方法进行求解。并且随着计算机的发展，用软件进行计算是一种非常有效的方式。