加载中…
正文 字体大小:

状态压缩dp之TSP

(2011-09-02 18:56:29)
标签:

杂谈

分类: 状态压缩dp
一个n个点的带权的有向图,求一条路径,使得这条路经过每个点恰好一次,并且路径上边的权值和最小(或者最大)。
或者求一条具有这样性质的回路,这是经典的TSP问题。
n <= 16 (重要条件,状态压缩的标志)

状态?
转移?


如何表示一个点集:
由于只有16个点,所以我们用一个整数表示一个点集:
例如:
   5 = 0000000000000101;(2进制表示)
   它的第0位和第2位是1,就表示这个点集里有2个点,分别是点0和点2。
   31 = 0000000000011111; (2进制表示)
   表示这个点集里有5个点,分别是0,1,2,4,5;

所以一个整数i就表示了一个点集;
整数i可以表示一个点集,也可以表示是第i个点。
状态表示:dp[i][j]表示经过点集i中的点恰好一次,不经过其它的点,并且以j点为终点的路径,权值和的最小值,如果这个状态不存在,就是无穷大。

状态转移:
   单点集:状态存在dp[1<<j][j] = 0;否则无穷大。
   非单点集:
   状态存在  dp[i][j] = min(dp[k][s] + w[s][j])
   k表示i集合中去掉了j点的集合,s遍历集合k中的点并且dp[k][s]状态存在, 点s到点j有边存在,w[s][j]表示边的权值。
   状态不存在 dp[i][j]为无穷大。

最后的结果是:
   min( dp[( 1<<n ) – 1][j] ) ( 0 <= j < n );

技巧:利用2进制,使得一个整数表示一个点集,这样集合的操作可以用位运算来实现。例如从集合i中去掉点j:
   k = i & ( ~( 1 << j ) ) 或者
   k = i - ( 1 << j )

#include <cstdio>
#include <queue>
#include <iostream>

using namespace std;

#define ffor(i, n) for(i=0; i<n; ++i)
#define max(a, b) (a>b ? a:b)
#define min(a, b) (a<b ? a:b)

const int inf = 0x7fffffff;
const int n = 4;

int weg[4][4]={
{0, 2, inf, 3},
{inf, 0, 6, 1},
{inf, 2, 0, 4},
{5, 1, 3, 0}
};

struct info{ int s, t; }; // s表示当前集合,t表示集合最后一个元素
queue<info> q; // bfs队列
int d[1<<n][n];

void dp()
{
int i, j;
int x;
info tmp1, tmp;

ffor(i, 1<<n) ffor(j, n) d[i][j]=inf; // 一开始只初始化到(1<<n)-1, 失败
ffor(i, n){
x=1<<i; d[x][i]=0;
tmp.t=i; tmp.s=x; q.push(tmp);
}

while(!q.empty()){
tmp=q.front(); q.pop();
ffor(j, n){ // 可以用邻接表存储,加速
x=1<<j;
// x已经在当前集合,加入失败,或者当前集合的最后元素与x没有边,continue
if((tmp.s)&x || weg[tmp.t][j]==inf) continue;
tmp1.s=(tmp.s)|x; tmp1.t=j;
d[tmp1.s][j]=min(d[tmp.s][tmp.t]+weg[tmp.t][j], d[tmp1.s][j]); // dp, 不解释
q.push(tmp1);
}
}

}

int main()
{
int i, ans=inf;

dp();
ffor(i, n) ans=min(ans, d[(1<<n)-1][i]);
printf("%d\n", ans);

return 0;
}



一开始的代码(恶心):




#include <cstdio>
#include <cstring>

#define ffor(i, n) for(i=0; i<n; ++i)
#define max(a, b) (a>b ? a:b)
#define min(a, b) (a<b ? a:b)

const int inf = 0x7fffffff;
int n = 4;

int weg[4][4]={
{0, 2, inf, 3},
{inf, 0, 6, 1},
{inf, 2, 0, 4},
{5, 1, 3, 0}
};

int d[20][4], q[100];
int head, tail;

void dp()
{
int i, j, k; // ???
int o, p; // ????
int x, y, z; // ??

ffor(i, (1<<n)) ffor(j, n) d[i][j]=inf;
head=tail=0;
ffor(i, n){ x=1<<i; q[tail++]=x; d[x][i]=0;}
while(head<tail){
o=q[head++];
ffor(i, n) {
z=1<<i;
if(o&z) continue;
p=o|z;
ffor(j, n){
x=1<<j;
{
ffor(k, n){
y=1<<k;
if(x==y) continue;
if(x&o && y&p && weg[j][k]!=inf && d[p&(~y)][j]!=inf){
d[p][k]=min(d[p&(~y)][j]+weg[j][k], d[p][k]);
q[tail++]=p;
}
}
}
}
}
}
}

int main()
{
int i, ans=inf;

dp();
ffor(i, n) ans=min(ans, d[(1<<n)-1][i]);
printf("%d\n", ans);

return 0;
}



0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有