囚徒逃生问题优化策略

背景介绍

优秀的开发在拿到产品需求后，一定会有一个抽象转化的过程，需要将复杂业务场景转化为高效的算法去实现，而不是按着业务需求开始写流水账式脚本，这个过程其实就和我们解数学题很类似：

分析题目 – 定义变量 – 开始求解。

今天给大家分享的就是一道有意思的数学题，这题是前阵子在网上充（chong）电（lang）时看到的，也欢迎大家提出更优解。

题目

现有编号1至100的100名的囚犯
每个囚犯的编号都写在一张纸条上，这100张纸条，被随机放入一个房间里的100个盒子，每个盒子放一张，这些盒子除了编号外，外观完全相同的。
每个囚犯有一次机会，可单独进入房间，任意查看50次盒子，看完后要将盒子盖上，不能留下任何痕迹。如果他能恰好看到“自己的编号”，视为任务成功，需要立刻离开房间，他也不能与其他人再有交流。
囚犯们可以在开始之前讨论策略。而一旦第一个囚犯进入房间后，囚犯之间就不能有任何交流。
若全部囚犯都在50次内找到自己的编号，则全员释放；任何一个囚犯没有找到自己的编号，则全员处决。
那么请问：囚犯们应该制定怎样的策略，才能尽可能提高全员释放的概率？

大家可以先思考一分钟，再继续往后看。

随机策略

我们先看，囚犯们如果躺平，不指定任何策略，全员逃生的概率。
100个箱子，每个人可看50次，那么每个人成功概率都是1/2,100个人就是：

1/2 * 1/2 *1/2 ······ *1/2 = (1/2)¹⁰⁰

换算成小数就是：0.000000000000000000000000008

这个概率，与大海捞针无异。

环策略

先说策略：

每个囚犯进去，均按自己的编号去找对应的箱子， 若找到，则离开房间； 若未找到，则按箱子里纸条的编号去开下一个对应编号的箱子。
依次类推，直到找到自己的编号或者用完50次次数。

策略听起来很简单，难的是怎么证明这个策略有效。
下面开始证明：
由于纸条和箱子个数都是有限的，且100张纸条均在100个盒子里，没有空盒子，所以每个囚犯按顺序开盒子一定能在最多100次内找到自己的纸条，这个寻址过程实际上形成了一个长度小于等于100的环。
如下图:

这实际上已经形成了闭环：

这也是这个策略被称之为环策略的原因。
接下来，问题就转化成了：求随机排列箱子和其中纸条，组成圆环，其长度小于等于50的概率。

我们先算长度为100的圆环出现的概率：
首先，随机排列的次数为：

100 * 99 * 9······2 * 1 = 100!

实际上，这里的组合又有大量的重复，从一个长度为100的环中任意位置开始寻址，其实都是同一个环，所以结果要再除以100，即长度为100的圆环出现的概率为：

100!/100

已知100张纸条随机放进100个箱子的方案总数是100!
那么得到圆环的长度为100的概率：

(100! /100) /100! =1/100

长度为99的概率，算法都一样，为1/99
依次类推，后续长度为1/98…1/1。

需要指出的是，这里的平均值，也是期望
如果依此类推到环的长度为1，则每次布置纸条都会出现1个长度为1的环，
这里其实是指有时会没有长度为1的环，有时会有多个长度为1的环，平均值为1
依此类推，对于长度>=51的环，平均值和期望是一回事

那么，我们再来看囚犯失败的概率p(f)，其实就是环长度大于等于51的概率，为：

p(f) = 1/51+ 1/52 +1/53 + ······· + 1/100 = 0.69

成功概率p(s)为：

p(s) = 1 - p(f) = 0.31

也就是说，使用环策略之后，逃生概率从(1/2)¹⁰⁰提升到了约1/3，甚至比两人两盒子随机抽取逃生的概率(1/4)更高。

举一反三

那么，如果把囚犯和盒子的数目提升到1000,10000甚至更多的时候，这个结论是否还成立？
如果有趋近于无穷多的囚犯，这个逃生的概率是否会收敛？

1. 我们先来根据上面的算法推导一遍人数增加时的逃生概率：
   

可以看到，到十亿级别的时候，逃生的概率仍然在30%左右，那么是否意味着这个概率就是收敛的呢？
我们继续往下看。
之前计算成功概率时，实际上是拿1减去成功概率，即：

p(s) = 1 - p(f)

而失败概率等于：

p(f) = 1/51 + 1/52 + 1/53 + 1/54 + … + 1/100

失败概率可以用下图矩形部分的面积表示：
y轴表示概率，x轴代表最长环的长度。

在这些矩形的上方贴合着一条曲线，这个曲线就是关于X的反比例函数:
$$\frac{1}{x}$$
曲线下方的50到100的面积之后近似的等于所有矩形面积之和。
而当囚犯数量趋近于无穷时，这个近似估计就越来越精确，这个面积的计算，
实际上就是求反比利函数(1/x)从n到2n定积分：

$$p(f)={\int }_n^{2n}\frac{1}{x}dx=ln2$$

那么成功的概率就为：

$p(s)=1-ln2\approx 30.7$

结果得证，当囚犯数目趋近于无穷大时，使用环策略，
囚犯成功逃生的概率是收敛的，约为30.7%

– by eric02.li

引用资料

https://docs.qq.com/doc/DWWZSRXhyc2NEaEFZ
https://www.youtube.com/watch?v=iSNsgj1OCLA
https://b23.tv/OE0vVCK