首页 > 代码库 > poj3311 经典tsp问题
poj3311 经典tsp问题
题目的大概意思就是一个人到一些城市送披萨,要求找到一条路径能够遍历每一个城市后返回出发点,并且路径距离最短。最后输出最短距离即可。注意:每一个城市可重复访问多次。
由于题中明确说了两个城市间的直接可达路径(即不经过其它城市结点)不一定是最短路径,所以需要借助邻接矩阵首先求出任意两个城市间的最短距离。这一步骤使用Floyd最短路径算法即可。然后,在此基础上来求出遍历各个城市后回到出发点的最短路径的距离,即求解TSP问题。
TSP问题目前有多种解法:搜索解法,动归解法,启发式解法。这里就针对poj 3311问题给出了前两种解法。
搜索解法:这种解法其实就是计算排列子集树的过程。从0点出发,要求遍历1,2,3点后回到0点。以不同的顺序来依次遍历1,2,3点就会导出不同的路径(0->1->2->3->0;0->1->3->2->0等等),总共有3!=6条路径需要考虑,从中选出最短的那条就是所求。搜索解法的时间复杂度为O(n!)。
附上搜索代码:
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <cstdio> #include <cstdlib> using namespace std; int n; vector<vector<int> > links; vector<vector<int> > sp; vector<bool> used; long long ans; void Floyed() { sp = links; for(int k = 0; k < n; ++k) { for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) sp[i][j] = min(sp[i][j], sp[i][k] + sp[k][j]); } } //for(int i = 0; i < n; ++i) //{ //for(int j = 0; j < n; ++j) //cout << sp[i][j] << " "; //cout << endl; //} } void Backtrack(int level, int v, long long cost) { if( level == n - 1 ) { ans = min(cost + sp[v][0], ans); return; } for(int i = 0; i < n; ++i) { if( !used[i] ) { used[i] = true; Backtrack(level + 1, i, cost + sp[v][i]); used[i] = false; } } } void Work() { Floyed(); ans = 1e8; used.assign(n, false); used[0] = true; Backtrack(0, 0, 0); //cout << "ans = "; cout << ans << endl; } int main() { //freopen("3311.tst", "r", stdin); while( cin >> n && n ) { ++n; //links.resize(n, vector<int>(n)); 将这一句替换为下面这一句,就会WA,还请高手能够指教! links.assign(n, vector<int>(n, 0)); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) cin >> links[i][j]; } Work(); } return 0; }
动归解法:仔细观察搜索解法的过程,其实是有很多重复计算的。比如从0点出发,经过1,2,3,4,5点后回到0点。那么0->1->2->(3,4,5三个点的排列)->0与0->2->1->(3,4,5三个点的排列)->0就存在重复计算(3,4,5三点的排列)->0路径集上的最短路径。只要我们能够将这些状态保存下来就能够降低一部分复杂度。下面就让我们用动归来求解这一问题。记dp(v, S)为从v点出发,遍历S集合中的每一个点后,回到出发点(0点)的最短距离。递推表达式的推导如下:
如果S为空集,即没有需要遍历的结点了。此时可以直接从v点回到0点,则dp(v,S)=sp[v][0] //sp[v][0]是v点到0点的最短路径距离
如果S不为空集,则dp(v,S)=min{sp[v][u] + dp(v,S-{u})}//sp[v][u]是v点到u点的最短路径距离
上述过程如何用编码实现呢,主要难点就在于集合S的表示。我们可以用位比特来表示一个集合。如集合{1,2,3},{1,2}分别可以用7(111),3(011)来表示。所以动归整个状态二维表的大小为n*2^n,而表中的每一个元素的计算需要O(n)的复杂度,所以动态规划的时间复杂度为O(n^2*2^n)。
附上动态规划代码:
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <cstdio> #include <cstdlib> using namespace std; int n; vector<vector<int> > links; vector<vector<int> > sp; vector<bool> used; vector<vector<long long> > dp; long long ans; void Floyed() { sp = links; for(int k = 0; k < n; ++k) { for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) sp[i][j] = min(sp[i][j], sp[i][k] + sp[k][j]); } } //for(int i = 0; i < n; ++i) //{ //for(int j = 0; j < n; ++j) //cout << sp[i][j] << " "; //cout << endl; //} } long long CalcVal(int v, long long bit) { if( dp[v][bit] != -1 ) { return dp[v][bit]; } if( !bit ) { dp[v][bit] = sp[v][0]; } else { long long ret = 1e8; for(int i = 1; i < n; ++i) { int b = 1 << i - 1; if( b&bit ) { ret = min(ret, sp[v][i] + CalcVal(i, b-bit)); } } dp[v][bit] = ret; } return dp[v][bit]; } void Work() { Floyed(); long long m = (1 << n - 1) - 1; dp.assign(n, vector<long long>(m, -1)); ans = 1e8; for(int i = 1; i < n; ++i) { long long b = 1 << i - 1; ans = min(ans, sp[0][i] + CalcVal(i, b-m)); } //cout << "ans = "; cout << ans << endl; } int main() { //freopen("3311.tst", "r", stdin); while( cin >> n && n ) { ++n; //links.resize(n, vector<int>(n)); links.assign(n, vector<int>(n, 0)); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) cin >> links[i][j]; } Work(); } return 0; }