动态规划2最优二叉搜索树

最优二叉搜索树问题是指在一棵二叉搜索树中查找某个节点的期望代价最小。其中，期望代价是指查找某个节点所需的平均搜索次数。这个问题可以使用动态规划来解决。具体来说，我们可以定义一个二维数组dp[i][j]表示从i到j的节点构成的子树中的最小期望代价。然后，我们可以通过枚举根节点来递归地计算dp[i][j]。最后，整棵树的最小期望代价就是dp[n]，其中n是节点总数。

在计算dp[i][j]时，我们可以枚举k作为根节点，然后将子树分为左子树和右子树。假设左子树的节点范围是[i,k-1]，右子树的节点范围是[k+1,j]，那么dp[i][j]可以通过以下公式计算得到：

dp[i][j] = min(dp[i][k-1] + dp[k+1][j]) + sum[i][j]

其中，sum[i][j]表示从i到j的节点的概率之和。这个公式的意义是，我们先假设k是根节点，然后计算左子树和右子树的最小期望代价，再加上根节点的代价和。最后，我们枚举所有可能的根节点，选择最小的那个作为dp[i][j]的值。

需要注意的是，我们需要先计算出所有长度为1的子树的最小期望代价，然后再逐步计算出长度为2、3、4……n的子树的最小期望代价。这样才能保证每一层的计算都是基于上一层的最优解的。

相关问题

动态规划求解最优二叉搜索树

### 动态规划求解最优二叉搜索树

#### 定义与目标
最优二叉搜索树（Optimal Binary Search Tree, OBST）是指在一棵给定关键字集合上构建的一棵树，在这棵树中执行查找操作的期望成本最小化。当各个节点被访问的概率不相等时，通过调整这些节点的位置可以减少平均查找长度。

#### 算法描述
为了利用动态规划方法解决这个问题，定义 `C[i][j]` 表示从第 i 到 j 的键构成的最佳子树的成本。对于每一个可能成为根节点的关键字 k(i≤k≤j)，计算左子树 C[i][k−1] 和右子树 C[k+1][j] 的总成本加上所有概率之和 p(k)+∑q(m)(i-1<=m<=j) ，这里 q(m) 是失败匹配的概率。最终的目标是最小化整个表达式的值：

\[ \text{Cost}(i,j)=\min_{i \leq k \leq j}\left(\sum_{r=i}^{j} w(r)+\text { Cost }(i, k-1)+\text { Cost }(k+1, j)\right)[^1] \]

其中 \(w(r)\) 代表成功或失败查询 r 发生的概率权重。

#### Python 实现代码
下面是一个简单的Python程序来展示如何使用动态规划实现上述过程:

def opt_bst(p, q, n):
    e = [[0]*(n+1) for _ in range(n+2)]
    w = [[0]*(n+1) for _ in range(n+2)]
    root = [[0]*(n+1) for _ in range(1+n)]

    for i in range(1, n+2):
        e[i][i-1], w[i][i-1] = q[i-1], q[i-1]
    
    for length in range(1, n+1):  
        for i in range(1, n-length+2):
            j = i + length - 1
            e[i][j], w[i][j] = float('inf'), sum(p[i:j+1]) + sum(q[i-1:j+1])
            
            for r in range(i, j+1):
                t = e[i][r-1] + e[r+1][j] + w[i][j]
                
                if t < e[i][j]:
                    e[i][j], root[i][j] = t, r
                    
    return e, root


if __name__ == "__main__":
    # Example usage with probabilities as input.
    p = [0.15, 0.10, 0.05, 0.10, 0.20]  # Key success probability
    q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]  # Failure match probability
    
    result_e, result_root = opt_bst(p, q, len(p))
    print("Expected cost:", result_e[1][-1])

此代码片段展示了如何创建一个函数 `opt_bst()` 来接收两个列表参数——p 和 q 分别表示成功的查询概率以及失败情况下的概率，并返回预期最低成本矩阵e及其对应的root结构用于重建实际的OBST。

C语言动态规划解决最优二叉搜索树

的实现代码是什么？

以下是C语言动态规划解决最优二叉搜索树的实现代码：

#include <stdio.h>
#include <limits.h>

int sum(int freq[], int i, int j);

int optimalSearchTree(int keys[], int freq[], int n)
{
    int cost[n + 1][n + 1];
    for (int i = 1; i <= n; i++)
        cost[i][i] = freq[i];

    for (int L = 2; L <= n; L++) {
        for (int i = 1; i <= n - L + 1; i++) {
            int j = i + L - 1;
            cost[i][j] = INT_MAX;

            for (int k = i; k <= j; k++) {
                int temp = cost[i][k - 1] + cost[k + 1][j] + sum(freq, i, j);
                if (temp < cost[i][j])
                    cost[i][j] = temp;
            }
        }
    }

    return cost[1][n];
}

int sum(int freq[], int i, int j)
{
    int s = 0;
    for (int k = i; k <= j; k++)
        s += freq[k];
    return s;
}

int main()
{
    int keys[] = {10, 12, 20};
    int freq[] = {34, 8, 50};
    int n = sizeof(keys) / sizeof(keys[0]);
    printf("Cost of Optimal BST is %d", optimalSearchTree(keys, freq, n));
    return 0;
}

这段代码实现了动态规划解决最优二叉搜索树的算法。其中，keys[]表示二叉搜索树中每个节点的键值，freq[]表示每个键值出现的次数，n表示节点数。代码中，先初始化cost[i][i]为freq[i]，然后枚举节点数L和起始节点i，实现了二叉搜索树的动态规划过程，最终返回cost[1][n]作为最优二叉搜索树的代价。