题解 P1171 【售货员的难题】

zhz小蒟蒻 · 2019-10-02 11:41:24 · 题解

这道题目我提供一种 dfs 的解法（不加状态压缩）
首先，第一眼看到这道题目,我们的想法是什么呢？
状态压缩dp dfs
仔细分析一下题目,我们就可以写出一个极其智障的搜索
我们从第 1 个点开始搜索，记录下经过的路径总长,当再次经过 1 且遍历完了所有的村庄时,我们就更新最小值

void dfs(int f,int len,int num)
{
//  if(len>ans) return;
    if(f==1 && !flag && num==n+1) 
    {
        ans=min(ans,len);
        return;
    }
    for(int i=1;i<=n;++i)
        if(!book[i] && i!=f)
        {
            flag=false;
            book[i]=1;
            dfs(i,len+a[f][i],num+1);
            book[i]=0;
        }
}

然而只有 40 分
就决定是你了,皮卡丘
接下来就应该轮到我们的剪枝入场了

剪枝

1.可行性剪枝
对于这道题目,我们仔细思考一下,就可以发现一个可行性剪枝,就是说,当我们目前经过的总长度大于等于我们记录下来的目前最小的总长度,那么我们就没必要继续找下去了,因为继续往后面走值肯定会变大,所以这种状态无法更新最小值，故我们可以将它"剪掉"。
但是,如果我们最开始搜索的值比较大,那么必定会导致搜索到许多冗余的状态,这该怎么办呢？

我们可以使用一个看上去不靠谱的东西,那就是将每个村庄通往其他村庄的距离从小到大排序,这样就可以让我们最开始搜索的值有可能变得比较小,从而避免了冗余状态。
代码:

  #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node
{
    int rank;
    int data;
}a[21][21];
int n,flag;
int book[21],ans=1<<30;
void dfs(int f,int len,int num)
{
    if(len>ans) return;
    if(f==1 && !flag && num==n+1) 
    {
        ans=min(ans,len);
        return;
    }
    for(int i=1;i<=n;++i)
        if(!book[a[f][i].rank] && a[f][i].rank!=f)
        {
            flag=false;
            book[a[f][i].rank]=1;
            dfs(a[f][i].rank,len+a[f][i].data,num+1);
            book[a[f][i].rank]=0;
        }
}
bool cmp(Node x,Node y)
{
    return x.data<y.data;
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    scanf("%d",&n);
    flag=true;
    for(int i=1;i<=n;++i) 
    {
        for(int j=1;j<=n;++j)
        {
            scanf("%d",&a[i][j].data);
            a[i][j].rank=j;
        }
        sort(a[i]+1,a[i]+n+1,cmp);
    }
    dfs(1,0,1);
    printf("%d",ans);
    return 0;
}

然而交上去仍然只有 60 分
肯定是我们的优化力度不够大,继续观察
仔细回想一下我们的搜索过程会经常出现一种情况,那就是还没有走完所有的村庄便又回到了 1 村庄,这种情况显然是不行的,那么我们就应该把它给舍去
代码就不放了,这样子该仍然只有 80 分

再回到我们的搜索上,我们还有一种剪枝没有用,那就是最优性剪枝
简单解释就是说,当前这种情况,无论我们怎么决策,都无法更新最优值
放到这道题里面而言,也就是说当我们搜索到一个状态时,就算接下来的决策全选最小值,也无法更新答案,那么这种答案就可以舍去。