Pubertyly
设计算法,输入如表3-1,输出是最优二叉搜索树的结构,形如:
k2为根
k1为k2的左孩子
d0为k1的左孩子
……
表3-1 搜索概率表
i | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
pi | 0.15 | 0.10 | 0.05 | 0.10 | 0.20 | |
qi | 0.05 | 0.10 | 0.05 | 0.05 | 0.05 | 0.10 |
用动态规划思想求解最优二分查找树问题。
如果一棵最优二叉搜索树T有一棵包含关键字ki,…,kj的子树T’,则T’必然是包含关键字ki,…,kj和伪关键字di-1,…,dj的子问题的最优解。
用剪切-粘贴法证明:
对关键字ki,…,kj和伪关键字di-1,…,dj,如果存在子树T’’,其期望搜索代价比T’低,那么将T’从T中删除,将T’’粘贴到相应位置,则可以得到一棵比T期望搜索代价更低的二叉搜索树,与T是最优的假设矛盾。
利用最优二叉搜索树的最优子结构性来构造最优二叉搜索树。
对给定的关键字ki,…,kj,若其最优二叉搜索树的根结点是kr(i≤r≤j),则kr的左子树中包含关键字ki,…,kr-1及伪关键字di-1 ,…,dr-1,右子树中将含关键字ki+1,…,kj及伪关键字dr,…,dj。
检查所有可能的根结点kr(i≤r≤j),如果事先分别求出含关键字ki,…,kr-1和关键字kr+1,…,kj的最优二叉搜索子树,则可保证找到原问题的最优解。
求解包含关键字ki,…,kj的最优二叉搜索树,其中, i≥1,j≤n 且 j≥i-1。定义e[i,j]:为包含关键字ki,…,kj的最优二叉搜索树的期望搜索代价。
e[1,n]为问题的最终解。
当j≥i时,我们需要从ki,…,kj中选择一个根结点kr,其左子树包含关键字ki,…,kr-1且是最优二叉搜索子树,其右子树包含关键字kr+1,…, kj且为最优二叉搜索子树。
子树的每个结点的深度增加1,根据二叉搜索树的期望搜索代价计算公式,这棵子树对根为kr的树的期望搜索代价的贡献是其期望搜索代价+其所含所有结点的概率之和:
若kr为包含关键字ki,…,kj的最优二叉搜索树(树根),则其期望搜索代价与左、右子树的期望搜索代价e[i,r-1]和e[r+1,j]有如下递推关系:
其中,
故有:
求kr的递归公式为:
测试用例已经在代码中写入,运行程序,结果如图3-1和图3-2,先输出最优二叉搜索树的结构,再输出搜索代价、根节点矩阵、e矩阵和w矩阵。
最优二叉搜索树测试
最优二叉搜索树测试
keyboard_arrow_left上一篇 : 基于python的信号集问题 基于C++实现的大整数计算 : 下一篇keyboard_arrow_right