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 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n;
vector > links;
vector > sp;
vector 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(n)); 將這一句替換為下面這一句，就會WA，還請高手能夠指教！
        links.assign(n, vector(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 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n;
vector > links;
vector > sp;
vector used;
vector > 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(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(n));
        links.assign(n, vector(n, 0));
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
                cin >> links[i][j];
        }
        Work();
    }
    return 0;
}