囚徒问题
100个囚犯如何制定最优策略，让所有人都能找到自己的号码？这个问题展示了看似随机的情况下如何通过巧妙的策略提高成功概率。
详细描述
监狱长给100名囚犯一个集体逃脱的机会。每个囚犯都有一个编号（1-100），规则如下：
- 监狱长准备了一个房间，里面有100个抽屉（编号1-100）
- 每个抽屉里放入一个随机的囚犯编号（1-100，完全随机打乱）
- 囚犯们将依次单独进入房间，每人可以打开50个抽屉
- 每个囚犯的目标是找到装有自己编号的抽屉
- 离开房间后不能与其他囚犯交流或传递信息
- 如果所有囚犯都找到了自己的编号，全部释放；否则全部处决
核心问题：
囚犯们应该采取什么策略来最大化生存概率？
常见误解
误解一：随机选择是最好的策略
直觉上，随机打开50个抽屉似乎是最合理的。但实际上，如果100个囚犯都采用随机策略，成功概率将接近于0（具体来说是(1/2)^100）。
误解二：这是一个不可能完成的任务
虽然每个人只能打开一半的抽屉，但通过巧妙的策略，全体囚犯的成功概率可以达到约31%，这是一个惊人的提升。
最优策略
循环策略
每个囚犯按以下步骤行动：
- 第一步：打开与自己编号相同的抽屉（例如，2号囚犯先打开2号抽屉）
- 第二步：如果找到的不是自己的编号，假设找到了编号x，那么下一步就去打开x号抽屉
- 第三步：重复第二步，直到找到自己的编号或已经打开了50个抽屉
举例：3号囚犯先打开3号抽屉，发现里面是7号，于是去打开7号抽屉，发现里面是4号， 再去打开4号抽屉，如此循环直到找到数字3或达到50次尝试。
策略模拟
100次
模拟结果
成功率：
45.0%
平均循环数：
5.6
- 成功(1)/失败(0)
- 平均循环长度
理论分析
为什么这个策略有效？
- 随机排列的数字会形成若干个独立的循环
- 如果囚犯所在的循环长度≤50，他一定能找到自己的编号
- 在随机排列中，所有循环长度都≤50的概率约为31%
- 这个概率远高于随机策略的(1/2)^100
关键在于：所有囚犯使用相同的策略，通过"追踪"数字之间的关联， 把原本独立的搜索变成了有方向的寻找。
现实启示
算法设计启示
- 看似随机的数据中往往隐藏着可利用的结构（如循环）
- 合适的策略可以显著降低问题的复杂度
- 集体行动时，统一的策略比各自为战更有效
实际应用场景
- 分布式系统中的资源分配问题
- 网络路由中的路径发现算法
- 大规模数据处理中的查找优化