动态规划的最优二叉查找树的递推公式怎么推导
时间: 2023-11-12 08:15:52 浏览: 31
动态规划的最优二叉查找树问题,通常也称为哈夫曼树问题,它的递推公式可以使用以下方法推导得到:
假设给定一个有序序列 $K=\{k_1,k_2,\cdots,k_n\}$,对应的概率序列为 $p=\{p_1,p_2,\cdots,p_n\}$。我们需要构建一棵二叉查找树 $T$,使得查找所有元素的期望代价最小,其中期望代价为查找每个元素的代价乘以该元素被查找的概率之和。
我们定义 $w_{i,j}$ 表示从 $k_i$ 到 $k_j$ 的所有元素作为叶子节点构成的子树的概率之和,即:
$$ w_{i,j} = \sum_{l=i}^j p_l $$
我们同时定义 $e_{i,j}$ 表示在以 $k_i$ 到 $k_j$ 的元素为叶子节点的子树中进行一次查找的期望代价,即:
$$ e_{i,j} = \begin{cases}
q_{i-1}, & j=i-1 \\
\min\limits_{i\leqslant r \leqslant j}\{e_{i,r-1}+e_{r+1,j}+w_{i,j}\}, & i\leqslant j
\end{cases} $$
其中 $q_{i-1}$ 表示在查找失败时返回 $k_{i-1}$ 的代价,即叶子节点的左侧边界的值的代价。
根据上述定义,我们可以得到最终的递推公式:
$$ e_{i,j} = \begin{cases}
q_{i-1}, & j=i-1 \\
\min\limits_{i\leqslant r \leqslant j}\{e_{i,r-1}+e_{r+1,j}+w_{i,j}\}, & i\leqslant j
\end{cases} $$
这个公式的含义是:对于每个子序列 $K_{i,j}$,我们枚举其中一个元素 $k_r$ 作为根节点,然后将其左侧子序列 $K_{i,r-1}$ 和右侧子序列 $K_{r+1,j}$ 作为 $k_r$ 的左右子树,此时期望代价为左右子树期望代价之和加上 $w_{i,j}$,选择其中最小的作为 $e_{i,j}$。最终,我们可以得到整个序列 $K$ 的最优二叉查找树的期望代价为 $e_{1,n}$。