旅行商问题的动态规划解决

24 Nov 2012

旅行商问题是一个著名的NP问题,不能找到多项式解。不过可以用动态规划的方法把时间复杂度从O(N!)降低到O(2^N)。对于解决小规模的旅行商还是可以实现的。

题目地址在这里:http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=420

发现枚举过程中还是有很多重复计算的,所以可以存贮一下状态,避免了重复计算。

开辟N+1维数组,dp[N][2][2]..[2],其中dp[cur][p1][p2]..[pn]表示,当前人在cur位置,并且p1–pn走过的为1,未走过的为0。可见空间复杂度为N*2^N。

状态转移方程为

dp[cur][p1]..[1]..[pn] = min{dp[i][p1]..[0]..[n]+Dis[cur][i]}

其中i为1–N地点中已经走过的地点。

因为当前状态只能从已经走过的那些地方走过来,所以只要选一个最短的,就表示走完以上地点,并且停在当前点需要的最短路程就是这么多。由于回路必然包含每一个点,所以从任何点出发,得到的最短路径都是一定的。所以我的程序假设就从第一个点出发。 边界条件就是 dp[0][1]。dp[0][1]=0,表示在第0个地点(我是用0–N-1表示N个地点的),1的二进制是00000001,表示只有第一个可以走过。

要注意:既然假设从第一个地点出发,所以在递归自顶向下搜索的时候,只有最后一次才能回出发点!即 dp[cur][p1]..[1]..[pn]中,在p1–pn中只有2个为1的时候,也就是只有出发点和第二个地点的时候,才能从第二个地点回到出发点。最终的结果只要取 min{dp[i][1]..[1]..[1]+Dis[0][i]} 就好了,表示回到出发点0。构成完整回路。

当然如果N比较大,开那么多维的数组比较麻烦,而且可能编译不能通过。所以我们用一个数的不同位分别表示一个城市是否走过。于是将N维压缩到一维。dp[N][2]..[2]变成了 dp[N][2^N]。

#include <iostream>
using namespace std;
int N;              //total num of place
int Map[16][16];
int dp[16][36768];  //dp[cur][status] cur:0--N-1 当前所在位
                    //status 第i位 表示当前是否走过
int num_of_1(int status)        //获取多少位为1,表示已经走过多少地点
{
    int i,sum=0;
    int t=1;
    for(i=0;i<N;++i)
    {
        if(status&t)
        {
            ++sum;
        }
        t<<=1;
    }
    return sum;
}
int get(int cur,int status)
{
    if(dp[cur][status]!=-1)
    {
        return dp[cur][status];
    }
    if (num_of_1(status)>2)     //除了出发点,还有其他地方可以走
    {
        int i,t=2;
        int minlen=10000000;
        for (i=1;i<N;++i,t<<=1)
        {
            if (i==cur)
            {
                continue;
            }
            if (status & t)
            {
                if (get(i,status & (~(1<<cur)))+Map[cur][i] < minlen)       //去掉当前位
                {
                    minlen=get(i,status & (~(1<<cur)))+Map[cur][i];
                }
            }
        }
        return dp[cur][status]=minlen;
    }else                       //只能回到出发点
    {
        return dp[cur][status]=Map[0][cur];
    }   
}
int main()
{
    int i,j,minlen;
    cin>>N;
    if (N==1)
    {
        cout<<0<<endl;
        return 0;
    }
    for(i=0;i<N;++i)
    {
        for(j=0;j<N;++j)
        {
            cin>>Map[i][j];
        }
    }
    for (i=0;i<N;++i)
    {
        for (j=0;j<32768;++j)
        {
            dp[i][j]=-1;
        }
    }
    dp[0][1]=0;     //处在第一个点,即出发点
    minlen=10000000;
    for (i=1;i<N;++i)
    {
        if (Map[0][i]+get(i,(1<<N)-1)<minlen)
        {
            minlen=Map[0][i]+get(i,(1<<N)-1);
        }
    }
    cout<<minlen<<endl;
}