Meet in the Middle

课件：MITM

blue  

MEET IN THE MIDDLE  

问题  

暴力  

优化的暴力  

MITM  

正解  

MITM  

Meet-in-the-Middle.  

就是个暴力。但是跑得比初级的暴力要快很多。  

核心思想是分治。将大问题转化为两个小问题来暴力求解。  

中间相遇。  

什么时候可以使用MITM？  

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

BFS  

一般来说，广搜的搜索范围随着搜索层数递增。  

那么，我们可以采用“双向广搜”的方式，来减少一些不必要  

的搜索过程。  

T

S

T

S

MITM  

切题时间到QAQ  

例题  

你我只隔六步  

给定一个社交网络（无向图）。  

给出两个人的名字，回答这两个人是否最多相隔6个好友。  

MITM  

双向搜索。  

在BFS的过程中，最多拓展3层。  

搜索图  

分赃  

你和blue合伙抢劫土豪Link，获得了40个金币，每个金币有相  

应的价值。  

询问是否能把所有金币分成两堆，价值之和相同。  

暴力  

MITM  

离散对数  

暴力  

MITM  

负数次幂  

blue  

END  

---

网上没有找到多少关于MITM的资料，找到了也只有“中途相遇攻击”……
然后在Google上找到一篇英文文档：http://www.infoarena.ro/blog/meet-in-the-middle

确实写得很好。MITM的原理就是，优化指数级暴力，尝试用双向搜索的方法解决问题。
具体见课件。