题目描述

房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。

输入格式

第一行有一个整数，表示奶酪的数量 n。

第 2 到第 (n + 1) 行，每行两个实数，第 (i + 1) 行的实数分别表示第 i 块奶酪的横纵坐标 $x_i, y_i$ 。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 2 位小数。

输入输出样例

输入 #1

4
1 1
1 -1
-1 1
-1 -1

输出 #1

7.41

说明/提示

数据规模与约定

对于全部的测试点，保证 $1\leq n\leq 15$，$|x_i|, |y_i| \leq 200$，小数点后最多有 3 位数字。

提示

对于两个点 $(x_1,y_1)$，$(x_2, y_2)$，两点之间的距离公式为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

题目分析

题目要我们找到能吃完所有奶酪的距离最短的路径。

从暴力的角度进行考虑，只需要找出所有的道路，找到里面最短的一条路即可。

不难想到可以深搜的方式去搜索解决这样的问题，设dfs(step,now,sum) 表示在第step步，当前位于now这个点，已经走过的距离为sum。

void dfs(int step,int now,double sum){
    if(step>n){//所有奶酪吃完
        if(sum<ans) ans=sum;//更新最小的走过的路径
        return ;
    }
    for(int i=1;i<=n;i++){//遍历所有的奶酪
        if(!vis[i]){//选没吃过的奶酪
            double tmp=sum+dist[now][i];//计算吃下第i个奶酪经过的总路径长度
            vis[i]=true;//标记第i个奶酪吃掉了
            dfs(step+1,i,tmp);//递归探索下一步
            vis[i]=false;//回溯状态
        }
    }
}

此时会有5个点超时。我们需要进行优化。

如果将搜索的状态看做结点，状态之间的转移看作是边，搜索的过程就构造出了一棵“搜索树”。所谓“剪枝”，就是在搜索树上去掉一些枝杈不进行搜索，从而减小时间消耗。

剪枝策略分为可行性剪枝和最优性剪枝两种。

可行性剪枝

保证当前搜索的状态是合法的，并且从当前状态继续搜索时，至少能找到一个最终解。

最优性剪枝

考虑一个最优化问题，在搜索过程中已经得出了上述一个解x（但不确定他是否是最优的），在某个状态中，发现从当前状态在最优情况下到达终点所得到的解也不优于已得到的解x，则可以直接剪枝返回。这种优化思路称为最优性剪枝。

搜索过程中我们可以尝试进行剪枝优化，若当前路径总长已超过记录的最短路径长度ans 那么之后只会更长，不可能优于已得到的解ans,此时就可以直接剪枝返回。

void dfs(int step,int now,double sum){
    if(sum>=ans) return ;//继续下去也不可能优于ans，最优性剪枝处理
    if(step>n){//所有奶酪吃完
        if(sum<ans) ans=sum;//更新最小的走过的路径
        return ;
    }
    for(int i=1;i<=n;i++){//遍历所有的奶酪
        if(!vis[i]){//选没吃过的奶酪
            double tmp=sum+dist[now][i];//计算吃下第i个奶酪经过的总路径长度
            vis[i]=true;//标记第i个奶酪吃掉了
            dfs(step+1,i,tmp);//递归探索下一步
            vis[i]=false;//回溯状态
        }
    }
}

此时，剩下一个点超时。

可以尝试使用“卡时”的技巧，去赌一赌运气。记录递归的次数，当快要超时的时候直接结束，输出当前记录下的最优解。若运气好，当前记录下的是整体最优的就能通过。

void dfs(int step,int now,double sum){
    cnt++;//计算次数
    if(cnt>=5e7){//超过规定的次数就直接输出
        printf("%.2f",ans);
        exit(0);//结束整个程序
    }
    if(sum>=ans) return ;//继续下去也不可能优于ans，最优性剪枝处理
    if(step>n){//所有奶酪吃完
        if(sum<ans) ans=sum;//更新最小的走过的路径
        return ;
    }
    for(int i=1;i<=n;i++){//遍历所有的奶酪
        if(!vis[i]){//选没吃过的奶酪
            double tmp=sum+dist[now][i];//计算吃下第i个奶酪经过的总路径长度
            vis[i]=true;//标记第i个奶酪吃掉了
            dfs(step+1,i,tmp);//递归探索下一步
            vis[i]=false;//回溯状态
        }
    }
}

