摔玻璃球找临界楼层问题

题目：有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略找出这个临界楼层是第几层？

CSDN和知乎上讲解临界楼层查找问题的文章不少，但是都讲得不全面透彻，本文将全面考虑玻璃球个数和楼层数为任意正整数的解法。

题目中的最优策略是指用最经济的办法即最少的查找次数找出临界楼层。假设你正在参加查找临界楼层策略设计大赛，比赛规则是查找次数最少者获胜。目前球数和楼层数已知，临界楼层未知，也就是说任意一层都是潜在的临界楼层，那么使用某种策略所需查找次数可能会因临界楼层的不同而不同，为了增加获胜的概率，你的策略必须使平均查找次数尽可能小。注意：这样设计出的策略只能增加获胜概率，但不能保证必胜，最终谁能获胜要看临界楼层到底是哪一层，也就是要碰运气。

要使平均查找次数尽可能小，首先想到的就是二分查找：用一个玻璃球在中间层查找，若玻璃球摔碎，则用下一个玻璃球查找该层下方楼层，若玻璃球没碎，则继续查找该层上方楼层。但二分查找真的适用于临界楼层查找问题吗？临界楼层查找与二分查找有什么区别和联系呢？

临界楼层查找与二分查找的区别与联系：

二分查找的关键字可以无限次使用，而临界楼层查找设定了真实场景，查找所用的玻璃球是消耗品且数量有限。

二分查找有关键字在序列中和不在序列中2种情况。当关键字在序列中时，关键字与序列元素的关系有大于、等于、小于3种，其中“等于”是临界点，当关键字等于序列元素时查找成功；当关键字不在序列中时，关键字与序列元素的关系只剩大于和小于2种，其中小于关键字的最大值以及与其相邻的大于关键字的最小值都是临界点，当关键字与二者都比较过后，才能确定查找失败。

临界楼层查找实际上就是二分查找失败的情况。玻璃球与每个楼层的关系只有能摔碎和不能摔碎2种，其中能使玻璃球摔碎的最低楼层是临界点，不能使玻璃球摔碎的最高楼层也是临界点，当玻璃球将2个相邻临界楼层都查找过后，才能确定能使玻璃球摔碎的最低楼层。

可以说，临界楼层查找是二分查找的阉割版。

基于临界楼层查找与二分查找的区别与联系，做以下分析。为叙述方便，事先定义如下变量：玻璃球个数$N$，查找楼层数$L$，平均查找次数$T$。

首先考虑玻璃球数量充足的情况：

当$N$=5, $L$=31时，可以用二分查找的方法来解决问题，此时$T$=5，解空间树为图1所示的二叉查找树（二叉排序树，二叉搜索树）。

查找策略就是从根节点代表的楼层开始查找，若玻璃球摔碎，则用下一个玻璃球查找左子节点代表的楼层，若没有摔碎，则继续查找右子节点代表的楼层，依此类推，直到查找到叶子节点代表的楼层为止，最后一次使玻璃球摔碎的楼层即为临界楼层。

由查找策略可得查找次数即为二叉查找树根节点到叶子节点的路径长度。要满足使平均查找次数尽可能小的条件，就要使二叉查找树的根节点到各叶子节点的路径长度尽量平均，也就是说要按照广度优先的原则来构造二叉查找树（但不必要求每个节点的左右子树节点数尽量相等）。

图1中的二叉查找树是满二叉树，满足广度优先原则。当$N$=5, 16≤$L$≤30时，可以通过删除满二叉树底层部分节点来构造解空间树（结构不唯一，可以是完全二叉树，也可以不是），所得二叉查找树也满足广度优先原则。
                        图1. 当$N$=5, $L$=31时的二叉查找树

接下来考虑玻璃球数量有限的情况：

当$N$=3, $L$=25时，$T$=4.8，解空间树如图2所示。由于只有3个玻璃球，在查找过程中，当第3个玻璃球摔碎时，查找就得结束，也就是说任意查找路径中查找左子节点的次数不能超过2次，因此需要对图1中的二叉查找树剪枝，将不满足条件的节点删除，结果如图2所示。

因此，查找策略要加上一条：若最后一个玻璃球摔碎，即当前查找节点左子树为空时，查找结束。
                        图2. 当$N$=3, $L$=25时的二叉查找树

同理，当$N$=2, $L$=15时，$T$=4.33，解空间树如图3所示。当$N$=1, $L$=5时，$T$=3，解空间树如图4所示。图4中的二叉查找树已经退化成了链表。
                        图3. 当$N$=2, $L$=15时的二叉查找树

                        图4. 当$N$=1, $L$=5时的二叉查找树

上述4种情况中的二叉查找树都是由满二叉树剪枝得到的，下面举一个由完全二叉树剪枝得到的例子。当$N$=3, $L$=17时，$T$=4.29，解空间树如图5所示。注意：当二叉查找树的底层不满时，底层节点的分布位置不唯一，只要避开剪枝位置就行，可以不用完全二叉树剪枝来构造。
                        图5. 当$N$=3, $L$=17时的二叉查找树

