algorithm - O(n^2) 中的 Knuth 最优二叉搜索树

Question

我正在尝试实现可以​​在 O(n^2) 时间内运行的 Knuth 的最佳二叉搜索树。我有在 O(n^3) 中运行的代码。

float P[N + 1] = {0, .13, .12, .15, .05, .12, .10, .08, .09, .03, .13};
float sum[N + 1] = {0, .13, .25, .40, .45, .57, .67, .75, .84, .87, 1.00};
float M[N + 1][N + 1];
int root[N + 1][N + 1];
int s, i, j;
float temp;
for (s = 0; s <= N; s++){
    for (i = 0; i <= N; i++){
        M[s][i] = 0;
        root[s][i] = 0;

    }

}
for (s = 2; s <= N; s++){
    for (i = 1; i <= N - s + 1; i++){
        M[s][i] = N;
        for (j = i; j <= i + s - 1; j++){
            temp = M[j - i][i] + M[i + s - j - 1][j + 1]+ sum[i + s - 1] - sum[i - 1] - P[j];
            if (M[s][i] > temp){
                M[s][i] = temp;
                root[s][i] = j;

            }

        }

    }
}

M 是成本数组。P 是每个节点的概率。我从以下方面得到一些想法：动态编程：为什么 Knuth 改进了最优二叉搜索树 O(n^2)？. 就我而言，我尝试将第三个循环从 修改for (j = i; j <= i + s - 1; j++)为for (j = root[s+1][i]; j <= root[s][i-1]; j++)。但它不起作用。有人可以给我一些关于这个问题的线索吗？

标签： algorithmbinary-search-treedynamic-programmingknuth

Answer 1

You're supposed to be computing the costs of the optimal subtrees in non-decreasing order by size, so when you're filling in M[s][i] --- the minimum cost of a subtree of size s whose leftmost key has index i --- you haven't filled in M[s+1][i] or root[s+1][i] yet.

Cheers, Travis

PS "j <= root[s][i-1]" isn't quite right either.