保持菜单顺序的二叉选择树怎样降低平均点击层数:规则演算第06例
把一排按固定顺序排列的选项组织成二叉选择树时,常用选项适合放浅一点,但又不能随意交换左右顺序。这个约束会让问题与任意重排选项的编码树不同。
本例采用的规则
本例七个叶子按编号零至六保持从左到右顺序,每个叶子给出使用权重。每个内部节点只有左右两个分支,每经过一层计一次选择。区间的最优成本由所有可能切分决定:左右子区间成本相加,再加区间内全部权重,因为这些叶子的深度都增加了一层。
具体输入与记录
七项权重[8, 12, 3, 10, 2, 14, 7],从左至右的顺序固定。
各行起点i,各列右开边界1至7,None表示空区间或反向范围: [0, 20, 38, 66, 82, 125, 159] [None, 0, 15, 38, 54, 94, 123] [None, None, 0, 13, 27, 56, 84] [None, None, None, 0, 12, 38, 66] [None, None, None, None, 0, 16, 39] [None, None, None, None, None, 0, 21] [None, None, None, None, None, None, 0] 选择树:[[[0, 1], [2, [3, 4]]], [5, 6]] 叶深度:[3, 3, 3, 4, 4, 2, 2] 加权总代价159,平均层数159/56。
这些记录只描述本次输入。请先确认编号、时间或坐标的起点,再比较中间结果。空集合、数值零以及没有定义分别表达不同含义,不能任意互换。分数保持精确值,显示近似小数并不意味着计算过程按同样位数舍入。
如何独立复算
单个叶子成本为零。表格列出各连续区间的最优成本,输出树用嵌套左右列表表示,叶子仍保持原顺序。最终用每个叶子的权重乘深度再相加,应与区间动态规划的总代价一致。
相同成本时本例选最靠左的切分点。可以枚举所有保持叶序的满二叉树独立比较,验证没有更低成本的树。若忘记在合并时加上整个区间权重,就会漏掉新根给全部叶子增加的一层,得到不合理的零成本。
适用范围
权重只是相对频率,除以权重总和才得到本例加权平均选择层数。这里没有不同按钮耗时、误触或记忆成本,也不允许三叉节点;实际界面的体验不由点击层数这一项完全决定。
复现时可以一次改变一个条件,观察结果从哪一行开始变化。出现差异应先核对规则,再检查输入和每一步状态,而不是直接把最终答案改成表中数字。把输入、边界约定和演算过程一起保存,才能在下一次调整后作出有意义的比较。
