Meet in the middle（MITM）

Tags：搜索

作业部落

评论地址

---

PPT中会讲的很详细
当搜索的各项互不影响（如共\(n\)个物品前\(n/2\)个物品选不选和后\(n/2\)个物品选不选互不干扰）且状态数小得可怜的时候可以考虑双向搜索（MITM）
实现非常灵活，具体看题
精髓是：用空间换时间

• [x] [SPOJ4580]ABCDEF☃☃
• [x] [NOI2001]方程的解数☃☃
• [x] [TopCoder14580] EllysRPS☃☃☃
• [x] [BZOJ4800]Ice Hockey World Championship☃☃☃
• [x] [Codeforces888E]Maximum Subsequence☃☃☃
• [x] [ZOJ3777] Problem Arrangement☃☃
• [x] 八数码难题☃☃☃