成功和不成功搜索的最佳二叉搜索树

Question

我正在研究用C++语言优化二叉搜索树的动态规划算法。我已经构建了自己的程序，但我不知道我的程序是否找到了正确的答案。我尝试在互联网上查找示例代码，但我只是找到了成功搜索的示例代码，因此，我不知道正确的答案。更重要的是，我认为我的编码方式有错误，但我无法指出它。

如果你不明白问题，可以阅读这里最优二叉搜索树

简要描述：这是一个构建最优二叉搜索树的问题。该问题给出了两个集合来记录二叉搜索树中找到和未找到对象的概率。根据给定的数据，我需要计算在二叉搜索树中搜索任意对象的最小成本

以下是我的源代码：

double OptimalBinarySearchTree(double Found[], double Unfound[], int n)
{
    double Cost[n + 2][n + 1], Freq[n + 2][n + 1];
    int i, j, k, l;
    double temp = 0;
    memset(Cost, 0, sizeof(Cost));
    memset(Freq, 0, sizeof(Freq));
    for (i = 1; i <= n; i++)
    {
        Cost[i][i - 1] = Unfound[i - 1];
        Freq[i][i - 1] = Unfound[i - 1];
    }
    for (l = 1; l <= n; l++)
    {
        for (i = 1; i <= n - l + 1; i++)
        {
            j = l + i - 1;
            Freq[i][j] = Freq[i][j - 1] + Found[j] + Unfound[j];
            Cost[i][j] = INT32_MAX;
            for (k = i; k <= j; k++)
            {
                temp = 0;
                if (k > i)
                    temp += Cost[i][k - 1];
                if (k < j)
                    temp += Cost[k + 1][j];
                temp += Freq[i][j];
                if (temp < Cost[i][j])
                    Cost[i][j] = temp;
            }
        }
    }
    return Cost[1][n];
}

例如，当我运行我的程序时

    double Found[7] = {0, 0.15, 0.10, 0.05, 0.10, 0.20};
    double Unfound[7] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10};

我的程序返回的值为 2.45，但也许“真实”答案是 2.85。我不知道我的算法哪里出了问题。我真的需要有人来检查我的程序或算法的正确性。如果您能为我指出，我将非常感激。

Answer 1

据我所知，这两种算法在计算新候选子根的成本时有所不同 E_{i,j} = E_{i,r-1} + E_{r+1,j} + W_{i, j} 当 k = 1 时，您的代码不会添加左子树值，而当 k=j 时，您的代码不会添加右子树值。

        temp = 0;
        if (k > i)
            temp += Cost[i][k - 1];
        if (k < j)
            temp += Cost[k + 1][j];
        temp += Freq[i][j];
        if (temp < Cost[i][j])
            Cost[i][j] = temp;

对于这2个案例，你们有具体的复发实现的理由吗？ 如果不是，这听起来是 DP 算法的其他实现中的情况，或者在您提供的链接中，则重现应该是：

        temp = Cost[i][k - 1] + Cost[k + 1][j] + Freq[i][j];
        if (temp < Cost[i][j])
            Cost[i][j] = temp;

Answer 2

根据算法

Algorithm OBST(p, q, n)
// e[1…n+1, 0…n ] : Optimal sub tree
// w[1…n+1,  0…n] : Sum of probability
// root[1…n, 1…n] : Used to construct OBST

for i ← 1 to n + 1 do
    e[i, i – 1] ← qi – 1
    w[i, i – 1] ← qi – 1
end

for m ← 1 to n do
    for i ← 1 to n – m + 1 do
        j ← i + m – 1 
        e[i, j] ← ∞
        w[i, j] ← w[i, j – 1] + pj + qj
        for r ← i to j do
            t ← e[i, r – 1] + e[r + 1, j] + w[i, j]
            if t < e[i, j] then
                e[i, j] ← t
                root[i, j] ← r
            end
        end
    end
end
return (e, root)

成本（e）和频率（w）的初始化应该针对1到n + 1进行。正如@PhM75所说，不需要对

k > i

和

k < j

进行显式验证 所以，最终的代码应该是

    double OptimalBinarySearchTree(double Found[], double Unfound[], int n)
        {
        double Cost[n + 2][n + 1], Freq[n + 2][n + 1];
        int i, j, k, l;
        double temp = 0;
        memset(Cost, 0, sizeof(Cost));
        memset(Freq, 0, sizeof(Freq));
        for (i = 1; i <= n + 1; i++)
        {
            Cost[i][i - 1] = Unfound[i - 1];
            Freq[i][i - 1] = Unfound[i - 1];
        }
        for (l = 1; l <= n; l++)
        {
            for (i = 1; i <= n - l + 1; i++)
            {
                j = l + i - 1;
                Freq[i][j] = Freq[i][j - 1] + Found[j] + Unfound[j];
                Cost[i][j] = INT_MAX;
                for (k = i; k <= j; k++)
                {
                    temp = Cost[i][k - 1] + Cost[k + 1][j] + Freq[i][j];
                    if (temp < Cost[i][j])
                        Cost[i][j] = temp;
                }
            }
        }
        return Cost[1][n];
    }

最终答案将是 2.75 而不是 2.85