【算法笔记】meet-in-the-middle 算法

meet-in-the-middle 算法（又称折半搜索、双向搜索），属于一种优化的 DFS 或 BFS 算法。同分治算法近似，它将问题进行了拆分，然后进行合并归一，得出最后的结果。这样做的好处是在穷举解的时候能够对很多情况进行剪枝，降低了时间复杂度。

n <= 40 的搜索类型题目一般都可以优化，本质上这是一种空间换时间的算法。

穷举类的问题当匹配条件越多的时候，其时间复杂度便会越大，所以可以通过将多个条件拆分匹配的方式来减小复杂度。简单来说，这就是“分而治之”的一种手段。

常见类型

求和

这一部分可直接见「举个例子」部分。

双向搜索

这在关系网处理和图的路径规划中经常使用，且在寻路问题中表现很好。算法会同时从两个节点开始搜索，并且看什么时候这两个搜索的边界相遇。这个可以将需要扩展的节点降低到 $O(p^{k/2})$。

2DES 破解

DES 算法为密码体制中的对称密码体制，又被称为美国数据加密标准，是 1972 年美国 IBM 公司研制的对称密码体制加密算法。明文按 64 位进行分组，密钥长 64 位，密钥事实上是 56 位参与 DES 运算（第 8、16、24、32、40、48、56、64 位是校验位，使得每个密钥都有奇数个1），分组后的明文组和 56 位的密钥按位替代或交换的方法形成密文组的加密方法。

DES 算法如今之所以被淘汰，是因为秘钥空间太小。其密钥的 $2^{56}$ 种可能性在以前是很难穷举破解的，但如今随着算力的发展，把所有可能的秘钥遍历一遍也是可以的（参考 BTC 挖矿）。在这之后的 DES 算法便开始显得力不从心，亟待升级，于是就有了 3DES 算法——使用 3 个密钥进行 3 次 DES 加密运算。

2DES 去哪儿了？答案是 DES 算法过后直接提升到了 3DES，直接把 2DES 给跳过了。理论上来说 2DES 具有 $2^{102}$ 的秘钥空间，已足够使用，但是为什么不用呢，原因就在于 meet-in-the-middle 算法为基础的中间人攻击（Diffile-Hellman 发明）——信息论课堂上的老朋友了，在这儿只用简单的语言介绍其原理。

假设我需要通过一组 2DES 的明文与密文破解出秘钥，我并不需要遍历 $2^{102}$ 整个秘钥空间，而是使用明文枚举 $2^{56}$ 个秘钥加密，得到 $2^{56}$ 个中间值并存入哈希表；然后使用密文枚举 $2^{56}$ 个秘钥并与明文的哈希库做对比，得到的所有值中一定有一个与之前加密所得到的相等，即 $E_{ki}(p) = D_{kj}(s)$，meet-in-the-middle 结束。这整个破解过程中不难发现，只要有足够大的空间用于存储哈希表，2DES 破解密码的时间仅仅相当于破解 2 次 DES。

3DES 的话就可以避免这个问题，无论如何 meet-in-the-middle，都只能够将时间复杂度给缩小到 $O(2^{102})$ 程度。

举个例子

「4 和问题」

问题：给定一个整数数组 A，问数组中是否存在 4 个数，使得这 4 个数的和是 0（同一个元素可以被多次使用）。

例如：A = [2, 3, 1, 0, -4, -1]，可能的方案是 3 + 1 + 0 - 4 = 0 或 0 + 0 + 0 + 0 = 0。

该题的直观解法就是穷举，然后记录所有符合条件的方案即可，复杂度为 $O(N^4)$。当然，并不能说穷举的时间复杂度高就不好，毕竟这种解法的解题复杂度低，比赛的时候可以快速解题。

一般情况下比赛都会配上阴间测试样例，暴力解极有可能错误导致加时，所以最好对算法进行优化后再提交。

使用 meet-in-the-middle 算法的话也不难理解。首先我们将问题中的 a + b + c + d = 0 的格式化为 a + b = -(c + d)，这时我们就可以发现，当 a + b 计算出来之后，c + d 的值也就出来了。所以我们要做的就是穷举所有的 a + b（时间复杂度为 $O(N^2)$）并记录到哈希表中，然后匹配一下是否有对应的值即可。

代码如下：

def 4sum(A):
  sums = {}
  for a in A:
    for b in A:
      sums[a + b] = (a, b)
 
  for c in A:
    for d in A:
      if -(c + d) in sums:
        print(sums[-(c + d)][0], sums[-(c + d)][1], c, d)
        return
 
  return None

「1755. 最接近目标值的子序列和」

解题复杂度最低的解法就是直接穷举，而且这道题 LeetCode 的测试集不够阴间，可以直接过。同时这也可以使用 meet-in-the-middle 算法剪枝，大大降低时间复杂度。

算法很直观，原理就是分块穷举会比总体穷举更节省时间。首先将该数组分成左右两半，然后分别穷举出所有可能的子数组和。然后对该两个生成数组重新排序，从而方便最后的 meet-in-the-middle 算法进行判断。

Python 代码如下：

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        ln = n // 2

        # make 函数是用于穷举一个列表所有可能的子数组和
        # 比如 [3, 5] 就会生成 [0, 3, 5, 8]；[5, -7] 就会生成 [0, 5, -7, -2]
        def make(lis, loc, lis_out):
            if loc == len(lis):
                return lis_out
            temp = lis_out + [k + lis[loc] for k in lis_out]
            return make(lis, loc + 1, temp)

        # ll 和 rr 实际上就是左右两半子数组和的穷举，方便后面 meet in the middle
        ll = make(nums[:ln], 0, [0])  
        rr = make(nums[ln:], 0, [0])

        # 排个序
        ll.sort()
        rr.sort()

        pl = 0
        pr = len(rr) - 1
        out = float("inf")
        # pl 遍历 ll 数组，pr 遍历 rr 数组
        while pl < 2 ** ln and pr >= 0:
            out = min(out, abs(ll[pl] + rr[pr] - goal))
            if ll[pl] + rr[pr] > goal:
                pr -= 1
            else:
                pl += 1
        return out

复杂度

假设向外搜索 $n$ 层需要的代价为 $f(n)$。如果不用 meet-in-the-middle 那么复杂度当然是 $O(f(n))$。

如果使用了 meet-in-the-middle，那么从起点开始需要搜索的代价为 $f(n/2)$，从终点开始搜索的代价也是 $f(n/2)$，总代价就是 $2*f(n/2)$，复杂度为 $O(f(n/2))$。

【算法笔记】meet-in-the-middle 算法.