旅行商问题的几种求解算法比较

旅行商问题的几种求解算法比较

作者:

(xxx学校)

摘要:TSP问题是组合优化领域的经典问题之一,吸引了许多不同领域的研究工作者,包括数学,运筹学,物理,生物和人工智能等领域,他是目前优化领域里的热点.本文从动态规划法,分支界限法,回溯法分别来实现这个题目,并比较哪种更优越,来探索这个经典的NP(Nondeterministic Polynomial)难题.

关键词:旅行商问题 求解算法 比较

一.引言

旅行商问题(Travelling Salesman Problem),是计算机算法中的一个经典的难解问题,已归为NP一完备问题类.围绕着这个问题有各种不同的求解方法,已有的算法如动态规划法,分支限界法,回溯法等,这些精确式方法都是指数级(2n)[2,3]的,根本无法解决目前的实际问题,贪心法是近似方法,而启发式算法不能保证得到的解是最优解,甚至是较好的解释.所以我认为很多问题有快速的算法(多项式算法),但是,也有很多问题是无法用算法解决的.事实上,已经证明很多问题不可能在多项式时间内解决出来.但是,有很多很重要的问题他们的解虽然很难求解出来,但是他们的值却是很容易求可以算出来的.这种事实导致了NP完全问题.NP表示非确定的多项式,意思是这个问题的解可以用非确定性的算法"猜"出来.如果我们有一个可以猜想的机器,我们就可以在合理的时间内找到一个比较好的解.NP-完全问题学习的简单与否,取决于问题的难易程度.因为有很多问题,它们的输出极其复杂,比如说人们早就提出的一类被称作NP-难题的问题.这类问题不像NP-完全问题那样时间有限的.因为NP-问题由上述那些特征,所以很容易想到一些简单的算法――把全部的可行解算一遍.但是这种算法太慢了(通常时间复杂度为O(2^n))在很多情况下是不可行的.现在,没有知道有没有那种精确的算法存在.证明存在或者不存在那种精确的算法这个沉重的担子就留给了新的研究者了,或许你就是成功者.

本篇论文就是想用几种方法来就一个销售商从几个城市中的某一城市出发,不重复地走完其余N—1个城市,并回到原出发点,在所有可能的路径中求出路径长度最短的一条,比较是否是最优化,哪种结果好.

二.求解策略及优化算法

动态规划法解TSP问题

我们将具有明显的阶段划分和状态转移方程的规划称为动态规划,这种动态规划是在研究多阶段决策问题时推导出来的,具有严格的数学形式,适合用于理论上的分析.在实际应用中,许多问题的阶段划分并不明显,这时如果刻意地划分阶段法反而麻烦.一般来说,只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决.所以动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的,相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略.

旅行商问题(TSP问题)其实就是一个最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解.若存在若干个取最优值的解的话,它只取其中的一个.在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算.

关于旅行商的问题,状态变量是gk(i,S),表示从0出发经过k个城市到达i的最短距离,S为包含k个城市的可能集合,动态规划的递推关系为:

gk(i,S)=min[gk-1(j,S\{j})+dji] j属于S,dji表示j-i的距离.

或者我们可以用:

f(S,v)表示从v出发,经过S中每个城市一次且一次,最短的路径.

f(S,v)=min { f(S-{u},u)+dist(v,u) }

u in S

f(V,1)即为所求

2.分支限界法解TSP问题

旅行商问题的解空间是一个排列树,与在子集树中进行最大收益和最小耗费分枝定界搜 索类似,使用一个优先队列,队列中的每个元素 中都包含到达根的路径.

假设我们要寻找的是最小耗费的旅行路径,那可以使用最小耗费分枝定界法.在实现 过程中,使用一个最小优先队列来记录活节点,队列中每个节点的类型为M i n H e a p N o d e.每个节点包括如下区域: x(从1到n的整数排列,其中x [ 0 ] = 1 ),s(

一个整数,使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而 剩余待访问的节点是x [ s + 1 : n - 1 ]),c c(旅行路径前缀,即解空间树中从根

节点到当前节点的耗费),l c o s t(该节点子树中任意叶节点中的最小耗费), r

c o s t(从顶点x [ s : n - 1 ]出发的所有边的最小耗费之和).当类型为M i n H

e a p N o d e ( T )的数据被转换成为类型T时,其结果即为l c o s t的值.分枝定界

算法的代码见程序.

程序首先生成一个容量为1 0 0 0的最小堆,用来表示活节点的最小优先队列.活节点按其l c o s t值从最小堆中取出.接下来,计算有向图中从每个顶点出发的边中 耗费最小的边所具有的耗费M i n O u t.如果某些顶点没有出边,则有向图中没有旅行 路径,搜索终止.如果所有的顶点都有出边,则可以启动最小耗费分枝定界搜索.根的孩子(图1 6 - 5的节点B)作为第一个E-节点,在此节点上,所生成的旅行路径前缀只有一个顶点1,因此s=0, x[0]=1, x[1:n-1]是剩余的顶点(即顶点2 , 3 ,., n ).旅行路径前缀1 的开销为0 ,即c c = 0 ,并且,r c o st=n i=1M i n O u t .在程序中,bestc 给出了当前能找到的最少的耗费值.初始时,由于没有找到任何旅行路径,因此b e s t c的值被设为N o E d g e.

程序旅行商问题的最小耗费分枝定界算法

template

T AdjacencyWDigraph::BBTSP(int v[])

