知识卡片

普通读书笔记卡 · 3623.h.2.b

最优搜索树枚举根与权重

理解等级:高级

对有序键区间 [i,j] 枚举根 r。设 e[i,j] 是该区间的最小期望搜索成本,w(i,j) 是区间内所有成功查询概率 pᵢ…pⱼ 与失败查询概率 qᵢ₋₁…qⱼ 的总和。

把左右最优子树接到根下后,区间内每类查询的深度都增加 1,所以除左右成本外还要加一次总概率 w(i,j):e[i,j]=minᵣ(e[i,r−1]+e[r+1,j]+w(i,j))。

只比较根自身概率 pᵣ,无法计入两侧成功与失败查询的深度代价。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 14 章 14.4–14.5 节(`OEBPS/chapter014.xhtml`,文本字符 [90000, 100000);Art_P474–P477)。 - 结论依据:14.5 节按候选根 kᵣ 分成左右区间,子树下移一层使区间所有查询各增一次成本,得到 e[i,j]=minᵣ(e[i,r−1]+e[r+1,j]+w(i,j))。 - 原始内容:The depth of each node in the subtree increases by 1.