我正在阅读Cormen et al.的《算法导论》(第3版)(PDF),第15.4节关于最优二叉搜索树,但是在Python中实现optimal_bst
函数的伪代码时遇到了一些问题。
这是我尝试应用最优二叉搜索树的示例:
让我们定义e[i,j]
为包含从标记为i
到j
的键的最优二叉搜索树的预期搜索成本。最终,我们希望计算e[1,n]
,其中n
是键的数量(此示例中为5)。最终递归公式为:
以下伪代码应该被实现:
注意,伪代码交替使用基于1和基于0的索引,而Python仅使用后者。因此,我在实现伪代码时遇到了麻烦。以下是我目前的进展:import numpy as np
p = [0.15, 0.10, 0.05, 0.10, 0.20]
q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]
n = len(p)
e = np.diag(q)
w = np.diag(q)
root = np.zeros((n, n))
for l in range(1, n+1):
for i in range(n-l+1):
j = i + l
e[i, j] = np.inf
w[i, j] = w[i, j-1] + p[j-1] + q[j]
for r in range(i, j+1):
t = e[i-1, r-1] + e[r, j] + w[i-1, j]
if t < e[i-1, j]:
e[i-1, j] = t
root[i-1, j] = r
print(w)
print(e)
然而,如果我运行这个程序,权重
w
会被正确计算,但期望的搜索值e
仍然停留在它们初始化的值上。[[ 0.05 0.3 0.45 0.55 0.7 1. ]
[ 0. 0.1 0.25 0.35 0.5 0.8 ]
[ 0. 0. 0.05 0.15 0.3 0.6 ]
[ 0. 0. 0. 0.05 0.2 0.5 ]
[ 0. 0. 0. 0. 0.05 0.35]
[ 0. 0. 0. 0. 0. 0.1 ]]
[[ 0.05 inf inf inf inf inf]
[ 0. 0.1 inf inf inf inf]
[ 0. 0. 0.05 inf inf inf]
[ 0. 0. 0. 0.05 inf inf]
[ 0. 0. 0. 0. 0.05 inf]
[ 0. 0. 0. 0. 0. 0.1 ]]
我希望
e
、w
和root
的值如下所示:
我已经调试了几个小时,但仍然卡住了。有人能指出上面的Python代码有什么问题吗?