给定有序数组概率分布时的最优搜索策略

问题回顾 #

我从1到100中想一个整数，你来猜；猜错时我会告知你猜高了还是低了，目标是最小化猜数次数的期望。当整数服从1-100均匀分布时，二分搜索是最优解。但如果整数服从非均匀概率分布（数组p中p[j]为选中数字j的概率），该采用何种策略？

核心分析 #

这个问题本质等价于**最优二叉搜索树（Optimal Binary Search Tree, OBST）**的构建问题：

• 猜数的决策过程对应一棵二叉树：每个节点代表一次猜测的数字，左子树对应“猜高了”的后续猜测，右子树对应“猜低了”的后续猜测，叶子节点就是猜中的数字。
• 期望猜数次数等于所有数字的「猜中次数（对应节点深度）× 概率」之和，我们的目标就是最小化这个总和。

关于你的思路的验证 #

1. 贪心策略的局限性
   你提出的“每次选当前范围中让左右概率和尽可能平衡的数字”是一种直觉贪心策略，在均匀分布下确实退化为二分搜索，但并非在所有非均匀分布下最优。
   比如极端情况：数字1的概率为0.9，其余99个数字的概率总和仅为0.1。此时最优策略是直接先猜1，期望次数为0.9×1 + 0.1×(1+后续猜数次数)，远优于先猜中间数的贪心选择。

2. 不存在统一最优策略
   你的怀疑是正确的：没有适用于所有概率数组p的通用贪心策略，最优策略完全依赖于具体的概率分布。

最优解法：动态规划 #

要得到严格最优的策略，需要通过动态规划计算：

• 定义状态：E[i][j]表示猜测范围为数字i到j时的最小期望猜数次数；W[i][j]表示i到j的概率总和，即W[i][j] = sum(p[k] for k in i..j)。
• 状态转移：对于范围i到j，尝试选择每个k（i ≤ k ≤ j）作为当前猜测的数字，那么期望次数为左子树的期望次数+右子树的期望次数+当前范围的概率总和（因为这次猜测要算一次），即：

  E[i][j] = min(E[i][k-1] + E[k+1][j]) + W[i][j] （k从i到j遍历）
  

• 初始条件：当i == j时，E[i][i] = p[i]（只需要猜一次就中），W[i][i] = p[i]。

通过填充这个二维数组，最终E[1][100]就是最小期望猜数次数，同时可以回溯得到每次应该选择的猜测数字。

内容的提问来源于stack exchange，提问作者Rohit Pandey