最优二叉查找树的填表过程

最优二叉查找树（Optimal Binary Search Tree）的填表过程可以通过动态规划来实现。假设有 $n$ 个节点，我们定义 $e_{i,j}$ 表示节点 $i$ 到节点 $j$ 中最优二叉查找树中所有节点被访问的期望代价，$w_{i,j}$ 表示节点 $i$ 到节点 $j$ 中所有节点的权值和，其中 $i\leq j$。

则最优二叉查找树的填表过程如下：

1. 初始化所有单个节点的期望代价和权值 $e_{i,i}=w_{i,i}$，$w_{i,i}=p_i$（$p_i$ 表示节点 $i$ 的概率）。

2. 对于每个长度 $l=2,3,...,n$ 的区间 $[i,j]$，计算 $e_{i,j}$ 和 $w_{i,j}$：

$e_{i,j}=\min\limits_{i\leq k\leq j}\{e_{i,k-1}+e_{k+1,j}+w_{i,j}\}$

其中 $k$ 表示最优二叉查找树的根节点。

$w_{i,j}=w_{i,j-1}+p_j$

3. 最终的最优二叉查找树的期望代价为 $e_{1,n}$。

注：以上填表过程中的下标从 $1$ 开始计算。

相关问题

动态规划最优二叉搜索树算法

动态规划最优二叉搜索树算法的基本思想是利用最优子结构来求解问题。首先定义e[i,j]为包含关键字k[i,...,j]的最优二叉搜索树的期望搜索代价，e[1,n]为问题的最终解。算法的过程可以分为以下几个步骤：

1. 初始化：对于每个关键字k[i]，将e[i,i-1]和w[i,i-1]初始化为d[i-1]和d[i-1]的值，其中w[i,i-1]表示权重。

2. 计算子问题：对于每个子问题的长度l（从2到n），计算e[i,j]和w[i,j]的值。其中e[i,j]表示包含关键字k[i,...,j]的最优二叉搜索树的期望搜索代价，w[i,j]表示子树的权重。

3. 填表：根据最优子结构的性质，逐步填充e[i,j]和w[i,j]的值。

4. 寻找根节点：根据填表得到的e和w数组，可以找到最优二叉搜索树的根节点。

5. 构建最优二叉搜索树：根据根节点，递归地构建最优二叉搜索树。

以上就是动态规划最优二叉搜索树算法的基本步骤。通过这个算法，我们可以找到包含给定概率集合的期望搜索代价最小的二叉搜索树。

动态规划最优二叉搜索树节点概率分别为0.1，0.3，0.1，0.2，0.1，虚拟节点分别为0.04，0.02，0.02，0.05，0.06，0.01。填表m和s，病得到最优值

首先，我们需要知道什么是最优二叉搜索树。最优二叉搜索树是指在给定节点概率的情况下，搜索树的期望搜索次数最小。

接下来，我们可以使用动态规划来解决问题。我们定义m[i][j]为从i到j的最优二叉搜索树的期望搜索次数，s[i][j]为从i到j的最优二叉搜索树的根节点。显然，当i>j时，m[i][j]=0。

接着，我们可以通过以下公式来计算m[i][j]和s[i][j]：


其中，w[i][j]表示从i到j的节点和虚拟节点的概率和。

下面是填表的过程：

首先，我们填对角线，即当i=j时，m[i][j]=p[i]，s[i][j]=i。


然后，我们填对角线上方的三角形，从小到大依次填。


最后，我们可以得到最优二叉搜索树的期望搜索次数为1.45。

至于最优解的构造，我们可以根据s[i][j]来进行递归构造。具体来说，当s[i][j]=k时，k为从i到j的最优二叉搜索树的根节点。那么我们可以以k为根节点，递归构造左子树和右子树。左子树的范围为(i,k-1)，右子树的范围为(k+1,j)。

以上就是动态规划求解最优二叉搜索树的过程。