最大的钻石问题

问题

1 楼到 n 楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从 1 楼到 n 楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗？

解答

这个问题的原型是”秘书问题”，属于最佳停止问题。

前提条件

钻石是随机放置的。如果放置是人为干预大小顺序，那么以下分析不成立。

最优策略

采用 1/e 法则（约 37% 法则）：

1. 前 n/e 层（约 37%）只观察不拿，记录这些层中的最大值
2. 从第 n/e + 1 层开始，遇到第一个比之前观察到的最大值更大的钻石就拿
3. 如果到最后一层都没遇到更大的，就拿最后一层的

示例

假设有 10 层楼：

• 前 3-4 层（10/e ≈ 3.7）只观察，记录最大值
• 从第 4 或 5 层开始，遇到比前面更大的就拿
• 这种策略能以约 37% 的概率拿到最大的钻石

关键点

• 这是一个最佳停止问题，需要在探索和利用之间平衡
• 最优策略是 1/e 法则（约 37% 用于观察，63% 用于决策）
• 该策略能以约 37% 的概率获得最大值，是理论最优解
• 前提是钻石随机放置，非人为排序