前言

作为一名往日OI的玩家，偶然间发现昔日的战友在SJTU-ACM的OJ上面发了几道题，随手点开一题发现一题用的正式赫赫有名的Meet in the Middle算法，于是心血来潮就把这题顺手AC了。

正文

我们首先还是来介绍一下meet in the middle 算法。

Meet in the Middle算法可以看成是搜索算法的一个改进，一般来说用于广搜（BFS），不过如果搜索深度有上限的情况下也可以用深搜。

我们首先假象一个搜索场景

假设从上面的红点开始进行搜索，找一条能通向下面那个红点的路径，每个点都有两条岔路可供选择。

显然如果我们简单的从上面那个点开始BFS，代价是较大的，在最差的情况下，可能需要把整张图的45个节点给走一遍。

当然把搜索的重任全部交给一个节点是不合理的。于是Meet in the Middle算法就诞生了。顾名思义，就是两个节点各自向中间搜索，直至碰头。

在上图中红点的部分为起点开始向外搜索到的点，而蓝点表示从终点开始搜索到的点。假如此时搜索进行到点B，直接就能发现A点是从起点过来的点，那么也就自然找到了一条从 起点->A->B->终点 的路径，然而我们发现，整个图里面黑色部分的节点与边其实我们都可以不用访问。当整张图扩大是，这种优化的效果还是比较明显的。

我们接下来用数学来具体推导一下这种搜索方案的复杂度。

假设向外搜索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复杂度均为O(n^2)。但是当f(n)为指数函数时该算法的效果就会非常明显。比如f(n)=2^n，那么不用meet in the middle复杂度即为O(2^n)，但是使用了meet in the middle的复杂的只有O(2^(n/2))，相当于直接开了一个根号。meet in the middle算法也有一定的局限性，首先是要求搜索图中的节点状态都是可逆的，即如果A点能到B点，B点也能一下子回到A点，否则就不存在从终点出发这个说法了。其次是需要额外的数据结构存储找过的节点，一般来说空间足够都采用哈希表。

我们接着来看这道我顺手AC掉的题。先给个原题传送门。

题目大概意思是给出两个位数相同的数，每次可以交换相邻两个数位，或者对一个数位+1（超过9回到0），问需要几次操作才能把第一个数变成第二个数。数据范围每个数不超过9位，并且保证10次操作以内一定能把第一个数变成第二个数，中间过程允许有前导零。

显然从一个节点出发进行搜索这题基本上是会超时的，我们可以估计一下这题的最大复杂度，即考虑9位数，10次操作。

对于一个9位数，一共有9种可能的+1操作（每一个数位都可以+1），一共有8种可能的交换操作（8组相邻的数），共17种操作。也就是搜索树一个节点有17个分支，如果向外搜10层，复杂度大概要17^10。尽管交换操作中可能会搜索到重复的节点，但是这也只是常数上的减少，对于17^10这样的天文数字无论如何是在一秒内解决不了的。

于是我们就想到了meet in the middle，显然这题的数的状态都是可逆的。如果数A到数B是对其中一个数位加一，那么减去这个数位一下子就能回到原来的数，采用了meet in the middle这题的复杂度一下子就降低到了17^5，大约是140W。在这个基础上我们的算法再乘一个常数在一秒内跑完一般是没有问题的。

大概讲下流程：

//标记A表示该点是从起点出发走到的点，标记B表示从终点出发走到的点，每个点对应一个数

（1）起点与重点距离为0，起点加上标记A，终点加上标记B 

（2）起点加入队列，终点加入队列。

（3）如果队列空就结束//虽然不可能，但是广搜一般还是习惯性加上这句

（4）从队列中取出一个点，改点对应数为X

（5）枚举Y为X通过一次操作得到的数

如果哈希表中没有Y，则标上与X相同标记，记录距离为 到X的距离+1，并加入队列，加入哈希表//没有搜索过的节点

如果哈希表中有Y且Y有与X相同标记，则跳过Y//重复搜索的节点

如果哈希表中有Y且Y有与X不同的标记,则直接返回 到X的距离+到Y的距离//找到了

代码就不贴了（因为刷OJ时的代码风格比较丑），实在想看的留下联系方式。

算法应用

其实这个算法在密码学中是有一定地位的。也许大家都听说过DES加密算法与3DES加密算法。其中3DES只是用3个不同秘钥做了3次DES。DES算法之所以现在被淘汰，是因为他的秘钥空间太小。由于只有56位即2^56中可能性，如果有个好点的服务器，把所有可能的秘钥遍历一遍也不过几个小时。而DES算法过后直接提升到了3DES，跳过了2DES，理论上来说2DES秘钥空间也有2^102完全也是足够的，但是为什么不用呢，原因就在于这个meet in the middle算法。假设我知道一组2DES的明文与密文，我希望知道秘钥，我并不需要遍历整个2^102个秘钥。我们可以运用meet in the middle算法，从明文出发枚举2^56个秘钥加密，得到2^56个中间值；然后从密文开始枚举2^56个秘钥解密，得到的所有值中一定有一个与之前加密所得到的相等，于是就完成一次meet in the middle。即得到了一组E（明文，秘钥1）=D（密文，秘钥2）,于是2DES算法的秘钥即为 （秘钥1||秘钥2）。这个过程中，只要有足够大的空间用于存储哈希表，其**密码的时间仅仅相当于**2次DES，安全性并没有实质的提升。

最后

当时XXXXX上课的时候听到还听到上面老教授在讲：之所以用3DES不用2DES是为了防止存在

E（E（明文，秘钥1），秘钥2）=E（明文，秘钥3）这种情况，然后又听到他将Meet in the Middle说成是中间人攻击的时候我就非常确信他在胡诌。尽管也有些地方会把Meet in the Middle称为攻击手段，但是和中间人攻击完全是两码事。其他的还包括他讲3DES算法中为什么第二重用解密不用加密，也并不是像他所说的为了加强混淆，DES算法的加密和解密过程几乎是一致的，没有任何混淆作用。这样做其实只是简单地为了工程考虑，从而更贴合DES算法（3DES的3个秘钥相同直接就能退化成DES）。

虽然我觉得这些也未必是多么重要的密码学概念，毕竟密码学还是非常博大精深的。尽管老师算有点名望的，但是上课瞎讲这种事情我觉得还是极不负责的。