TSP问题即最短旅行商问题,在给定的带权无向图中求得一条最短的哈密顿路.这个问题我们在离散数学课上有讲过,是NPhard但是数据范围较小的时候我们还是可以通过一些算法求得近似解.白书上介绍了一种很经典的状压dp求解方法.
dp[s][v],s表示一个点的集合,这个集合可以是DAG中所有点的子集,这里我们用s来代表所有已经到过的点,用dp[s][v](v∈s)代表从v点出发经过除s以外的所有点后回到点1的最小代价.那么可以推出转移方程dp[s][v] = min ( dp[s][v] , dp[s ∪ u][u] + Map[v][u]) 这个转移方程的意思是枚举所有点找到一个点u使得:v到u的距离 加上 从u出发经过除s以外所有点回到1的距离 的最小值,就是dp[s][v]的状态,这个方程的正确性显然不会证 orz,但是看起来就感觉是对的.注意dp[s][v] , v∈s ,从意义上讲从v出发代表已经到过了v,所以v应该是属于s的.
状态和方程都有了,接下来就是枚举的问题了,我们把s转化成一个二进制来表示点集,1表示已经走过,0代表尚未走过,每一位对应一个点.由于集合不像其他dp有明显的先后关系,枚举就不太方便了,递推方式不太好确定,于是可以用记忆化搜索的方式来求解,(传说中的dp+dfs = dps) .白书中提到由于若S(i)包含于 S(j) , i<=j ,所以我们还是可以用枚举的方式来递推.
poj3311的代码,由于题目中边是可以多次走的,我们先跑一遍floyd预处理一下,然后就是裸的TSP了.
#include<cmath> #include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<time.h> #include<cstdio> #include<vector> #include<stack> #include<queue> #include<iostream> using namespace std; #define LONG long long const int INF=0x3f3f3f3f; const int MOD=1e9+7; const double PI=acos(-1.0); #define clrI(x) memset(x,-1,sizeof(x)) #define clr0(x) memset(x,0,sizeof x) #define clr1(x) memset(x,INF,sizeof x) #define clr2(x) memset(x,-INF,sizeof x) int dp[1<<12][12]; // dp[i][j]表示从j出发经过除了i点集合以为所有的点集并且回到点1的最小代价 int Map[15][15]; int n ; void Floyd( ) { for( int i = 0 ; i < n ;++ i) { for(int j = 0 ;j < n ; ++ j) for(int k = 0 ; k < n ;++ k) Map[j][k] = min (Map[j][k] , Map[j][i] +Map[i][k]); } } void solve1( ) { clr1(dp); for(int i = 0 ; i < n ; ++ i) dp[(1<<n) - 1][i] = Map[i][0] ; for(int s = (1<<n) - 2 ; s >= 0 ;--s ) for(int v = 0 ; v < n ;++ v) for(int u = 0; u < n ; ++ u) if(!((s>>u)& 1 )) dp[s|(1<<v)][v] = min(dp[s | (1<<v)][v] , dp[s| (1<<u)][u] + Map[v][u]); cout<<dp[1][0]<<endl; } int Find(int s , int v) { if(s == (1<<n ) - 1 ) { dp[s][v] = Map[v][0] ; return dp[s][v] ; } if(dp[s|(1<<v)][v] >= 0 )return dp[s|(1<<v)][v] ; int res = INF; for(int u = 0 ;u < n; ++u) { if( !((s>>u) &1) ) { res = min(res, Find(s |(1<<u), u) + Map[v][u]) ; } } dp[s|(1<<v)][v] = res; return dp[s|(1<<v)][v] ; } void solve2() { clrI(dp); cout<<Find(1, 0)<<endl; } int main() { while(cin>>n) { clr1(Map); if(n == 0)break ; n++ ; for(int i = 0; i < n ;++ i) { for(int j = 0; j < n ;++ j) scanf("%d",&Map[i][j]); } Floyd(); solve1(); solve2(); } }
