[LeetCode][458. 可怜的小猪] 从 经典面试问题 到 信息论

By Long Luo

Leetcode 458. 可怜的小猪 题解。

这道题让我想起了一个经典面试题：1000瓶药水，其中1瓶有毒，最少要几只老鼠？，答案如下：

1. 给 $1000$ 瓶药水按 $0-999$ 编号，把十进制转为二进制，每一只老鼠喝掉对应为 $1$ 的药水；
2. 再根据老鼠“死活”的状态确定药水的编号。

总共需要 $10$ 只就够了，$2^{10}=1024>1000$。

然后受了这个思维定势，以为需要将 $\textit{buckets}$ 瓶液体转成二进制，按照类似方法进行处理，然而却迟迟行不通，那么问题出在哪里呢？为什么这道面试题可以转成二进制进行处理？具体到这道题目却不行呢？

信息论

同样有一道面试题 N个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？ ，这道题本质上是考察信息论。

假设 $n$ 个球中有一个坏球，不知道轻重，并且记坏球出现在位置 $i$ 的概率为 $p_i$，其中 $\Sigma_{i=1}^np_i=1$。那么从信息论的角度来看，其中蕴含的平均信息量为 $H_{total}=-\Sigma_{i=1}^np_ilog_2(p_i)$。

当 $H_{total}$ 取到极大值时，需要满足 $p_1=p_2=...=p_{n-1}=p_n=\frac{1}{n}$，此时 $H_{total}=log_2n$。

每次天平称重会产生 $3$ 种结果，分别记为 $p_{equal}$，$p_{left}$，$p_{right}$ 每次称重可以获得的平均信息量为 $H_{new}=-(p_{equal}log_2(p_{equal})+p_{left}log_2(p_{left})+p_{right}log_2(p_{right}))$，且满足 $p_{equal}+p_{left}+p_{right}=1$。

那么可以得到 $H_{new} \le log_2(3)$，当且仅当 $p_{equal}=p_{left}=p_{right}=\frac{1}{3}$ 时取到等号。

所以题中要求选出 $12$ 个球中的坏球，在最坏的情况下至少需要的次数 $T_{min}=\lceil \frac{max_{H_{total}}}{max_{H_{new}}} \rceil=\lceil log_3(12) \rceil=3$。同理，最坏情况下要分辨出坏球并且推断出坏球是轻是重至少需要的次数为 $T_{min}'=\lceil log_3(25) \rceil=3$，因为最坏情况坏球轻或重的概率相等且为 $\frac{1}{2}$。但是怎样才能取到这个最小值呢？

每次都选平均信息增量最大的称法。

N进制问题

思路与算法：

根据上面的分析，我们知道一只小猪可以进行 $n$ 轮实验 $(n = \textit{minutesToTest} / \textit{minutesToDie})$。

经过所有实验，一只小猪能有多少种状态？

第一轮就死、第二轮死、…、第 $n$ 轮死，生还，所以一共有 $n+1$ 种状态。

$n+1$ 种状态所携带的信息为 $log_2(n+1)$ 比特，这也是一只小猪最多提供的信息量。

回到题设，“ $\textit{buckets}$ 瓶液体中哪一瓶是毒”这件事，也有 $\textit{buckets}$ 种可能性，所以需要的信息量是 $log_2(\textit{buckets})$。

因此一定存在一种“合理设计”的实验，使得我们只要有 $k$ 只猪且满足 $k \times log_2(n+1) \ge log_2(\textit{buckets})$ 时，则我们一定能得到足够的信息量去判断哪一瓶是毒。

当然，香农只是存在性定理，就是指出最理想化的编码算法能达到的位数底线，就是这样的理想算法理论上存在，但是这种理想的算法不一定能在现实中被发现或实现。

具体到这道题，猪猪所带来的信息量多于毒瓶子的信息量，并不代表一定有这样的“实验方案”：即 $k \times log_2(n+1) \ge log_2(\textit{buckets})$ 是“能找到实验方案”的必要不充分条件。

其实我们可以从另一个角度看这个问题。信息熵只是对信息的度量，直观层面我们可以用“状态的数量”取看待一个事件的信息量大小（前提自然是状态概率时相等的）：

我们编码前后的状态两侧状态数分别是 $\textit{buckets}$ 和 $(n+1)^k$（ $k$ 只猪猪、$n$ 轮实验），$k \times log_2(n + 1) \ge log_2(\textit{buckets})$ 实际上代表 $(n+1)^k \ge \textit{buckets}$。

根据“鸽笼原理”，我们一定可以把“第 $i$ 瓶有毒”这一系列事件一个不落地塞到猪猪经过 $n$ 轮后的存活状况的状态集合中，即 $1:1$，一一映射。

为了不失一般性，我们可以这样描述这种编码：

假设有 $64$ 瓶药水、$3$ 只猪、$3$ 轮实验，且 $(3+1)^3=64$，令 $(1,1,1)$ 表示 $3$ 只小猪都死于第一轮，$(1,1,2)$ 表示前 $2$ 只小猪死于第一轮、第 $3$ 只小猪死于第二轮，依次类推。

1. 把“第一瓶药有毒”映射到 $(1,1,1)$，则具体操作是我们把第一瓶药在第一轮同时喂给$3$只小猪；

2. 把“第二瓶药有毒”映射到 $(1,1,2)$，则具体操作是我们把第二瓶药在第一轮同时喂给 $2$ 只小猪、第二轮喂给最后一只小猪；

3. 把“第四瓶药有毒”映射到 $(1,1,4)$，这里 $4$ 代表第三只小猪存活，所以操作比较特殊，第四瓶药水将不喂给第三只小猪。

依次类推，我们可以把每瓶药水，在哪一轮，喂给哪只小猪确定下来。

根据确定好的顺序，将药水混合，以此我们可以通过观察 $(x,y,z)$ 最后的取值，根据我们的映射码本，找到究竟是哪瓶药有毒。不妨更进一步，如果这个时候有第$65$瓶药水，它势必只能和其他某个瓶子共享状态 $(a,b,c)$，那么当实验结果是 $(a,b,c)$ 出现时，我们则只能确定是两瓶药水中的一瓶有毒，具体是哪一瓶，则无从确定了。

所以，信息量足够的情况下，本题一定有解，且解法不止一种。因此，$klog_2(n + 1) >= log_2(\textit{buckets})$ 也是“能找到实验方案”的充分条件。

代码如下所示：

public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    int states = minutesToTest / minutesToDie + 1;
    int pigs = (int) Math.ceil(Math.log(buckets) / Math.log(states));
    return pigs;
}

复杂度分析：

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