知识卡片
最优搜索树枚举根与权重
对有序键区间 [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ᵣ,无法计入两侧成功与失败查询的深度代价。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
The depth of each node in the subtree increases by 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.