5

好吧，我希望有人能给我解释一下。我正在为期末考试而学习，但我无法弄清楚一些事情。

问题是动态规划；构建最优二叉搜索树（OBST）。我一般理解动态规划，特别是这个问题的概念，但我不理解这个问题的递归形式。

我知道我们正在为这些节点的越来越多的子集构建最佳二叉搜索树，并将答案保存在表格中以避免重新计算。我还知道，当您在 a_{k} 根树时，从 a_{1} 到 a_{k-1} 的所有成功节点以及它们相应的虚构不成功节点（即树的叶子）都在左子树，然后右子树中的那些是a_{k+1}到a_{n}。

这是我不明白的方程的递归形式：

c(i, j) = min (i < k <= j) {c(i, k-1) + c(k, j) + p(k) + w(i, k-1) + w(k +j)}

其中 w(i, j) = q(i) + 从 i+1 到 j 的总和 (q(l) + p(l))。

所以在 c(i,j) 中，从左到右，我们有左子树的成本 + 右子树的成本 + 成功搜索根的概率 + w(i, k-1) + w(k +j)。

我的困惑是 c(i, k-1) 与 w(i, k-1) 有何不同。

文本是 Horowitz、Sahni 和 Rajasekeran 的计算机算法，但我也阅读了 OBST 上的 CLRS 并在线搜索，我遇到的任何内容都无法很好地解释方程中这些部分之间的差异。

4

2 回答 2

8

c(i,j) 表示搜索包含键 ki, ..., kj 的最优二叉搜索树的预期成本。w(i,j) 表示包含键 ki, ..., kj 的子树的概率和。对于公式：</p> 

c(i, j) = min (i < k <= j) {c(i, k-1) + c(k, j) + p(k) + w(i, k-1) + w(k,j)}

如果我们选择键 k 作为根，c(i,k-1)+w(i,k-1) 表示左子树的成本。c(k,j)+w(k,j) 表示右子树的成本。p(k) 表示根 k 的成本。

注意：如果我们选择键 k 作为根，那么左子树包含键 ki, ..., k(k-1)，右子树包含键 k(k+1), ..., kj . 但我们不能简单地说：

c(i,j)=min (i < k <= j) {c(i, k-1) + c(k, j) + p(k)}

因为当我们为根选择键 k 时，生成的子树的深度增加了 1。所以 c(i,k-1)+w(i,k-1) 将是左子树的正确成本！

于 2012-12-15T15:56:14.960 回答
2

这是一种计算特定深度节点的频率*深度的微妙方法。

每次将节点评估为根时，在总结其左（或右）子树时，您正在添加频率总和以增加所有子节点的深度。

例如，假设节点“A”、“B”和“C”，其中“A”是根节点，“B”是“A”的左子节点，“C”是“B”的左子节点。（没有合适的孩子让事情变得简单。）

以自下而上的方式，以叶“C”为根：

cost is Pr(C) = freqC*1  (no children)

以'B'为根：

cost = Pr(B) + Cost[C,C] + sum of children freq 
     = freqB*1 + freqC*1 + freqC*1
     = freqB*1 + freqC*2 

where Pr(B) = freqB*1
     Cost[C,C] = freqC*1
     sum of children freq = freqC*1

最后，以“A”为根：

cost = Pr(A) + Cost[C,B] + sum of children freq 
     = freqA*1 + freqB*1 + freqC*2 + freqB*1 + freqC*1
     = freqA*1 + freqB*2 + freqC*3

where Pr(A) = freqA*1
     Cost[C,B] = freqB*1 + freqC*2
     sum of children freq = freqB*1 + freqC*1
于 2015-04-16T21:02:59.747 回答