求解最优二叉查找树：输入概率求平均搜索结点数

构建最优二叉查找树（Optimal Binary Search Tree, OBST）是一个经典的动态规划问题。我们需要定义几个重要的概念： 1. 权重：每个关键字和虚拟键的搜索概率。 2. 子问题：给定一组关键字`k[i..j]`和相应的权重`p[i..j]`以及虚拟键的权重`q[i-1], q[j]`，我们需要找到最优二叉查找树。 3. 期望代价：搜索每个关键字或虚拟键的期望访问结点总数。 接下来，我们定义几个动态规划数组： - `e[i][j]`：对于关键字`k[i..j]`，构建最优二叉查找树时的期望代价。 - `w[i][j]`：对于关键字`k[i..j]`，构建最优二叉查找树时，从根节点到这些关键字的总权重（包括虚拟键）。 - `root[i][j]`：对于关键字`k[i..j]`，构建最优二叉查找树时的根节点。 然后，我们使用动态规划的方法填充这些数组。`e[1][n]`会包含最优二叉查找树的期望代价，`root[1][n]`会告诉我们哪个关键字或虚拟键是根节点。 这里是一个高层次的算法 1. 初始化`w[i][i] = p[i] + q[i-1] + q[i]`，其中`i`从1到`n`。 2. 对于所有长度为`l`的子序列`k[i..i+l-1]`，其中`l`从2到`n`，`i`从1到`n-l+1`： - 对于每个可能的根节点`r`（`i`到`i+l-1`之间）： - 计算`e[i][i+l-1]`，使用公式`e[i][i+l-1] = e[i][r-1] + e[r+1][i+l-1] + w[i][r-1] * w[r+1][i+l-1]`。 - 更新`root[i][i+l-1]`为使得`e[i][i+l-1]`最小的`r`。 - 更新`w[i][i+l-1] = w[i][r-1] + w[r][i+l-1] + p[r]`。 3. 输出`e[1][n]`作为答案。 下面是算法的伪代码实现： ```plaintext 输入: 概率数组 p[1..n], q[0..n] 输出: 最优二叉查找树的期望代价 e[1][n] 初始化 w[i][i] = p[i] + q[i-1] + q[i] 对于所有 i 从 1 到 n 初始化 e 和 root 为无穷大 对于长度 l 从 2 到 n: 对于 i 从 1 到 n-l+1: j = i + l - 1 w[i][j] = w[i][j-1] + p[j] + q[j] 对于 r 从 i 到 j: t = e[i][r-1] + e[r+1][j] + w[i][r-1] * w[r+1][j] 如果 t < e[i][j]: e[i][j] = t root[i][j] = r 输出 e[1][n] 作为平均搜索每个结点的访问结点数的值 ``` 这个算法的时间复杂度是O(n^3)，因为对于每个可能的子序列长度`l`，我们可能需要遍历所有可能的根节点`r`。 将`e[1][n]`输出为最终的答案，并格式化保留两位小数。在实际编程实现时，需要注意处理浮点数精度问题，比如使用`double`类型来存储概率和期望代价，并可能在输出时使用`printf`的格式化选项来控制小数位数。 ######[AI写代码神器 | 916点数解答 | 2024-06-17 14:32:16]