洛谷P1433——最优性剪枝与位运算状压dp

洛谷P1433——最优性剪枝与位运算状压dp

关键词：dfs；剪枝；dp；位运算

一、题目描述

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

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

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

样例 1
样例输入 1

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

样例输出 1

7.41

提示
数据规模与约定
对于全部的测试点，保证 $1\le n\le 15$，$|x_i|,|y_i|\le 200$，小数点后最多有 $3$ 位数字。
提示：对于两个点 $(x_1,y_1)$，$(x_2,y_2)$，两点之间的距离公式为 $\sqrt{(x_1?x_2{)}^2+(y_1?y_2{)}^2}$。
$\mathrm{2022.7.13}$：新增加一组 $\text{Hack}$ 数据。

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

二、思路分析

思路1：dfs+最优性剪枝。
先创建邻接矩阵，然后借助dfs枚举所有可能的道路。最优性剪枝策略可以这样实现：if new_d <= minimum。意思是若这条路径上某一步的长度就比先前达到过的整条路径的总长度长，那么这条路径就一定不是最优的路径，所以直接舍去。反之就继续遍历这条路径。dfs的细节见代码，但是这种思路会在部分测试点超时，因为毕竟是$O(n!)$的复杂度。

思路2：位运算状压dp。
状压DP的时间复杂度为 $O(n^2{2}^n)$，通常只能通过$N\le 21$的数据范围，本题数据范围为$N\le 15$因此可以使用状压DP。获取节点数据和创建邻接矩阵(float型)与dfs做法相同，属于准备工作。

在这里储存状态的方式与dfs不同，使用一个二进制数i来储存已经到达了哪些点。例如10000，代表已经到达过第4个点。1001001，代表已经到达了第0、3、6三个点（从右往左看，从0开始）。因为一共有n个点，二进制数左边默认用0填满补全（例如n=9，10000补全后为000010000）各种运算的结果是一样的。

位运算：1<<i表示将1左移i位，即在后面添加i个0。例如1<<5，这个数字就是0b100000。(1<<5)-1就表示0b11111，相应的就表示n=5时走过全部节点的一种状态。i&(1<<j)使用了按位与的运算，用来判断i的（从右往左）第j位是否为1，若是1则不返回0，若是0则返回0。i^(1<<j)使用了异或运算，返回把二进制数i的第j（从右往左）位取反（0变成1、1变成0）后的结果，表示将第j个节点状态设置为未经过。

主要思路是三重循环。最外层循环：枚举每种可能的已经过点的集合i，这种集合与从0到(1<<n)-1这1<<n个二进制数一一对应。第二重循环：当这些点的集合i固定后，要从中选取一个点j作为当前的终点，dp[i][j]就表示从集合i里任意一个不为j的节点当作起点，终点为j，途中不重复地遍历集合i中的所有点，在所有可能的以j为终点的路径中路径长度的最小值。第三重循环：当选定集合i和终点j后，考虑每一条可能路径的上一步，也就是到达终点j之前的上一步，设其为节点k。这个节点k可以是集合i里所有不是j的点。dp[i][j]所描述的情况，就可以根据节点k的不同进行枚举。从集合i（去掉点j）里任意一个不为k的节点当作起点，终点为k，途中不重复地遍历集合i（去掉点j）中的所有点，在所有可能的以k为终点的路径中路径长度的最小值，即为dp[i^(1<<j)][k]。接着，从节点k走到节点j需要L[k][j]长度的距离，所以就可以用这个式子进行迭代，求出dp[i][j]的值：dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+L[j][k])。

最后需要获取的结果是状态为dp[(1<<n)-1]，终点任意的情况下，可能的最小值。总而言之，通过一个二进制数和三重循环，将所有可能的情况的信息“压缩”在了一个二进制数里，并且通过dp储存已得到的信息，从而降低了时间复杂度。

三、代码实现

#dfs做法，TLE
import math
n=int(input())#节点数量
#创建邻接矩阵
L=[[float('inf')]*n for _ in range(n)]#邻接矩阵
points=[]
for _ in range(n):
    xi,yi=map(float,input().split())
    points.append((xi,yi))
for pi in range(n-1):
    for pj in range(pi+1,n):
        dist=math.sqrt((points[pi][0]-points[pj][0])**2+(points[pi][1]-points[pj][1])**2)
        L[pi][pj]=L[pj][pi]=dist

visited=[False]*n
minimum=float('inf')
def dfs(i,cheese,d):#第i个点为源点dfs,吃掉第i个点的奶酪后有cheese个,源点到i的距离
    global minimum
    visited[i]=True
    if cheese==n:
        minimum=min(d,minimum)
        return
    for neigh in range(n):
        if not visited[neigh]:
            new_d = d + L[neigh][i]
            if new_d <= minimum:#剪枝
                visited[neigh]=True
                dfs(neigh,cheese+1,new_d)
                visited[neigh]=False
    visited[i]=False
for k in range(n):
    dfs(k,1,math.sqrt((points[k][0])**2+(points[k][1])**2))
print('{:.2f}'.format(minimum))

#状压dp，AC
import math
n=int(input())#节点数量
L=[[float('inf')]*n for _ in range(n)]#邻接矩阵
points=[]
for _ in range(n):
    xi,yi=map(float,input().split())
    points.append((xi,yi))
for pi in range(n-1):
    for pj in range(pi+1,n):
        dist=math.sqrt((points[pi][0]-points[pj][0])**2+(points[pi][1]-points[pj][1])**2)
        L[pi][pj]=L[pj][pi]=dist
#创建邻接矩阵

dp=[[float('inf')]*n for _ in range((1<<n))]
#dp[i][j]表示当前到达过的点记录为二进制数i，最后到达的终点是j

for i in range(n):
    dp[1<<i][i]=math.sqrt((points[i][0])**2+(points[i][1])**2)
#dp数组初始化

for i in range(1,(1<<n)):#对于确定的到达过的点的集合i
    for j in range(n):#以集合中的一点j为终点
        if i&(1<<j)==0:
            continue#j不在集合i里
        for k in range(n):
            if k==j:
                continue
            if i&(1<<k)==0:
                continue#k不在集合i里
            dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+L[j][k])
#dp状态转移方程

ans=float('inf')
for q in range(n):
    ans=min(ans,dp[(1<<n)-1][q])
print('{:.2f}'.format(ans))

#注：洛谷，使用pypy3提交，可AC

总结：从洛谷P1433中，我们可以学习到dfs的最优性剪枝策略的运用，以及位运算状压dp的思路。这种难以想到的dp思路值得学习积累。

谢谢您的阅读！