但这样做比较看运气，如果数据出的不凑巧，仍然会无法AC。

此时需要进一步进行优化。此时奶酪数量最多15个，每个奶酪在过程中不是选中吃掉，就是没有选中。我们可以用二进制来压缩它的状态，1表示吃过，0表示没吃过。此时设dp[vis][i] ,第一维描述的是所有奶酪的状态；第二维描述的是奶酪的编号。dp[vis][i] 描述的就是在vis 状态下的吃第i个奶酪的最短总距离，此时复杂度是 ，因为n的范围限制，能在复杂度要求内完成。

首先，既然已经状态压缩了，那么寻找下一个未吃过的奶酪，就不用每次 $1\sim n$ 进行遍历了，可以直接利用lowbit 寻找未吃过的奶酪。

int vis=all&(~state);//为了配合lowbit，转换状态，将没吃过的标为1，吃过的标为0
while(vis){
    int x=lowbit(vis);//获取低位
    int i=Log[x]+1;//根据低位值算出没吃过的奶酪的编号
    ...
    vis-=x;
}

过程中还可以进一步进行剪枝，只有当往后走存在更优解时，才继续递归搜索下去，否则不用继续。

void dfs(int state,int now,double sum){
    if(sum>=ans) return ;
    if(state==all){//全部吃完
        if(sum<ans) ans=sum;
        return ;
    }
    int vis=all&(~state);//转换状态 1-没选 0-选过
    while(vis){
        int x=lowbit(vis);
        int i=Log[x]+1;//求出第i个奶酪没选
        // 第一次 或者是 dp[state][i]存在更优解 
        if(dp[state][i]==0||dp[state][i]>sum+dist[now][i]){
            dp[state][i]=sum+dist[now][i];//更新更优的值
            dfs(state+x,i,dp[state][i]);//继续向后探索
        }
        vis-=x;
    }

}

实现代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct node{
    double x,y;
};
node dot[20];
int all;
int n;
int Log[1<<15];
double ans;
double dist[20][20];
double dp[1<<15][20];
double dis(node a,node b){//计算两点间路径
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int lowbit(int x){
    return x&(-x);
}
void init(){//初始化 Log, Log[x] == log2(x)
    Log[1]=0;Log[2]=1;
    for(int i=3;i<(1<<15);i++){
        Log[i]=Log[i/2]+1;
    }
}
void dfs(int state,int now,double sum){
    if(sum>=ans) return ;
    if(state==all){//全部吃完
        if(sum<ans) ans=sum;
        return ;
    }
    int vis=all&(~state);//转换状态 1-没选 0-选过
    while(vis){
        int x=lowbit(vis);
        int i=Log[x]+1;//求出第i个奶酪没选
        // 第一次 或者是 dp[state][i]存在更优解 
        if(dp[state][i]==0||dp[state][i]>sum+dist[now][i]){
            dp[state][i]=sum+dist[now][i];//更新更优的值
            dfs(state+x,i,dp[state][i]);//继续向后探索
        }
        vis-=x;
    }

}
int main(){
    init();//初始化 Log[]数组,Log[x]==log2(x)
    scanf("%d",&n);
    all=(1<<n)-1;//终点状态，所有位标为1
    dot[0].x=dot[0].y=0;
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&dot[i].x,&dot[i].y);
        ans+=dis(dot[i-1],dot[i]);
    }
    //预处理计算两点间的距离
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dist[i][j]=dis(dot[i],dot[j]);
        }
    }
    dfs(0,0,0);
    printf("%.2f",ans);
    return 0;
}