成功和失败搜索的最佳二进制搜索树

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_当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;

对于这两种情况，您有具体的递归实现的原因吗？如果没有，这听起来像是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];
}

注意：不需要使用memset，但保留它是为了保持代码与问题的相似性。

最终答案是2.75而不是2.85