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

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(1)+ p(1)).

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

我的困惑是c(i,k-1)与w(i,k-1)的区别.

文本是Horowitz,Sahni和Rajasekeran的计算机算法,但我也读过OBST上的CLRS并在线搜索,我所遇到的任何内容都没有很好地解释这些部分之间的差异.

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)}

如果我们选择密钥k作为根,则c(i,k-1)+ w(i,k-1)重新表示左子树的成本.c(k,j)+ w(k,j)表示右子树的成本.p(k)表示根k的成本.

请注意:如果我们选择键k作为根,则左子树包含键ki,...,k(k-1),右子树包含kyes 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)将是左子树的正确成本!