{// 旅行商问题的最小耗费分枝定界算法

// 定义一个最多可容纳1 0 0 0个活节点的最小堆

MinHeap > H(1000);

T *MinOut = new T [n+1];

// 计算MinOut = 离开顶点i的最小耗费边的耗费

T MinSum = 0; // 离开顶点i的最小耗费边的数目

for (int i = 1; i

T Min = NoEdge;

for (int j = 1; j

if (a[j] != NoEdge &&

(a[j]

Min = a[j];

if (Min == NoEdge) return NoEdge; // 此路不通

MinOut = Min;

MinSum += Min;

}

// 把E-节点初始化为树根

MinHeapNode E;

E.x = new int [n];

for (i = 0; i

E.x = i + 1;

E.s = 0; // 局部旅行路径为x [ 1 : 0 ]

E.cc = 0; // 其耗费为0

E.rcost = MinSum;

T bestc = NoEdge; // 目前没有找到旅行路径

// 搜索排列树

while (E.s

if (E.s == n - 2) {// 叶子的父节点

// 通过添加两条边来完成旅行

// 检查新的旅行路径是不是更好

if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && (E.cc +

a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1]

// 找到更优的旅行路径

bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];

E.cc = bestc;

E.lcost = bestc;

E . s + + ;

H . I n s e r t ( E ) ; }

else delete [] E.x;}

else {// 产生孩子

for (int i = E.s + 1; i

if (a[E.x[E.s]][E.x] != NoEdge) {

// 可行的孩子, 限定了路径的耗费

T cc = E.cc + a[E.x[E.s]][E.x];

T rcost = E.rcost - MinOut[E.x[E.s]];

T b = cc + rcost; //下限

if (b

// 子树可能有更好的叶子

// 把根保存到最大堆中

MinHeapNode N;

N.x = new int [n];

for (int j = 0; j

N.x[j] = E.x[j];

N.x[E.s+1] = E.x;

N.x = E.x[E.s+1];

N.cc = cc;

N.s = E.s + 1;

N.lcost = b;

N.rcost = rcost;

H . I n s e r t ( N ) ; }

} // 结束可行的孩子

delete [] E.x;} // 对本节点的处理结束

try {H.DeleteMin(E);} // 取下一个E-节点

catch (OutOfBounds) {break;} // 没有未处理的节点

}

if (bestc == NoEdge) return NoEdge; // 没有旅行路径

// 将最优路径复制到v[1:n] 中

for (i = 0; i

v[i+1] = E.x;

while (true) {//释放最小堆中的所有节点

delete [] E.x;

try {H.DeleteMin(E);}

catch (OutOfBounds) {break;}

}

return bestc;

}

while 循环不断地展开E-节点,直到找到一个叶节点.当s = n - 1时即可说明找到了 一个叶节点.旅行路径前缀是x [ 0 : n - 1 ],这个前缀中包含了有向图中所有的n个顶点.因此s = n - 1的活节点即为一个叶节点.由于算法本身的性质,在叶节点上lco st 和cc 恰好等于叶节点对应的旅行路径的耗费.由于所有剩余的活节点的lcost 值都大于等于从最小堆中取出的第一个叶节点的lcost 值,所以它们并不能帮助我们找到更好的叶节点,因此,当某个叶节点成为E-节点后,搜索过程即终止.

while 循环体被分别按两种情况处理,一种是处理s = n - 2的E-节点,这时,E-节点是某个单独叶节点的父节点.如果这个叶节点对应的是一个可行的旅行路径,并且此旅行路径的耗费小于当前所能找到的最小耗费,则此叶节点被插入最小堆中,否则叶节点被删除,并开始处理下一个E-节点.

其余的E-节点都放在while 循环的第二种情况中处理.首先,为每个E-节点生成它的两个子节点,由于每个E-节点代表着一条可行的路径x [ 0 : s ],因此当且仅当 是有向图的边且x [ i ]是路径x [ s + 1 : n - 1 ]上的顶点时,它的子节点可行.对于每个可行的孩子节点,将边 的耗费加上E.cc 即可得到此孩子节点的路径前缀( x [ 0 : s ],x) 的耗费c c.由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边,因此任何叶节点对应的耗费都不可能小于cc 加上离开各剩余顶点的出边耗费的最小值之和,因而可以把这个下限值作为E-节点所生成孩子的lcost 值.如果新生成孩子的lcost 值小于目前找到的最优旅行路径的耗费b e s t c,则把新生成的孩子加入活节点队列(即最小堆)中.如果有向图没有旅行路径,程序返回N o E d g e;否则,返回最优旅行路径的耗费,而最优旅行路径的顶点序列存储在数组v 中.

3.回朔法解TSP问题

回朔法有"通用解题法"之称,它采用深度优先方式系统地搜索问题的所有解,基本思路是:确定解空间的组织结构之后,从根结点出发,即第一个活结点和第一个扩展结点向纵深方向转移至一个新结点,这个结点成为新的活结点,并成为当前扩展结点.如果在当前扩展结点处不能再向纵深方向转移,则当前扩展结点成为死结点.此时,回溯到最近的活结点处,并使其成为当前扩展结点,回溯到以这种工作方式递归地在解空间中搜索,直到找到所求解空间中已经无活结点为止.

旅行商问题的解空间是一棵排列树.对于排列树的回溯搜索与生成1,2,……, n的所有排列的递归算法Perm类似.设开始时x=[ 1,2,… n ],则相应的排列树由x[ 1:n ]的所有排列构成.旅行商问题的回溯算法

找旅行商回路的回溯算法Backtrack是类Treveling的私有成员函数,TSP是Treveling的友员.TSP(v)返回旅行售货员回路最小费用.整型数组v返回相应的回路.如果所给的图G不含旅行售货员回路,则返回NoEdge.函数TSP所作的工作主要是为调用Backtrack所需要变量初始化.由TSP调用Backtrack(2)搜索整个解空间.

在递归函数Backtrack中,当i = n时,当前扩展结点是排列树的叶结点的父结点.此时,算法检测图G是否存在一条从顶点x[ n-1 ]到顶点x[ n ]的边和一条从顶点x[ n ]到顶点1的边.如果这两条边都存在,则找一条旅行售货员回路.此时,算法还需判断这条回路的费用是否优于已找到的当前最优回路的费用best.如果是,则必须更新当前最优值bestc和当前最优解bestx. 当i

解旅行商售货员问题的回溯法可描述如下:

template

class Traveling {

friend Type TSP(int * *,int [],Type);

private:

void Backtrack(int i);

int n, //图G的顶点数

* x, //当前解

*bestx; //当前最优解

Type * *a, //图G的邻接矩阵

cc, //当前费用

bestc, //当前最优值

NoEdge; //无边际记

};

template

vode Traveling::Backtrack(int i)

{

if(I==n){

if(a[x[n-1]][x[n]]! = NoEdge &&

a[x[n]][1]!= NoEdge &&

(cc + a[x[n-1]][x[n]]+a[x[n]][1]bestc== NoEdge) ){

for(int j=1;j

bestx[j]=x[j];

bestc =cc + a[x[n-1]][x[n]]+ a[x[n]][1];}

}

else {

for(int j=I; j

//是否可进入x[j]子树

if(a[x[i-1]][x[j]]! = NoEdge &&

(cc + a[x[i-1]][x[i]]

bestc == NoEdge

//搜索子数

Swap(x[i],x[j]);

cc += a[x[i-1]][x[i]];

Backtrack(I+1);

cc -= a[x[i-1]][x[i]];

Swap(x[i],x[j]);}

}

}

template

Type TSP(Type * *a,int v[],int n,Type NoEdge)

{

Traveling Y;

//初始化Y

Y.x = new int[n+1];

// 置x为单位排列

for(int i=1;i

Y.x[i] = I;

Y.a=a;

Y.n=n;

Y.bestc = NoEdge;

Y.bestc = v;

Y.cc = 0;

Y. NoEdge = NoEdge;

//搜索x[2:n]的全排列

Y.Backtrack(2);

Delete[] Y.x;

三.三种方法的比较

1.动态规划法和回朔法的比较:

这本来就是两个完全不同的领域,一个是算法领域,一个是数据结构问题.但两者又交叉,又有区别.从本质上讲就是算法与数据结构的本质区别,回朔是一个具体的算法,动态规划是数据结构中的一个概念.动态规划讲究的是状态的转化,以状态为基准,确定算法,动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复.动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解.简单的说就是:动态规划法是从小单元开始积累计算结果.回朔讲究过程的推进与反还,随数据的搜索,标记,确定下一步的行进方向,回朔是去搜索. 如果想要搜索时,发现有很多重复计算,就应该想到用动态规划了.动态规划和搜索都可以解决具有最优子结构的问题,然而动态规划在解决子问题的时候不重复计算已经计算过的子问题,对每个子问题只计算一次;而简单的搜索则递归地计算所有遇到的的子问题.比如一个问题的搜索树具有如下形式:

........A

......./.......B...C

...../.\./.....D...E...F

如果使用一般深度优先的搜索,依次搜索的顺序是A-B-D-E-C-E-F,注意其中节点E被重复搜索了两次;如果每个节点看作是一个子问题的话,节点E所代表的子问题就被重复计算了两次; 但是如果是用动态规划,按照树的层次划分阶段,按照自底向上的顺序,则在第一阶段计算D,E,F;第二阶段计算B,C;第三阶段计算A;这样就没有重复计算子问题E.

搜索法的优点是实现方便,缺点是在子问题有大量的重复的时候要重复计算子问题,效率较低;动态规划虽然效率高,但是阶段的划分和状态的表示比较复杂,另外,搜索的时候只要保存单前的结点;而动态规划则至少要保存上一个阶段的所有节点,比如在动态规划进行到第2阶段的时候,必须把第三阶段的D,E,F三个节点全部保存起来,所以动态规划是用空间换时间. 另外,有一种折衷的办法,就是备忘录法,这是动态规划的一种变形.该方法的思想是:按照一般的搜索算法解决子问题,但是用一个表将所有解决过的子问题保存起来,遇到一个子问题的时候,先查表看是否是已经解决过的,如果已解决过了就不用重复计算.比如搜索上面那棵树,在A-B-D-E的时候,已经将E记录在表里了,等到了A-B-D-E-C的时候,发现E已经被搜索过,就不再搜索E,而直接搜索F,因此备忘录法的搜索顺序是A-B-D-E-C-(跳过E)-F

自底向上的动态规划还有一个缺点,比如对于下面的树:

........A

......./.......B...C......G

...../.\./.\..../.....D...E...F..H...I

如用自底向上的动态规划,各个阶段搜索的节点依次是:

D,E,F,H,I

B,C,G

A

A才是我们最终要解决的问题,可以看到,G,H,I根本与问题A无关,但是动态规划还是将它们也解决了一遍,这就造成了效率降低.而备忘录法则可以避免这种问题,按照备忘录法,搜索的次序仍然是:A-B-D-E-C-(跳过E)-F.备忘录法的优点是实现简单,且在子问题空间中存在大量冗余子问题的时候效率较高;但是要占用较大的内存空间(需要开一个很大的表来记录已经解决的子问题),而且如果用递归实现的话递归压栈出栈也会影响效率;而自底向上的动态规划一般用for循环就可以了.

值得一提的是,用动态规划法来计算旅行商的时间复杂度是指数型的.

2. 分支限界法和回朔法的比较:

分支限界法类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法.但在一般情况下,分支限界与回溯法的求解目标不同.回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解.我们先看一个列子:

设G=(V,E)是一个带权图.图1中各边的费用(权)为一正数.图中的一条周游线是包括V中的每个顶点在内的一条回路.一条周游路线的费用是这条路线上所有边的费用之和.所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线.

给定一个有n个顶点的带权图G,旅行售货员问题要找出图G的费用(权)最小的周游路线.图1是一个4顶点无向带权图.顶点序列1,2,4,3,1;1,3,2,4,1和1,4,3,2,1是该图中3条不同的周游路线.

1 2

5

6 10

4

3 20 4

图1 4顶点带权图

该问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图G的一条周游路线.图1是当n=4时这种树结构的示例.其中从根结点A到叶结点L的路径上边的标号组成一条周游路线1,2,3,4,1.而从根结点到叶结点O的路径则表示周游路线1,3,4,2,1.图G的每一条周游路线都恰好对应解空间树中一条从根结点到叶结点的路径.因此,解空间树中叶结点个数为(n-1)!.

A

1

B

2 3 4

C D E

3 2 4 2 3

F G H I J K

4 3 4 2 3 2

L M N O P Q

图2 旅行售货员问题的解空间树

对于图1中的图G,用回溯法找最小费用周游路线时,从解空间树的根结点A出发,搜索至B,C,F,L.在叶结点L处记录找到的周游路线1,2,3,4,1,该周游路线的费用为59.从叶结点L返回至最近活动结点F处.由于F处已没有可扩展结点,算法又返回到结点C处.结点C成为新扩展结点,由新扩展结点,算法再移至结点G 后又移至结点M,得到周游路线1,2,4,3,1,其费用为66.这个费用不比已有周游路线1,2,3,4,1的费用小.因此,舍弃该结点.算法有依次返回至结点G,C,B.从结点B,算法继续搜索至结点D,H,N.在叶结点N算法返回至结点H,D,然后再从结点D开始继续向纵深搜索至结点O.依次方式算法继续搜索遍整个解空间,最终得到1,3,2,4,1是一条最小费用周游路线.

以上便是回溯法找最小费用周游路线的实列,但如果我们用分支限界法来解的话,会更适合.由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同.回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小消耗优先的方式搜索解空间树T.分支限界法的搜索策略是,在扩展结点处,先生成所有的儿子结点(分支),然后再从当前的活动点表中选择下一个扩展结点.为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上的最优解的分支推进,以便尽快的找出一个最优解.

四.结论:

参考文献:

动态规划 dynamic programming

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

dongtai guihua

动态规划(卷名：自动控制与系统工程)

dynamic programming

研究多段（多步）决策过程最优化问题的一种数学方法，英文缩写DP，是最优控制和运筹学的重要数学工具。为了寻找系统最优决策，可将系统运行过程划分为若干相继的阶段（或若干步），并在每个阶段（或每一步）都作出决策。这种决策过程就称为多段（多步）决策过程。多段决策过程的每一阶段的输出状态就是下一阶段的输入状态。某一阶段所作出的最优决策，对于下一阶段未必是最有利的。多段决策过程的最优化问题必须从系统整体出发，要求各阶段选定的决策序列所构成的策略最终能使目标函数达到极值。

发展简况 20世纪40年代，人们开始研究水力资源的多级分配和库存的多级存储问题。50年代初,美国数学家R.贝尔曼首先提出动态规划的概念，1957年发表《动态规划》一书。在1961、1962年相继出版的第二版和第三版中，又进一步阐明了动态规划的理论和方法。

多段决策过程 又称为多步决策过程(或系统)，是一种适合采用动态规划的过程(或系统)。多段决策过程包括阶段、状态、决策、策略和目标函数 5个要素。①阶段:把所要求解的过程划分成若干相互联系的阶段,并用k表示阶段变量。②状态:表示某一阶段出发位置的状态，它既是上一阶段的输出又是本阶段的输入，并用向量xk表示第k阶段的状态，称为状态变量。③决策:指给定k阶段的状态后,从该状态转移到下一阶段某一状态的选择。用Uk表示第k阶段当状态处于Xk时的决策变量。对于系统的每一个状态，都可以从若干种可能的决策（或控制）中任选一种。选定决策并加以实施，即可引起系统状态的变化。系统的下一阶段状态由现在的状态和决策确定，与过去的历史无关，即系统是无记忆的。④策略：由过程中每一阶段所选决策构成的整个序列，又称为方案。⑤目标函数：策略的目标是使状态变量的某个特定函数的值为最大（或最小）。这个特定函数就是目标函数。使目标函数值为最大（或最小）的策略称为最优策略。图1中求最短路径的例子说明了多段决策过程及其构成要素。图中S是出发点，G是目的地，各边上的数字表示两点间的距离。求从S到G的最短路径和距离数。首先，可将图1划分成四个阶段，然后逆向依次寻求使总的距离为最小的最短路径。先从

第一阶段开始,从C1到G只有一条路线,同样从C2到G也只有一条路线。到了第二阶段，从B1到G有经过C1或C2两条路线，经选择后由B1经C2到G距离最小。如此继续进行下去，就把一个最短路径问题变成了多段决策问题（图2）。最后求得最短路径为SA2B1C2G。

基本原理 动态规划的理论基础是最优化原理和嵌入原理。

最优化原理 一个最优策略，具有如下性质：不论初始状态和初始决策（第一步决策）如何，以第一步决策所形成的阶段和状态作为初始条件来考虑时，余下的决策对余下的问题而言也必构成最优策略。最优化原理体现了动态规划方法的基本思想。

嵌入原理 一个具有已知初始状态和固定步数的过程总可以看作是初始状态和步数均不确定的一族过程中的一个特殊情况。这种把所研究的过程嵌入一个过程族的原理称为嵌入原理。通过研究过程族的最优策略族的共同性质得出一般通解，此通解自然也适用于原来的特殊问题。动态规划的基本方法就是根据嵌入原理把一个多步决策问题化为一系列较简单的一步决策问题，可显著降低数学处理上的难度。

贝尔曼方程 应用最优化原理和嵌入原理可推导出动态规划的基本方程，称为贝尔曼方程。它具有下面的形式：

式中N表示多段决策过程的总段数,F(xk，uk)为标量函数，表示由第k段到第k+1段的过程中基于状态xk和决策uk的性能损失，表示以xk+1为初始状态的后N-(k+1)段分过程的最优性能目标，xk+1=f(xk，uk)是基于第k段的状态 xk和决策uk而得到的第k+1段的状态向量，[·]表示选择决策uk使[·]取极小值。这是一个逆向递推方程。采用迭代法按k=N-1,N-2,…,1,0顺序求解贝尔曼方程，即可得到N段决策过程的最优策略{uk，k=0,1,2,…,N-1}和最优轨线{xk，k=0,1,2,…,N },而最优性能值为J壨(x0)。

对于图1中的例子，贝尔曼方程的形式如下：

经迭代计算后，得

………………………

这就是所求的最短距离。从S到G的最短路径是SA2B1C2G。而A2B1C2G，B1C2G，C2G 则分

别是从A2，B1,C2到G 的最短路径。

贝尔曼方程是关于未知函数（目标函数）的函数方程组。应用最优化原理和嵌入原理建立函数方程组的方法称为函数方程法。在实际运用中要按照具体问题寻求特殊解法。动态规划理论开拓了函数方程理论中许多新的领域。

特点和应用范围 若多阶段决策过程为连续型，则动态规划与变分法处理的问题有共同之处。动态规划原理可用来将变分法问题归结为多阶段决策过程，用动态规划的贝尔曼方程求解。在最优控制理论中动态规划方法比极大值原理更为适用。但动态规划还缺少严格的逻辑基础。60年代，В．Г．沃尔昌斯基对动态规划方法作了数学论证。动态规划方法有五个特点：①在策略变量较多时，与策略穷举法相比可降低维数；②在给定的定义域或限制条件下很难用微分方法求极值的函数，可用动态规划方法求极值；③对于不能用解析形式表达的函数,可给出递推关系求数值解;④动态规划方法可以解决古典方法不能处理的问题，如两点边值问题和隐变分问题等；⑤许多数学规划问题均可用动态规划方法来解决，例如，含有随时间或空间变化的因素的经济问题。投资问题、库存问题、生产计划、资源分配、设备更新、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。

旅行商问题的几种求解算法比较

作者:

(xxx学校)

摘要:TSP问题是组合优化领域的经典问题之一,吸引了许多不同领域的研究工作者,包括数学,运筹学,物理,生物和人工智能等领域,他是目前优化领域里的热点.本文从动态规划法,分支界限法,回溯法分别来实现这个题目,并比较哪种更优越,来探索这个经典的NP(Nondeterministic Polynomial)难题.

关键词:旅行商问题 求解算法 比较

一.引言

旅行商问题(Travelling Salesman Problem),是计算机算法中的一个经典的难解问题,已归为NP一完备问题类.围绕着这个问题有各种不同的求解方法,已有的算法如动态规划法,分支限界法,回溯法等,这些精确式方法都是指数级(2n)[2,3]的,根本无法解决目前的实际问题,贪心法是近似方法,而启发式算法不能保证得到的解是最优解,甚至是较好的解释.所以我认为很多问题有快速的算法(多项式算法),但是,也有很多问题是无法用算法解决的.事实上,已经证明很多问题不可能在多项式时间内解决出来.但是,有很多很重要的问题他们的解虽然很难求解出来,但是他们的值却是很容易求可以算出来的.这种事实导致了NP完全问题.NP表示非确定的多项式,意思是这个问题的解可以用非确定性的算法"猜"出来.如果我们有一个可以猜想的机器,我们就可以在合理的时间内找到一个比较好的解.NP-完全问题学习的简单与否,取决于问题的难易程度.因为有很多问题,它们的输出极其复杂,比如说人们早就提出的一类被称作NP-难题的问题.这类问题不像NP-完全问题那样时间有限的.因为NP-问题由上述那些特征,所以很容易想到一些简单的算法――把全部的可行解算一遍.但是这种算法太慢了(通常时间复杂度为O(2^n))在很多情况下是不可行的.现在,没有知道有没有那种精确的算法存在.证明存在或者不存在那种精确的算法这个沉重的担子就留给了新的研究者了,或许你就是成功者.

本篇论文就是想用几种方法来就一个销售商从几个城市中的某一城市出发,不重复地走完其余N—1个城市,并回到原出发点,在所有可能的路径中求出路径长度最短的一条,比较是否是最优化,哪种结果好.

二.求解策略及优化算法

动态规划法解TSP问题

我们将具有明显的阶段划分和状态转移方程的规划称为动态规划,这种动态规划是在研究多阶段决策问题时推导出来的,具有严格的数学形式,适合用于理论上的分析.在实际应用中,许多问题的阶段划分并不明显,这时如果刻意地划分阶段法反而麻烦.一般来说,只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决.所以动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的,相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略.

旅行商问题(TSP问题)其实就是一个最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解.若存在若干个取最优值的解的话,它只取其中的一个.在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算.

关于旅行商的问题,状态变量是gk(i,S),表示从0出发经过k个城市到达i的最短距离,S为包含k个城市的可能集合,动态规划的递推关系为:

gk(i,S)=min[gk-1(j,S\{j})+dji] j属于S,dji表示j-i的距离.

或者我们可以用:

f(S,v)表示从v出发,经过S中每个城市一次且一次,最短的路径.

f(S,v)=min { f(S-{u},u)+dist(v,u) }

u in S

f(V,1)即为所求

2.分支限界法解TSP问题

旅行商问题的解空间是一个排列树,与在子集树中进行最大收益和最小耗费分枝定界搜 索类似,使用一个优先队列,队列中的每个元素 中都包含到达根的路径.

假设我们要寻找的是最小耗费的旅行路径,那可以使用最小耗费分枝定界法.在实现 过程中,使用一个最小优先队列来记录活节点,队列中每个节点的类型为M i n H e a p N o d e.每个节点包括如下区域: x(从1到n的整数排列,其中x [ 0 ] = 1 ),s(

一个整数,使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而 剩余待访问的节点是x [ s + 1 : n - 1 ]),c c(旅行路径前缀,即解空间树中从根

节点到当前节点的耗费),l c o s t(该节点子树中任意叶节点中的最小耗费), r

c o s t(从顶点x [ s : n - 1 ]出发的所有边的最小耗费之和).当类型为M i n H

e a p N o d e ( T )的数据被转换成为类型T时,其结果即为l c o s t的值.分枝定界

算法的代码见程序.

程序首先生成一个容量为1 0 0 0的最小堆,用来表示活节点的最小优先队列.活节点按其l c o s t值从最小堆中取出.接下来,计算有向图中从每个顶点出发的边中 耗费最小的边所具有的耗费M i n O u t.如果某些顶点没有出边,则有向图中没有旅行 路径,搜索终止.如果所有的顶点都有出边,则可以启动最小耗费分枝定界搜索.根的孩子(图1 6 - 5的节点B)作为第一个E-节点,在此节点上,所生成的旅行路径前缀只有一个顶点1,因此s=0, x[0]=1, x[1:n-1]是剩余的顶点(即顶点2 , 3 ,., n ).旅行路径前缀1 的开销为0 ,即c c = 0 ,并且,r c o st=n i=1M i n O u t .在程序中,bestc 给出了当前能找到的最少的耗费值.初始时,由于没有找到任何旅行路径,因此b e s t c的值被设为N o E d g e.

程序旅行商问题的最小耗费分枝定界算法

template

T AdjacencyWDigraph::BBTSP(int v[])

{// 旅行商问题的最小耗费分枝定界算法

// 定义一个最多可容纳1 0 0 0个活节点的最小堆

MinHeap > H(1000);

T *MinOut = new T [n+1];

// 计算MinOut = 离开顶点i的最小耗费边的耗费

T MinSum = 0; // 离开顶点i的最小耗费边的数目

for (int i = 1; i

T Min = NoEdge;

for (int j = 1; j

if (a[j] != NoEdge &&

(a[j]

Min = a[j];

if (Min == NoEdge) return NoEdge; // 此路不通

MinOut = Min;

MinSum += Min;

}

// 把E-节点初始化为树根

MinHeapNode E;

E.x = new int [n];

for (i = 0; i

E.x = i + 1;

E.s = 0; // 局部旅行路径为x [ 1 : 0 ]

E.cc = 0; // 其耗费为0

E.rcost = MinSum;

T bestc = NoEdge; // 目前没有找到旅行路径

// 搜索排列树

while (E.s

if (E.s == n - 2) {// 叶子的父节点

// 通过添加两条边来完成旅行

// 检查新的旅行路径是不是更好

if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && (E.cc +

a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1]

// 找到更优的旅行路径

bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];

E.cc = bestc;

E.lcost = bestc;

E . s + + ;

H . I n s e r t ( E ) ; }

else delete [] E.x;}

else {// 产生孩子

for (int i = E.s + 1; i

if (a[E.x[E.s]][E.x] != NoEdge) {

// 可行的孩子, 限定了路径的耗费

T cc = E.cc + a[E.x[E.s]][E.x];

T rcost = E.rcost - MinOut[E.x[E.s]];

T b = cc + rcost; //下限

if (b

// 子树可能有更好的叶子

// 把根保存到最大堆中

MinHeapNode N;

N.x = new int [n];

for (int j = 0; j

N.x[j] = E.x[j];

N.x[E.s+1] = E.x;

N.x = E.x[E.s+1];

N.cc = cc;

N.s = E.s + 1;

N.lcost = b;

N.rcost = rcost;

H . I n s e r t ( N ) ; }

} // 结束可行的孩子

delete [] E.x;} // 对本节点的处理结束

try {H.DeleteMin(E);} // 取下一个E-节点

catch (OutOfBounds) {break;} // 没有未处理的节点

}

if (bestc == NoEdge) return NoEdge; // 没有旅行路径

// 将最优路径复制到v[1:n] 中

for (i = 0; i

v[i+1] = E.x;

while (true) {//释放最小堆中的所有节点

delete [] E.x;

try {H.DeleteMin(E);}

catch (OutOfBounds) {break;}

}

return bestc;

}

while 循环不断地展开E-节点,直到找到一个叶节点.当s = n - 1时即可说明找到了 一个叶节点.旅行路径前缀是x [ 0 : n - 1 ],这个前缀中包含了有向图中所有的n个顶点.因此s = n - 1的活节点即为一个叶节点.由于算法本身的性质,在叶节点上lco st 和cc 恰好等于叶节点对应的旅行路径的耗费.由于所有剩余的活节点的lcost 值都大于等于从最小堆中取出的第一个叶节点的lcost 值,所以它们并不能帮助我们找到更好的叶节点,因此,当某个叶节点成为E-节点后,搜索过程即终止.

while 循环体被分别按两种情况处理,一种是处理s = n - 2的E-节点,这时,E-节点是某个单独叶节点的父节点.如果这个叶节点对应的是一个可行的旅行路径,并且此旅行路径的耗费小于当前所能找到的最小耗费,则此叶节点被插入最小堆中,否则叶节点被删除,并开始处理下一个E-节点.

其余的E-节点都放在while 循环的第二种情况中处理.首先,为每个E-节点生成它的两个子节点,由于每个E-节点代表着一条可行的路径x [ 0 : s ],因此当且仅当 是有向图的边且x [ i ]是路径x [ s + 1 : n - 1 ]上的顶点时,它的子节点可行.对于每个可行的孩子节点,将边 的耗费加上E.cc 即可得到此孩子节点的路径前缀( x [ 0 : s ],x) 的耗费c c.由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边,因此任何叶节点对应的耗费都不可能小于cc 加上离开各剩余顶点的出边耗费的最小值之和,因而可以把这个下限值作为E-节点所生成孩子的lcost 值.如果新生成孩子的lcost 值小于目前找到的最优旅行路径的耗费b e s t c,则把新生成的孩子加入活节点队列(即最小堆)中.如果有向图没有旅行路径,程序返回N o E d g e;否则,返回最优旅行路径的耗费,而最优旅行路径的顶点序列存储在数组v 中.

3.回朔法解TSP问题

回朔法有"通用解题法"之称,它采用深度优先方式系统地搜索问题的所有解,基本思路是:确定解空间的组织结构之后,从根结点出发,即第一个活结点和第一个扩展结点向纵深方向转移至一个新结点,这个结点成为新的活结点,并成为当前扩展结点.如果在当前扩展结点处不能再向纵深方向转移,则当前扩展结点成为死结点.此时,回溯到最近的活结点处,并使其成为当前扩展结点,回溯到以这种工作方式递归地在解空间中搜索,直到找到所求解空间中已经无活结点为止.

旅行商问题的解空间是一棵排列树.对于排列树的回溯搜索与生成1,2,……, n的所有排列的递归算法Perm类似.设开始时x=[ 1,2,… n ],则相应的排列树由x[ 1:n ]的所有排列构成.旅行商问题的回溯算法

找旅行商回路的回溯算法Backtrack是类Treveling的私有成员函数,TSP是Treveling的友员.TSP(v)返回旅行售货员回路最小费用.整型数组v返回相应的回路.如果所给的图G不含旅行售货员回路,则返回NoEdge.函数TSP所作的工作主要是为调用Backtrack所需要变量初始化.由TSP调用Backtrack(2)搜索整个解空间.

在递归函数Backtrack中,当i = n时,当前扩展结点是排列树的叶结点的父结点.此时,算法检测图G是否存在一条从顶点x[ n-1 ]到顶点x[ n ]的边和一条从顶点x[ n ]到顶点1的边.如果这两条边都存在,则找一条旅行售货员回路.此时,算法还需判断这条回路的费用是否优于已找到的当前最优回路的费用best.如果是,则必须更新当前最优值bestc和当前最优解bestx. 当i

解旅行商售货员问题的回溯法可描述如下:

template

class Traveling {

friend Type TSP(int * *,int [],Type);

private:

void Backtrack(int i);

int n, //图G的顶点数

* x, //当前解

*bestx; //当前最优解

Type * *a, //图G的邻接矩阵

cc, //当前费用

bestc, //当前最优值

NoEdge; //无边际记

};

template

vode Traveling::Backtrack(int i)

{

if(I==n){

if(a[x[n-1]][x[n]]! = NoEdge &&

a[x[n]][1]!= NoEdge &&

(cc + a[x[n-1]][x[n]]+a[x[n]][1]bestc== NoEdge) ){

for(int j=1;j

bestx[j]=x[j];

bestc =cc + a[x[n-1]][x[n]]+ a[x[n]][1];}

}

else {

for(int j=I; j

//是否可进入x[j]子树

if(a[x[i-1]][x[j]]! = NoEdge &&

(cc + a[x[i-1]][x[i]]

bestc == NoEdge

//搜索子数

Swap(x[i],x[j]);

cc += a[x[i-1]][x[i]];

Backtrack(I+1);

cc -= a[x[i-1]][x[i]];

Swap(x[i],x[j]);}

}

}

template

Type TSP(Type * *a,int v[],int n,Type NoEdge)

{

Traveling Y;

//初始化Y

Y.x = new int[n+1];

// 置x为单位排列

for(int i=1;i

Y.x[i] = I;

Y.a=a;

Y.n=n;

Y.bestc = NoEdge;

Y.bestc = v;

Y.cc = 0;

Y. NoEdge = NoEdge;

//搜索x[2:n]的全排列

Y.Backtrack(2);

Delete[] Y.x;

三.三种方法的比较

1.动态规划法和回朔法的比较:

这本来就是两个完全不同的领域,一个是算法领域,一个是数据结构问题.但两者又交叉,又有区别.从本质上讲就是算法与数据结构的本质区别,回朔是一个具体的算法,动态规划是数据结构中的一个概念.动态规划讲究的是状态的转化,以状态为基准,确定算法,动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复.动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解.简单的说就是:动态规划法是从小单元开始积累计算结果.回朔讲究过程的推进与反还,随数据的搜索,标记,确定下一步的行进方向,回朔是去搜索. 如果想要搜索时,发现有很多重复计算,就应该想到用动态规划了.动态规划和搜索都可以解决具有最优子结构的问题,然而动态规划在解决子问题的时候不重复计算已经计算过的子问题,对每个子问题只计算一次;而简单的搜索则递归地计算所有遇到的的子问题.比如一个问题的搜索树具有如下形式:

........A

......./.......B...C

...../.\./.....D...E...F

如果使用一般深度优先的搜索,依次搜索的顺序是A-B-D-E-C-E-F,注意其中节点E被重复搜索了两次;如果每个节点看作是一个子问题的话,节点E所代表的子问题就被重复计算了两次; 但是如果是用动态规划,按照树的层次划分阶段,按照自底向上的顺序,则在第一阶段计算D,E,F;第二阶段计算B,C;第三阶段计算A;这样就没有重复计算子问题E.

搜索法的优点是实现方便,缺点是在子问题有大量的重复的时候要重复计算子问题,效率较低;动态规划虽然效率高,但是阶段的划分和状态的表示比较复杂,另外,搜索的时候只要保存单前的结点;而动态规划则至少要保存上一个阶段的所有节点,比如在动态规划进行到第2阶段的时候,必须把第三阶段的D,E,F三个节点全部保存起来,所以动态规划是用空间换时间. 另外,有一种折衷的办法,就是备忘录法,这是动态规划的一种变形.该方法的思想是:按照一般的搜索算法解决子问题,但是用一个表将所有解决过的子问题保存起来,遇到一个子问题的时候,先查表看是否是已经解决过的,如果已解决过了就不用重复计算.比如搜索上面那棵树,在A-B-D-E的时候,已经将E记录在表里了,等到了A-B-D-E-C的时候,发现E已经被搜索过,就不再搜索E,而直接搜索F,因此备忘录法的搜索顺序是A-B-D-E-C-(跳过E)-F

自底向上的动态规划还有一个缺点,比如对于下面的树:

........A

......./.......B...C......G

...../.\./.\..../.....D...E...F..H...I

如用自底向上的动态规划,各个阶段搜索的节点依次是:

D,E,F,H,I

B,C,G

A

A才是我们最终要解决的问题,可以看到,G,H,I根本与问题A无关,但是动态规划还是将它们也解决了一遍,这就造成了效率降低.而备忘录法则可以避免这种问题,按照备忘录法,搜索的次序仍然是:A-B-D-E-C-(跳过E)-F.备忘录法的优点是实现简单,且在子问题空间中存在大量冗余子问题的时候效率较高;但是要占用较大的内存空间(需要开一个很大的表来记录已经解决的子问题),而且如果用递归实现的话递归压栈出栈也会影响效率;而自底向上的动态规划一般用for循环就可以了.

值得一提的是,用动态规划法来计算旅行商的时间复杂度是指数型的.

2. 分支限界法和回朔法的比较:

分支限界法类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法.但在一般情况下,分支限界与回溯法的求解目标不同.回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解.我们先看一个列子:

设G=(V,E)是一个带权图.图1中各边的费用(权)为一正数.图中的一条周游线是包括V中的每个顶点在内的一条回路.一条周游路线的费用是这条路线上所有边的费用之和.所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线.

给定一个有n个顶点的带权图G,旅行售货员问题要找出图G的费用(权)最小的周游路线.图1是一个4顶点无向带权图.顶点序列1,2,4,3,1;1,3,2,4,1和1,4,3,2,1是该图中3条不同的周游路线.

1 2

5

6 10

4

3 20 4

图1 4顶点带权图

该问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图G的一条周游路线.图1是当n=4时这种树结构的示例.其中从根结点A到叶结点L的路径上边的标号组成一条周游路线1,2,3,4,1.而从根结点到叶结点O的路径则表示周游路线1,3,4,2,1.图G的每一条周游路线都恰好对应解空间树中一条从根结点到叶结点的路径.因此,解空间树中叶结点个数为(n-1)!.

A

1

B

2 3 4

C D E

3 2 4 2 3

F G H I J K

4 3 4 2 3 2

L M N O P Q

图2 旅行售货员问题的解空间树

对于图1中的图G,用回溯法找最小费用周游路线时,从解空间树的根结点A出发,搜索至B,C,F,L.在叶结点L处记录找到的周游路线1,2,3,4,1,该周游路线的费用为59.从叶结点L返回至最近活动结点F处.由于F处已没有可扩展结点,算法又返回到结点C处.结点C成为新扩展结点,由新扩展结点,算法再移至结点G 后又移至结点M,得到周游路线1,2,4,3,1,其费用为66.这个费用不比已有周游路线1,2,3,4,1的费用小.因此,舍弃该结点.算法有依次返回至结点G,C,B.从结点B,算法继续搜索至结点D,H,N.在叶结点N算法返回至结点H,D,然后再从结点D开始继续向纵深搜索至结点O.依次方式算法继续搜索遍整个解空间,最终得到1,3,2,4,1是一条最小费用周游路线.

以上便是回溯法找最小费用周游路线的实列,但如果我们用分支限界法来解的话,会更适合.由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同.回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小消耗优先的方式搜索解空间树T.分支限界法的搜索策略是,在扩展结点处,先生成所有的儿子结点(分支),然后再从当前的活动点表中选择下一个扩展结点.为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上的最优解的分支推进,以便尽快的找出一个最优解.

四.结论:

参考文献:

动态规划 dynamic programming

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

图片：

dongtai guihua

动态规划(卷名：自动控制与系统工程)

dynamic programming

研究多段（多步）决策过程最优化问题的一种数学方法，英文缩写DP，是最优控制和运筹学的重要数学工具。为了寻找系统最优决策，可将系统运行过程划分为若干相继的阶段（或若干步），并在每个阶段（或每一步）都作出决策。这种决策过程就称为多段（多步）决策过程。多段决策过程的每一阶段的输出状态就是下一阶段的输入状态。某一阶段所作出的最优决策，对于下一阶段未必是最有利的。多段决策过程的最优化问题必须从系统整体出发，要求各阶段选定的决策序列所构成的策略最终能使目标函数达到极值。

发展简况 20世纪40年代，人们开始研究水力资源的多级分配和库存的多级存储问题。50年代初,美国数学家R.贝尔曼首先提出动态规划的概念，1957年发表《动态规划》一书。在1961、1962年相继出版的第二版和第三版中，又进一步阐明了动态规划的理论和方法。

多段决策过程 又称为多步决策过程(或系统)，是一种适合采用动态规划的过程(或系统)。多段决策过程包括阶段、状态、决策、策略和目标函数 5个要素。①阶段:把所要求解的过程划分成若干相互联系的阶段,并用k表示阶段变量。②状态:表示某一阶段出发位置的状态，它既是上一阶段的输出又是本阶段的输入，并用向量xk表示第k阶段的状态，称为状态变量。③决策:指给定k阶段的状态后,从该状态转移到下一阶段某一状态的选择。用Uk表示第k阶段当状态处于Xk时的决策变量。对于系统的每一个状态，都可以从若干种可能的决策（或控制）中任选一种。选定决策并加以实施，即可引起系统状态的变化。系统的下一阶段状态由现在的状态和决策确定，与过去的历史无关，即系统是无记忆的。④策略：由过程中每一阶段所选决策构成的整个序列，又称为方案。⑤目标函数：策略的目标是使状态变量的某个特定函数的值为最大（或最小）。这个特定函数就是目标函数。使目标函数值为最大（或最小）的策略称为最优策略。图1中求最短路径的例子说明了多段决策过程及其构成要素。图中S是出发点，G是目的地，各边上的数字表示两点间的距离。求从S到G的最短路径和距离数。首先，可将图1划分成四个阶段，然后逆向依次寻求使总的距离为最小的最短路径。先从

第一阶段开始,从C1到G只有一条路线,同样从C2到G也只有一条路线。到了第二阶段，从B1到G有经过C1或C2两条路线，经选择后由B1经C2到G距离最小。如此继续进行下去，就把一个最短路径问题变成了多段决策问题（图2）。最后求得最短路径为SA2B1C2G。

基本原理 动态规划的理论基础是最优化原理和嵌入原理。

最优化原理 一个最优策略，具有如下性质：不论初始状态和初始决策（第一步决策）如何，以第一步决策所形成的阶段和状态作为初始条件来考虑时，余下的决策对余下的问题而言也必构成最优策略。最优化原理体现了动态规划方法的基本思想。

嵌入原理 一个具有已知初始状态和固定步数的过程总可以看作是初始状态和步数均不确定的一族过程中的一个特殊情况。这种把所研究的过程嵌入一个过程族的原理称为嵌入原理。通过研究过程族的最优策略族的共同性质得出一般通解，此通解自然也适用于原来的特殊问题。动态规划的基本方法就是根据嵌入原理把一个多步决策问题化为一系列较简单的一步决策问题，可显著降低数学处理上的难度。

贝尔曼方程 应用最优化原理和嵌入原理可推导出动态规划的基本方程，称为贝尔曼方程。它具有下面的形式：

式中N表示多段决策过程的总段数,F(xk，uk)为标量函数，表示由第k段到第k+1段的过程中基于状态xk和决策uk的性能损失，表示以xk+1为初始状态的后N-(k+1)段分过程的最优性能目标，xk+1=f(xk，uk)是基于第k段的状态 xk和决策uk而得到的第k+1段的状态向量，[·]表示选择决策uk使[·]取极小值。这是一个逆向递推方程。采用迭代法按k=N-1,N-2,…,1,0顺序求解贝尔曼方程，即可得到N段决策过程的最优策略{uk，k=0,1,2,…,N-1}和最优轨线{xk，k=0,1,2,…,N },而最优性能值为J壨(x0)。

对于图1中的例子，贝尔曼方程的形式如下：

经迭代计算后，得

………………………

这就是所求的最短距离。从S到G的最短路径是SA2B1C2G。而A2B1C2G，B1C2G，C2G 则分

别是从A2，B1,C2到G 的最短路径。

贝尔曼方程是关于未知函数（目标函数）的函数方程组。应用最优化原理和嵌入原理建立函数方程组的方法称为函数方程法。在实际运用中要按照具体问题寻求特殊解法。动态规划理论开拓了函数方程理论中许多新的领域。

特点和应用范围 若多阶段决策过程为连续型，则动态规划与变分法处理的问题有共同之处。动态规划原理可用来将变分法问题归结为多阶段决策过程，用动态规划的贝尔曼方程求解。在最优控制理论中动态规划方法比极大值原理更为适用。但动态规划还缺少严格的逻辑基础。60年代，В．Г．沃尔昌斯基对动态规划方法作了数学论证。动态规划方法有五个特点：①在策略变量较多时，与策略穷举法相比可降低维数；②在给定的定义域或限制条件下很难用微分方法求极值的函数，可用动态规划方法求极值；③对于不能用解析形式表达的函数,可给出递推关系求数值解;④动态规划方法可以解决古典方法不能处理的问题，如两点边值问题和隐变分问题等；⑤许多数学规划问题均可用动态规划方法来解决，例如，含有随时间或空间变化的因素的经济问题。投资问题、库存问题、生产计划、资源分配、设备更新、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。