洛谷题单指南-搜索-P1433 吃奶酪

原题链接：https://www.luogu.com.cn/problem/P1433

题意解读：计算经过所有奶酪一次的总路径最短，可以采用dfs、dp等方法。

解题思路：

最直接的思路是DFS，暴搜所有的路径方案，计算最小距离，n最大是15，复杂度为15!≈10^12，必定会超时，先保证正确性，得到部分分：

50分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 20;

double x[N], y[N]; //保存奶酪坐标
int path[N]; //保存路径是第几个奶酪
double jl[205][205]; //保存每两个点之间的距离
bool flag[N]; //标记第i个奶酪是否已走过
int n;

double ans = 2e9;

double distance(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

//k:第几个奶酪，dist：当前走过的距离
void dfs(int k, double dist)
{
    if(k > n)
    {
        ans = min(ans, dist);
        return;
    }
    for(int i = 1; i <= n; i++)
    {
       if(flag[i]) continue;
       flag[i] = true;
       path[k] = i;
       dfs(k + 1, dist + jl[path[k]][path[k-1]]);
       flag[i] = false; //恢复flag
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];

    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            jl[i][j] = distance(x[i], y[i], x[j], y[j]);
        }
    }

    dfs(1, 0);
    cout << fixed << setprecision(2) << ans;

    return 0;
}

能否尽量减少DFS的次数呢？由于是要找最小路径，那么如果在DFS过程中，某次已走过的路径已经大于之前保存的最小路径，则本次dfs可以返回，这样起到了一定的剪枝效果，关键代码是：if(dist > ans) return;

由于剪枝无法准确评估到底能减掉多少，所以复杂度是由数据点来决定的，仍然无法保证不超时，只能尽量减少超时。

90分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 20;

double x[N], y[N]; //保存奶酪坐标
int path[N]; //保存路径是第几个奶酪
double jl[205][205]; //保存每两个点之间的距离
bool flag[N]; //标记第i个奶酪是否已走过
int n;

double ans = 2e9;

double distance(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

//k:第几个奶酪，dist：当前走过的距离
void dfs(int k, double dist)
{
    if(dist > ans) return; //如果某次中间的距离已经大于之前的最小ans，直接结束本次搜索
    if(k > n)
    {
        ans = min(ans, dist);
        return;
    }
    for(int i = 1; i <= n; i++)
    {
       if(flag[i]) continue;
       flag[i] = true;
       path[k] = i;
       dfs(k + 1, dist + jl[path[k]][path[k-1]]);
       flag[i] = false; //恢复flag
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];

    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            jl[i][j] = distance(x[i], y[i], x[j], y[j]);
        }
    }

    dfs(1, 0);
    cout << fixed << setprecision(2) << ans;

    return 0;
}

还能不能进一步减少dfs的次数呢？

想象一种场景，当最多有15个点时，如果已经过a、b、c、d、e 5个点，当前在d点，走过距离是L1

下一次dfs时，也已经过a、b、c、d、e 5个点，当前在b点，走过距离是L2，

如果L2>L1，其实这时就没有必要继续dfs下去，因为肯定不可能是最优解。

因此，我们可以记录每种状态下所走过的距离，通过二进制来表示已经过了哪几个点

如：01011可以表示经过了1/2/4号点，用整数表示就是11，15个点用整数表示状态不超过2^16-1 = 65535

定义数组double dp[40000][20]; dp[i][j]表示，已经过的点是i所表示的二进制状态（1表示走过，0表示没走过）、当前在j点所经过的距离，

在代码中，通过判断dp[i][j]是否有值，且当前值比原值还大，则不需要继续dfs。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 20;

double x[N], y[N]; //保存奶酪坐标
int path[N]; //保存路径是第几个奶酪
double jl[205][205]; //保存每两个点之间的距离
bool flag[N]; //标记第i个奶酪是否已走过
double dp[65540][20]; //dp[i][j]表示已经过的点是i所表示的状态，当前在j点所经过的距离
int n;

double ans = 2e9;

double distance(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

//k：第几个，s：当前已经过的点的状态，dist：当前走过的距离
void dfs(int k, int s, double dist)
{
    if(dist > ans) return; //如果某次中间的距离已经大于之前的最小ans，直接结束本次搜索
    if(k > n)
    {
        ans = min(ans, dist);
        return;
    }
   
    for(int i = 1; i <= n; i++) //遍历所有奶酪编号
    {
        if(flag[i]) continue;
 
        int ns = s + (1 << (i - 1)); //当前已经过的点算上i 
        double ndist = dist + jl[i][path[k-1]]; //已经过的距离加上当前距离
        if(dp[ns][i] != 0 && ndist >= dp[ns][i]) continue; //如果当前已经过点的状态之前已出现过，且距离比之前还大或相等，则不需要继续dfs
        
        flag[i] = true; path[k] = i; dp[ns][i] = ndist;
        dfs(k + 1, ns, ndist);
        flag[i] = false; //恢复flag
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];

    //预计算所有点之间的距离
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            jl[i][j] = distance(x[i], y[i], x[j], y[j]);
        }
    }

    dfs(1, 0, 0);
    cout << fixed << setprecision(2) << ans;

    return 0;
}