TSP问题之状压dp

林不二 lv.1

发布时间：2022-12-05 12:49:50 390

相关标签：

TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。
假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市
只能拜访一次，而且最后要回到原来出发的城市，要求路径的总和最小。其中，2<=N<=15。

看到n的这个范围，很多情况下就是状压了，因为所有可能的路线共有(n-1)!种，这个值太大了。状压就是将状态压缩成一个整数，然后用这个整数来表示状态。就像背包里的二进制优化，每一个元素的选与不选对应到二进制里面。

首先我们试着去设计状态，假设现在已经访问过的顶点的集合为S，当前所在顶点为v，
用dp[S][v]表示从v出发还有访问剩余的所有顶点，最终返回到顶点0的路径总和最小值。从v出发可以到任意一个还未访问过的顶点，边界就是访问完所有顶点并且返回到顶点0。
在看递推式之前，必须要了解一下知识点….

一些集合的表示
空集 ∅ –> 0
只含有第i个的集合{i} –> 1<< i
含有全部n个元素的集合{0,1,2,….,n-1} –> (1 << n)-1
判断第i个元素是否在S集合中 –> if (S>>i&1)
向集合S中加入第i元素 S∪{i} –> S | 1<< i
从集合S中除去第i个元素 S{i} –> S & -(1 << i)
集合S和T的并集 S∪T –> S|T
集合S和T的交集 S∩T –> S&T

有了以上知识点，递推式就很好理解了。
递推式为
dp[V][0] = 0;(边界)
dp[S][v] = min{dp[S∪{u}][u] + d[u][v] | u不属于S}

ok,上code（^_^）
首先我们可以通过递推式写出记忆化搜索

int rec(int S,int v)
{
    if(dp[S][v]>=0)
        return dp[S][v];
    if(S==(1<<n)-1&&v==0)  //边界
        return dp[S][v] = 0;
    int res = inf;
    for(int u = 0; u < n; ++u)
        if(!(S>>u&1)) //如果u不属于S集合
        //下一步移动到顶点u
        res = min(res,rec(S|1<<u,u)+d[v][u]);
    return dp[S][v] = res; //记忆化
}

void solve()
{
    memset(dp,-1,sizeof(dp));
    printf("%d\n", rec(n,0));
}

但是在这个问题中，对于任意两个整数i和j，如果他们对应的集合满足S（i）包含于S（j），就有i<=j，因此我们可以写成循环的方式。

void solve()
{
    for(int S = 0; S < 1<<n; ++S){
        fill(dp[S],dp[S]+n,inf);  //初始化
    }
    dp[(1<<n)][0] = 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)){ //如果u不属于S集合
                    dp[S][v] = min(dp[S][v],dp[S|1<<u][u]+d[v][u]);
                }
            }
        }
    }
    printf("%d\n",dp[0][0]);
}

文章来源： https://blog.51cto.com/u_14797585/5898570

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。