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;
}

如果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;
}

poj3311 经典tsp问题,布布扣,bubuko.com

poj3311 经典tsp问题

原文：http://blog.csdn.net/hustluy/article/details/28110923