新浪博客

旅行售货商问题 (Travelling Salesman Problem)

2015-04-20 21:24阅读：

http://blog.sina.cn/dpool/blog/u/3204563164

旅行售货商问题 <wbr>(Travelling <wbr>Salesman <wbr>Problem) 旅行商问题和中国邮路问题的区别在于旅行商问题所走的图是一个完全连通图，并且所有顶点只通过一次，而中国邮路问题是所有的边至少通过一次。对于规模较小的旅行商问题可以使用动态规划来解决。
首先，自顶向下将问题分解为子问题从而构成解空间。假设初始出发点是节点0，并且定义d(i,V)为节点i经过V中所有节点仅一次最后回到节点0的最小费用。在有4个节点（0，1，2，3）的情况下，问题的解空间如下图：
旅行售货商问题 <wbr>(Travelling <wbr>Salesman <wbr>Problem)

在明确了问题的解空间之后，我们通过自底向上解决子问题，然后组合子问题来解决子问题上一层的问题，这里是一个组合优化的问题。思路明确之后就是代码的实现了，然而如何选择一个恰当的数据结构来表示状态集合V呢？V中是顶点集合，我们必须通过V找到不在V中的顶点，这些不在V中的顶点下一步可能跳转到V，例如V={1，3}，此时2不在V中，并且2可能到达V；除此之外，我们还必须对于每一个不在V中的顶点，例如2，遍历V中的顶点1和3，在遍历的过程中找到花费最小值，这样才能确定子问题d(2,{1,3})的值。因此如何选择V的数据结构是实现该动态规划的关键。用vector肯定操作非常复杂，而且内存占用极大。因此，较为高效的数据结构是用一个二进制串表示节点集合V，如果节点i在V中则将二进制串的第i位置为1，不在V中的节点置为0.如下表所示：
旅行售货商问题 <wbr>(Travelling <wbr>Salesman <wbr>Problem)
在解决了如何表示状态集合之后，就可以写一波代码了。
代码如下：
#include
#include
#include


using namespace std;


int n;


int C[15][15] = {0};
int D[15][1<<15];


void init(){
for(int i=0;i
for(int j=0;j<(1<<(n-1));j++){
D[i][j] = INT_MAX;
}
}
for(int i=1;i
D[i][0] = C[i][0];
}


}


void dp(){
for(int j = 1; j<(1<<n-1); j++){
for(int i = 0; i < n-1; i++){
if(((1<<i)&j) == 0){
for(int k=0; k < n-1; k++){
if(((1<<k)&j) != 0){
D[i+1][j] = min(D[i+1][j], C[i+1][k+1]+D[k+1][((~(1<<k))&j)]);
}
}


}
}
}
for(int k =0; k< n-1;k++){
int all = ((1<<n-1)-1);
if(((1<<k)& all ) != 0){
D[0][all] = min(D[0][all], C[0][k+1]+D[k+1][((~(1<<k))&all)]);
}
}
}


int main(){
cin>>n;
if(n == 1){
cout<<0;
return 0;
}
for(int i=0;i
for(int j=0;j
cin>>C[i][j];
}
init();
dp();
int all = ((1<<n-1)-1);
cout<<D[0][all];
}
最外层的变量j表示状态集合V，下一层的变量i表示不在V中的顶点，在实现的过程中，我们通过将1左移i位然后和状态集合j进行与运算来确定i是不是在V中，即代码（((1<<i)&j) == 0）部分，等于0表示不在V中。最里边一层循环中的变量k用来确定变量k是不是在状态集合V中。因此，对于一个不在V中的节点i,我们循环在V中的节点k，然后用min(D[0][all], C[0][k+1]+D[k+1][((~(1<<k))&j)])来确定最小花费。从而解决子问题d(i,V)。其中((~(1<<k))&j)表示在V中去掉节点k之后剩下的节点集合V'.在实现的过程中，还需注意 <<的优先级最低，并且 &的优先级是低于==的。以上就是动态规划解决旅行商问题的过程。分支限界法好像也可以解决该问题，以后慢慢研究吧。
分支限界法，也就是常说的搜索空间剪枝。在我的理解中一般剪枝是在没有办法使用动态规划的情况下使用的优化方法。是以广度优先或最小耗费(最大效益)优先的方式搜索问题的解空间树。其搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一个结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
旅行售货商问题 <wbr>(Travelling <wbr>Salesman <wbr>Problem)
旅行售货商问题 <wbr>(Travelling <wbr>Salesman <wbr>Problem)
算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：
1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点对应着一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。
2、当s
算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n时，已找到的回路前缀是x[1:n]，它已包含图G的所有n个顶点。因此，当s=n时，相应的扩展结点表示一个叶结点。此时该叶结点所对应的回路的费用等于cc和lcost的和。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所对应的回路是一个最小费用旅行售货员回路，算法可以结束。

我的更多文章

下载客户端阅读体验更佳

APP专享