综上，利用二叉查找树解决临界楼层查找问题的方法为：
当已知$N$和$L$时，按照广度优先的原则逐层生成一棵二叉查找树，生成过程中要根据$N$值进行剪枝，当二叉树节点个数达到$L$时停止生成，然后按照二叉树中序遍历的顺序，将楼层序号依次填入节点中，接下来就可以按照上文中的查找策略进行查找了。

Python代码实现：
下面用Python代码来构造二叉查找树并模拟临界楼层查找过程，最后对查找策略进行评价，主要评价指标为查找准确率和平均查找次数。

class TreeNode:
    def __init__(self, left_cnt):
        self.layer = None
        self.left = None
        self.right = None
        self.left_cnt = left_cnt


class BiTree:
    def __init__(self):
        self.root = None

    def genBiTree(self, node_limit, left_limit):
        self.root = TreeNode(0)
        node_cnt = 1
        node_queue = [self.root]
        while True:
            root = node_queue.pop(0)
            if root.left_cnt < left_limit:
                root.left = TreeNode(root.left_cnt+1)
                node_queue.append(root.left)
                node_cnt += 1
            if node_cnt == node_limit:
                break
            root.right = TreeNode(root.left_cnt)
            node_queue.append(root.right)
            node_cnt += 1
            if node_cnt == node_limit:
                break

    def inorder_traversal_assign(self, root, sequence):
        if root:
            self.inorder_traversal_assign(root.left, sequence)
            if sequence:
                root.layer = sequence.pop(0)
            self.inorder_traversal_assign(root.right, sequence)


def binary_search_tree(balls_number, layers_number):
    tree = BiTree()
    tree.genBiTree(layers_number, balls_number-1)
    layers_sequence = list(range(1, layers_number+1))
    tree.inorder_traversal_assign(tree.root, layers_sequence)
    return tree.root


def search_critical_layer(root, critical_layer_truth, search_layers, broken_layers):
    test_layer = root.layer
    search_layers.append(test_layer)
    if test_layer >= critical_layer_truth:
        broken_layers.append(test_layer)
        if root.left:
            search_critical_layer(root.left, critical_layer_truth, search_layers, broken_layers)
    else:
        if root.right:
            search_critical_layer(root.right, critical_layer_truth, search_layers, broken_layers)


def record_search_process(balls_number, layers_number, critical_layer_truth):
    if balls_number > 0 and layers_number > 0 and critical_layer_truth in range(1, layers_number+1):
        binary_search_tree_root = binary_search_tree(balls_number, layers_number)
        search_layers = []
        broken_layers = []
        search_critical_layer(binary_search_tree_root, critical_layer_truth, search_layers, broken_layers)
        critical_layer_result = broken_layers[-1]
        return {'critical layer result': critical_layer_result, 'search layers': search_layers, 'broken layers': broken_layers}


def evaluate_search_strategy(balls_number, layers_number):
    correct_result_cnt = 0
    search_times = []
    broken_ball_cnt = 0
    for critical_layer_truth in range(1, layers_number+1):
        search_record = record_search_process(balls_number, layers_number, critical_layer_truth)
        if search_record['critical layer result'] == critical_layer_truth:
            correct_result_cnt += 1
        search_times.append(len(search_record['search layers']))
        broken_ball_cnt += len(search_record['broken layers'])
    search_accuracy = round(correct_result_cnt / layers_number, 2)
    mean_search_times = round(sum(search_times)/layers_number, 2)
    max_search_times = max(search_times)
    mean_broken_number = round(broken_ball_cnt / layers_number, 2)
    return {'search accuracy': search_accuracy, 'mean search times': mean_search_times, 'max search times': max_search_times, 'mean broken number': mean_broken_number}


print(evaluate_search_strategy(5, 31))
print(evaluate_search_strategy(3, 25))
print(evaluate_search_strategy(2, 15))
print(evaluate_search_strategy(1, 5))
print(evaluate_search_strategy(3, 17))

实验结果：
{‘search accuracy’: 1.0, ‘mean search times’: 5.0, ‘max search times’: 5, ‘mean broken number’: 2.58}
{‘search accuracy’: 1.0, ‘mean search times’: 4.8, ‘max search times’: 5, ‘mean broken number’: 2.2}
{‘search accuracy’: 1.0, ‘mean search times’: 4.33, ‘max search times’: 5, ‘mean broken number’: 1.67}
{‘search accuracy’: 1.0, ‘mean search times’: 3.0, ‘max search times’: 5, ‘mean broken number’: 1.0}
{‘search accuracy’: 1.0, ‘mean search times’: 4.29, ‘max search times’: 5, ‘mean broken number’: 2.18}

本文地址：https://blog.csdn.net/weixin_43918780/article/details/107331661