Meet-in-the-Middle

问题

你有一个n(n<=1000)个整数的集S.
问能否从S中找到4个元素a,b,c,d,使得a+b+c+d=0.
允许选取同一个元素多次.

暴力

初级暴力:枚举a,b,c,d.复杂度为O(n^4).
高级暴力:枚举a,b,c,查询集合中是否存在d=(-a)+(-b)+(-c).复杂度为O(n^3).

MITM

Step1.枚举a,b,Hash存储a+b的结果.复杂度为O(n^2).
Step2.枚举a,b,查询Hash表中是否有(-a)+(-b).复杂度为O(n^2).


Meet in the Middle.
其实就是个暴力.但是跑得比初级的暴力要快很多.
核心思想是分治.将大问题转化为两个小问题来暴力求解,中间相遇.

什么时候可以使用MITM?

问题可以“在中间相遇”的时候.

BFS

一般来说,广搜的搜索范围随着搜索层数递增.
那么,我们可以采用“双向广搜”的方式,来减少一些不必要的搜索过程.


例题

你我只隔六步

问题

给定一个社交网络(无向图).
给出两个人的名字,回答这两个人是否最多相隔6个好友.

MITM

双向搜索.
在BFS的过程中,最多拓展3层.

分赃

问题

你和blue合伙抢劫土豪Link,获得了40个金币,每个金币有相应的价值.
询问是否能把所有金币分成两堆,价值之和相同.

暴力

NP完全问题.现在人类没有找到多项式时间内的解法.
枚举每个硬币是放在A还是放在B.共2^40=1,099,511,627,776次.

MITM

设总价值为2w,那么A堆得价值为w.
如果A堆的价值为w,则B堆的价值也为w.

因此问题转换成:
从40个元素的集合中取出一些元素,使得价值之和为w.

我们把序列随便分为两份,每份20个元素.
那么问题化为:
从A,B中各取若干个元素,使其和为w.

对于集合A,枚举所有的元素和的取值,压进Hash表.复杂度为O(2^20).
对于集合B,枚举所有的元素和的取值k,如果Hash表中有(w-k),则判断有解.复杂度为O(2^20).

这儿有个PDF

感谢原作者ruanxz

显示 Gitment 评论