动态规划：最优二叉搜索树

Question

好的，我希望有人能够向我解释这个问题。我正在准备期末考试，但无法完全理解动态规划；构造最优二叉搜索树（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的《计算机算法》，但我也阅读了CLRS关于OBST的内容，还搜索了一些在线文章，但没有任何一篇文章能很好地解释方程中这些部分的区别。

- rpmartz

---

q(i)是什么？你能说一下吗？这是用于未成功搜索的吗？ - Ayush

Answer 1

c(i,j)表示包含关键字ki, ..., kj的最优二叉搜索树的期望代价。w(i,j)表示包含关键字ki, ..., kj的子树的概率和。对于公式：

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

c(i, k-1)+w(i, k-1)代表左子树的成本，如果我们选择关键字k作为根节点。 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）将是左子树的正确成本！

- Chasefornone

Answer 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

- mithya