文档状态：编辑....

• 今日音乐
  

决策树是一个好东西

Intro

一般情况当我问讨论算法的效率时，有的人注重平均时间复杂度，有的人注重最坏时间复杂度，当注重最坏时间复杂度的时候，决策的路径就已经很明显了，引入决策树的办法还是很好的。

Problem[来源知乎]
一幢 200 层的大楼,给你两个鸡蛋. 如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从前 n-1 层扔鸡蛋都不碎. 这两只鸡蛋一模一样,不碎的话可以扔无数次. 已知鸡蛋在0层扔不会碎.
提出一个策略, 要保证能测出鸡蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少.

最早看见这个问题是在吴育昕学长的Blog中,他的解法很不错，贴上他的回答

面试Hulu的最后一轮, 是我现在的manager zhibing来面试, 他只问了我这一个问题. 不过把200层换成了100层, 把鸡蛋换成了瓶子(瓶子更科学!).

首先搞清楚这题的意思: 第一个瓶子用来试探, 只要它从 kk 层楼扔下去没碎, 则目标就在[k+1,100][k+1,100]之间了. 但一旦运气不好碎了, 对于已知的区间, 我们只能用剩下一个瓶子从小到大一层层试, 因为我们要保证策略必须成功, 不能冒险了.

面试时我得到的题目描述也不太严谨, 没有说"最坏情况下代价最小", 因此我愚昧了一会才明白这题的意思.

"最坏情况下代价最小"这句话十分重要, 它已经反映了题目的数学结构:

我们如果把任何一种策略看成一个决策树, 每一次扔瓶子都会有两个子节点, 对应碎与不碎的情况下下一步应该扔的楼层. 那么, 策略的一次执行, 是树中的一条从根往下走的路, 当且仅当这条路上出现过形如 kk 没碎 与 k+1k+1碎了的一对节点时, 路停止, 当前节点不再扩展. 那么要找的是这么一棵树, 使得所有路里最长者尽量短, 也即, 要找一个最矮的决策树.

再看一个节点处, 选择楼层时会发生什么. 容易看出, 选择的楼层如果变高, 那么"碎子树"高度不减, "不碎子树"高度不增. 同样的, 选择的楼层变矮的话, "碎子树"高度不增, "不碎子树"高度不减.

这时候答案很明显了: 为了使两子树中高度最大者尽量小, 我们的选择应当使两子树高度尽量接近. 最终希望的结果是, 整个二叉树尽量像一个满二叉树.

假设第一次在根节点上, 我们选择扔kk层, 其"碎子树"的高度显然是k−1k−1. 为了考虑不碎子树的高度, 设不碎后第二次扔mm层(显然m>km>k), 则这个新节点的碎子树高度为m−k−1m−k−1, 不碎子树高度仍然未知, 但按照满二叉树的目标, 我们认为它与碎子树相同或少1就好. 那么在根节点上的不碎子树的高度就是m−k−1+1m−k−1+1, 令它与碎子树高度相同, 于是:
m−k−1+1=k−1⇒m=k+k−1
m−k−1+1=k−1⇒m=k+k−1
也即, 如果第一次扔在kk层, 第二次应该高k−1k−1 层, 这可以有直观一点的理解: 每扔一次, 就要更保守一些, 所以让区间长度少1. [1,k)→[k+1,2k−1)[1,k)→[k+1,2k−1). 用类似刚才的分析, 可以继续得到, 下一次应该增高k−2k−2, 再下一次应该增高k−3k−3. 考虑:
k+(k−1)+⋯+1=k(k+1)2=100⇒k≈14
k+(k−1)+⋯+1=k(k+1)2=100⇒k≈14
所以第一次扔14层, 最坏需要14次(策略不唯一, 树的叶子可以交换位置). 200层的话, kk =20.

面试的时候脑子有点乱, 没想到树, 就只是从两边要平均的角度来算的, 所以有点不自信. 最后算出来14之后由于是个近似(其实上取整就对了), 又试了一下15和13. 之后在重新理思路, 这时候貌似已经过了很久,zhibing就问怎么样了, 我说了下答案, 然后说我没有想出很好的办法证明14一定是最优的. zhibing就直接说: 这是对的, 应该是一个等差数列. 然后下一句话就是别的什么了...

所以面试要多说话啊....................!

以上说的是数学做法..代码做法就简单的多, 看面试是要答案还是要程序了.

设f(n,m)f(n,m)为n层楼, m个蛋所需次数, 那么它成了一道DP..

$$
\begin{eqnarray}
f(0, m) & = & 0, (m >= 1)\\
f(n, 1) & = & n, (n >= 1)\\
f(n, m) & = & \min_{1 \le i \le n} \{ \max\{ f(i - 1, m - 1), f(n - i, m)\}\} + 1 \\
\end{eqnarray}
$$
[Doge],有关
$$\min_{1 \le i \le n} \{ \max\{a,b\}\}$$
很简单看出a，b近似时才能达到效果的最优[a,b是存在一定的制约关系的]

实现

#！/usr/bin/env python3
import functools
@functools.lru_cache(maxsize=None)
def f(n, m):
    if n == 0:
        return 0
    if m == 1:
        return n

    ans = min([max([f(i - 1, m - 1), f(n - i, m)]) for i in range(1, n + 1)]) + 1
    return ans

print(f(100, 2))    # 14
print(f(200, 2))    # 20

据大神说python3的functools的一个自带函数, 可以对函数返回结果进行LRU cache, 下次以相同参数调用就不重复计算了.
maxsize=None就是不限制大小, 其实就变成是全部都cache下来, 不考虑LRU了..

好吧：），问题解决了[懒的码代码，copy了一遍]