旅行商问题的几种求解算法比较
作者:
(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 <= n; i++) {
T Min = NoEdge;
for (int j = 1; j <= n; j++)
if (a[j] != NoEdge &&
(a[j] < Min || Min == NoEdge))
Min = a[j];
if (Min == NoEdge) return NoEdge; // 此路不通
MinOut = Min;
MinSum += Min;
}
// 把E-节点初始化为树根
MinHeapNode E;
E.x = new int [n];
for (i = 0; i < n; i++)
E.x = i + 1;
E.s = 0; // 局部旅行路径为x [ 1 : 0 ]
https://www.doczj.com/doc/d115704312.html, = 0; // 其耗费为0
E.rcost = MinSum;
T bestc = NoEdge; // 目前没有找到旅行路径
// 搜索排列树
while (E.s < n - 1) {// 不是叶子
if (E.s == n - 2) {// 叶子的父节点
// 通过添加两条边来完成旅行
// 检查新的旅行路径是不是更好
if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && (https://www.doczj.com/doc/d115704312.html, + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc == NoEdge)) {
// 找到更优的旅行路径
bestc = https://www.doczj.com/doc/d115704312.html, + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];
https://www.doczj.com/doc/d115704312.html, = 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 < n; i++)
if (a[E.x[E.s]][E.x] != NoEdge) {
// 可行的孩子, 限定了路径的耗费
T cc = https://www.doczj.com/doc/d115704312.html, + a[E.x[E.s]][E.x];
T rcost = E.rcost - MinOut[E.x[E.s]];
T b = cc + rcost; //下限
if (b < bestc || bestc == NoEdge) {
// 子树可能有更好的叶子
// 把根保存到最大堆中
MinHeapNode N;
N.x = new int [n];
for (int j = 0; j < n; j++)
N.x[j] = E.x[j];
N.x[E.s+1] = E.x;
N.x = E.x[E.s+1];
https://www.doczj.com/doc/d115704312.html, = 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 < n; 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 ]上的顶点时,它的子节点可行.对于每个可行的孩子节点,将边的耗费加上https://www.doczj.com/doc/d115704312.html, 即可得到此孩子节点的路径前缀( 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 < n时,当前扩展结点位于排列树的第i–1 层.图G中存在从顶点x[ i-1 ]到顶点x[ i ]的边时,x[ 1:i ]构成图G的一条路径,且当x[ 1:i ]的费用小于当前最优值时,算法进入排列树的第I 层.否则将剪去相应的子树.算法中用变量cc记录当前路径x[ 1: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<=n;j++)
bestx[j]=x[j];
bestc =cc + a[x[n-1]][x[n]]+ a[x[n]][1];}
}
else {
for(int j=I; j<=n;j++)
//是否可进入x[j]子树
if(a[x[i-1]][x[j]]! = NoEdge &&
(cc + a[x[i-1]][x[i]]< bestc||
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<=n;i++)
Y.x[i] = I;
Y.a=a;
Y.n=n;
Y.bestc = NoEdge;
Y.bestc = v;
https://www.doczj.com/doc/d115704312.html, = 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年代，В．Г．沃尔昌斯基对动态规划方法作了数学论证。动态规划方法有五个特点：①在策略变量较多时，与策略穷举法相比可降低维数；②在给定的定义域或限制条件下很难用微分方法求极值的函数，可用动态规划方法求极值；③对于不能用解析形式表达的函数,可给出递推关系求数值解;④动态规划方法可以解决古典方法不能处理的问题，如两点边值问题和隐变分问题等；⑤许多数学规划问题均可用动态规划方法来解决，例如，含有随时间或空间变化的因素的经济问题。投资问题、库存问题、生产计划、资源分配、设备更新、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。
旅行商问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，简称ＴＳＰ）是一个著名的组合优化问题：给定ｎ个城市，有一个旅行商从某一城市出发，访问每个城市各一次后再回到原出发城市，要求找出的巡回路径最短。如果用图论来描述，那就是已知带权图Ｇ＝ （Ｃ，Ｌ），寻出总权值最小的Ｈａｍｉｌｔｏｎ圈。其中Ｃ＝｛ｃ１，ｃ２，…，ｃｎ｝表示ｎ个城市的集合，Ｌ＝｛ｌｉｊ｜ｃｉ，ｃｊ∈Ｃ｝是集合Ｃ中元素（城市）两两连接的集合，每一条边ｌｉｊ，都存在与之对应的权值ｄｉｊ，实际应用中ｄｉｊ可以表示距离、费用、时间、油量等。 ＴＳＰ的描述虽然简单， 解决起来却很困难。最简单思路是用穷举法把所有可能的巡回路径全部列出来，最短的一个就是最优解，但这样只能处理很小规模的问题。旅行商问题属于 ＮＰ－ｃｏｍｐｌｅｔｅ问题， 是ＮＰ（ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃｐｏｌｙ－ｎｏｍｉｎａｌ）问题中最难的一类，不能在多项式时间内求解。如果有ｎ座城市，那么巡游路径共有（ｎ－１）！／２条，计算的时间和（ｎ－１）！成正比。当 城市数ｎ＝２０，巡回路径有１．２×１０１８种，ｎ＝１００， 巡回路径就有多达４．６×１０１５５种，而据估计宇宙中基本粒子数“仅仅只有”１０８７个。 尽管如此，随着算法研究的逐步深入和计算机技术飞速提高，对ＴＳＰ问题的研究不断取得进展。７０年来，被征服的ＴＳＰ规模从几十个城市增加到上万个城市。目前的最高记录是在２００４年５月，找到的巡游瑞典２４９７８个城镇的最优路径 （ｓｗ２４９７８）， 花费了８４．８个ＣＰＵ年。图１展示了ＴＳＰ的研究进展，最近的二三十年时间里，被攻克的ＴＳＰ规模高速增长，差不多是每十年增加一个数量级。照这样发展下去的话，再过２０年就能解决上百万个城市的ＴＳＰ，有专家甚至已经为此准备好了数据：全球１９０，４７１１个城市的坐标。当然，能不能达到这 个目标，有赖于未来计算技术的发展。 图１ＴＳＰ的发展 字母后面的数字表示城市数，“ｓｗ２４９７８”就是瑞典的 ２４９７８个城镇。 一、应用 旅行商问题具有重要的实际意义和工程背景。它一开始 是为交通运输而提出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等。实际上其应用范围扩展到了许多其他领域，下面举几个实例。 印制电路板转孔是ＴＳＰ应用的经典例子，在一块电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。把这个问题转化为ＴＳＰ，孔相当于城市，孔到孔之间的移动时间就是距离。 为了避免大气干扰，使光学系统达到其衍射极限分辨率，欧美发达国家提出发展空间光干涉仪和综合孔径望远镜的计划。美国航空航天局有一个卫星群组成空间天文台（Ｓｐａｃｅ－ｂａｓｅｄＯｂｓｅｒｖａｔｏｒｉｅｓ）的计划， 用来探测宇宙起源和外星智慧生命。欧洲空间局也有类似的Ｄａｒｗｉｎ计划。对天体成像的时候，需要对两颗卫星的位置进行调整，如何控制卫星，使消耗的燃料最少，可以用ＴＳＰ来求解。这里把天体看作城市，距离就是卫星移动消耗的燃料。 美国国家卫生协会在人类基因排序工作中用ＴＳＰ方法绘制放射性杂交图。把ＤＮＡ片断作为城市，它们之间的相似程度作为城市间的距离。法国科学家已经用这种办法作出了老鼠的放射性杂交图。 此外，旅行商问题还有电缆和光缆布线、晶体结构分析、数据串聚类等多种用途。更重要的是，它提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分配问题、车间调度问题，和ＴＳＰ同属ＮＰ－ｃｏｍｐｌｅｔｅ类，它们都是同等难度的，如果其中一个能用多项式确定性算法解决，那么其他所有的ＮＰ－ｃｏｍｐｌｅｔｅ类问题也能用多项式确定性算法解决。很多方法本来是从ＴＳＰ发展起来的，后来推广到其他ＮＰ－ｃｏｍｐｌｅｔｅ类问题上去。 二、ＴＳＰ求解方法 求解旅行商问题的方法可以分为两大类，一类是精确算法，目的是要找到理论最优解；另一类是近似算法，不强求最优解，只要找到“足够好”的满意解就可以了。 （一）精确算法 如前面所述，穷举法和全局搜索算法属于精确算法，但 旅行商问题概述 郭靖扬 （电子科技大学光电信息学院， 四川成都６１００５４） 【摘要】旅行商问题是组合优化的经典问题，应用广泛，而且长期以来被作为ＮＰ－ｃｏｍｐｌｅｔｅ问题的理想研究平台。文章介绍 了旅行商问题的基础知识、应用，以及常用的求解方法。 【关键词】旅行商问题；组合优化；ＮＰ－ｃｏｍｐｌｅｔｅ；ｋ－ｏｐｔ；智能算法【中图分类号】ＴＰ１８２【文献标识码】Ａ【文章编号】１００８－１１５１（２００６）０８－０２２９－０２大众科技 ＤＡＺＨＯＮＧＫＥＪＩ２００６年第８期（总第９４期） Ｎｏ．８，２００６ （ＣｕｍｕｌａｔｉｖｅｌｙＮｏ．９４） 【收稿日期】２００６－０３－１８【作者简介】郭靖扬（１９８０－），四川宜宾人，电子科技大学光电信息学院硕士研究生。 ２２９－－
#include { /*if(mincost <= cost[cur][i]+cost[i][start]) { continue; //其作用为结束本次循环。即跳出循环体中下面尚未执行的语句。区别于break } */ visit[i] = 1; //递归调用时，防止重复调用 int value = cost[cur][i] + imin(num-1, i); if(mincost > value) { mincost = value; } visit[i] = 0;//本次递归调用完毕，让下次递归调用 } } return mincost; } int main() { int i,j; // int k,e,w; n=4; int cc[4][4]={{0,10,15,20}, {5,0,9,10}, {6,13,0,12}, {8,8,9,0}}; for(i=0; i T S P问题算法分析集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289- 算法第二次大作业 TSP问题算法分析 021251班 王昱（02125029） 一．问题描述 “TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。 TSP问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。 二．算法描述 2.1分支界限法 2.1.1算法思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 2.1.2算法设计说明 设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down,up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。 对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即： bound(x1)≥bound(x1,x2)≥…≥bound(x1,…,xn) 若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。 再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。 直到一个叶子结点时的可行解X=(x1,…,xn)，及目标函数值 bound(x1,…,xn)。 2.2A*算法 算法思想 对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值，并有 f*(n)=g*(n)+h*(n)。 摘要 本文分析比较了tsp问题的动态规划算法，分支界限法，近似等算法。分析了旅行商问题的时间度特点，针对启发式算法求解旅行商问题中存在的一些问题提出了改进算法。此算法将群体分为若干小子集，并用启发式交叉算子，以较好利用父代个体的有效信息，达到快速收敛的效果，实验表明此算法能提高寻优速度，解得质量也有所提高。 关键词：旅行商问题TSP Abstract this paper analyzed the time complexity of traveling salesman problem,then put forward some imprivement towards the genetic algorithm for solving this problen: divding the population into some small parent individual well.so it can quickly get into convergence, the experimental result indicates the impwoved algorithm can accelerate the apeed of finding solution and improve the precision. Keywords traveling salesman problem; genetic algorithm; subset; henristic crossover operator 目录 1、摘要--------------------------------------------------------------1 2、Abstract---------------------------------------------------------1 3、Tsp问题的提法------------------------------------------------2 4、回溯法求Tsp问题--------------------------------------------3 5、分支限界法求Tsp问题--------------------------------------7 6、近似算法求解Tsp问题-------------------------------------10 7、动态规划算法解Tsp问题----------------------------------12 《算法设计与课程设计》 题目： TSP问题多种算法策略 班级：计算机技术14 学号： 姓名： 指导老师： 完成日期： 成绩： 旅行商问题的求解方法 摘要 旅行商问题（TSP 问题）时是指旅行家要旅行n 个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用动态规划法、贪心法、回溯法和深度优先搜索策略求解TSP 问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。 关键字：旅行商问题；动态规划法；贪心法；回溯法；深度优先搜索策略 1引言 旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP 的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP 的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法、回溯法和深度优先搜索策略。 2正文 2.1动态规划法 2.1.1动态规划法的设计思想 动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。 2.1.2 TSP 问题的动态规划函数 假设从顶点i 出发，令'(,)d i V 表示从顶点i 出发经过'V 中各个顶点一次且仅一次，最后回到出发点i 的最短路径长度，开始时，{}'V V i =-，于是，TSP 问 旅行商问题的几种求解算法比较 作者: (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 个城市的可能集合,动态规划的递推关系为: 用遗传算法解决旅行商问题 姓名：王晓梅 学号：1301281 班级：系统工程6班 一、问题背景 有一个销售员，要到n 个城市推销商品，他要找出一个包含所有n 个城市的具有最短路程的环路。 现在假设有10个城市，他们之间的距离如下。 { 0, 107, 241, 190, 124, 80, 316, 76, 152, 157}, { 107, 0, 148, 137, 88, 127, 336, 183, 134, 95}, { 241, 148, 0, 374, 171, 259, 509, 317, 217, 232}, { 190, 137, 374, 0, 202, 234, 222, 192, 248, 42}, { 124, 88, 171, 202, 0, 61, 392, 202, 46, 160}, { 80, 127, 259, 234, 61, 0, 386, 141, 72, 167}, { 316, 336, 509, 222, 392, 386, 0, 233, 438, 254}, { 76, 183, 317, 192, 202, 141, 233, 0, 213, 188}, { 152, 134, 217, 248, 46, 72, 438, 213, 0, 206}, { 157, 95, 232, 42, 160, 167, 254, 188, 206, 0} 将这10个城市分别编码为0,1,2,3,4,5,6,7,8,9。要求走完这10个城市，目标是使走的距离最短。 二、建立模型 ),...,1,(1) ,...,1,(1. .)(min 11 11n j j i n i j i t s j i n j ij n i ij ij n i n j ij x x d x =≠==≠=≠∑∑∑∑==== 旅行商问题的求解方法 摘要 旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用蛮力法、动态规划法、贪心法和分支限界法求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。 关键字：旅行商问题；动态规划法；贪心法；分支限界法 1引言 旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法，并对蛮力法做简单介绍，用以比较。 2正文 2.1蛮力法 2.1.1蛮力法的设计思想 蛮力法所依赖的基本技术是扫描技术，即采用一定的策略将待求解问题的所有元素一次处理一次，从而找出问题的解。一次处理所有元素的是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。在基本的数据结构中，一次处理每个元素的方法是遍历。 2.1.2算法讨论 用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。如对于图1，我们求解过程如下： （1）路径：1->2->3->4->1；路径长度：18； （2）路径：1->2->4->3->1；路径长度：11； （3）路径：1->3->2->4->1；路径长度：23； （4）路径：1->3->4->2->1；路径长度：11；TSP问题算法分析
Tsp问题的几种算法的分析
算法报告-旅行商问题模板讲解
旅行商问题的几种求解算法比较
用遗传算法解决旅行商问题
算法论文：旅行商问题的求解方法(动态规划法和贪心法)
相关主题
文本预览