最优二叉搜索树 动态规划

问题描述:现有n个排好序的数\(a_1,a_2,\cdots,a_n\),并且它们的查找概率分别是 \(p_1,p_2,\cdots,p_n\),如何构造一颗二叉排序树,使得平均查找次数最少?

贪心策略:每次选择查询最大的那个元素作为根节点,然后依次左右子树递归构建下去。但是贪心问题不是最优的,可以举一个反例进行反驳。

最优子结构分析:假设有一颗树是当前问题的一个最优查询树,根节点为 \(a_i\) ,那么根节点连接的两颗子树(两个子问题 \(a_1,a_2,\cdots,a_{i-1}\)和 \(a_{i+1},a_{i+2},\cdots,a_n\) )也应该是对应的最优查询树(平均查找次数最少),否则原来那个树就不是最优的树,产生矛盾。因此该问题存在最优子结构性质。

动态规划策略:

首先定义dp数组,定义\(A[i][j]\)表示序列 \(a_{i},a_{i+1},\cdots,a_j\)对应的最优二叉排序树下的最小查询次数。因此原问题就是要求解 \(A[1][n]\)

下面推导状态转移方程:

根据问题的特性当两个子问题要合并成一个大问题的时候,在子问题的基础开销上,子问题的子树上所有节点的高度都增加1,也就是每个节点的开销都需要加上该节点的访问概率,同时根节点的开销是根节点的访问概率,因此也就是从左子问题的头节点的访问概率累加到右子问题的尾节点的访问概率。因此有下面的转态转移方程:

\(A[i][j]=\mathop{min}_{i\leq k\leq j} \{ A[i][k-1]+A[k+1][j] +\sum^{j}_{x=i}p_x \}\)

初始化条件:,当i=j时,即只有一个元素,只能作为根节点。故此时 \( A[i][i]=p_i\)

边界条件:当i>j是,这种情况不合常理,当时在求解的时候回设计到,为了保障算法的正确运行,将这个值设为0,即没有代价。有了这一步,实际上初始化条件都可以改为将\(A[i][i-1]\)直接设为0,可以结合转态转移方程,并分析自底向上计算过程得到这个结论。

计算顺序:自底向上方法,如果要求最优的二叉排序树的结构,可能该需要一个二维数组记录一下树的结构。

时间复杂度:三层循环,上界为O(n*n*n)

空间复杂度:O(n*n)

练习:

答案

发表评论

电子邮件地址不会被公开。 必填项已用*标注