python – 生成最佳二叉搜索树(Cormen)

发布时间：2020-12-20 13:19:44 所属栏目：Python 来源：网络整理

导读：我正在阅读Cormen等人的“算法导论”(第3版)( PDF),关于最优二叉搜索树的第15.4节,但是在Python中为optimal_bst函数实现伪代码时遇到了一些麻烦. 以下是我尝试将最佳BST应用于的示例：让我们将e [i,j]定义为搜索包含从i到j标记的密钥的最优二叉搜索树的预期

我正在阅读Cormen等人的“算法导论”(第3版)( PDF),关于最优二叉搜索树的第15.4节,但是在Python中为optimal_bst函数实现伪代码时遇到了一些麻烦.

以下是我尝试将最佳BST应用于的示例：

enter image description here

让我们将e [i,j]定义为搜索包含从i到j标记的密钥的最优二叉搜索树的预期成本.最后,我们希望计算e [1,n],其中n是键的数量(本例中为5).最终的递归表达式是：

enter image description here

应该通过以下伪代码实现：

enter image description here

请注意,伪代码可互换地使用基于1和0的索引,而Python仅使用后者.结果我在实现伪代码时遇到了麻烦.这是我到目前为止：

import numpy as np

p = [0.15,0.10,0.05,0.20]
q = [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如下：

enter image description here

我现在已经调试了几个小时,但仍然卡住了.有人可以指出上面的Python代码有什么问题吗？

解决方法

在我看来,你在指数中犯了一个错误.我不能按预期工作,但下面的代码应该给你一个指示我前往的地方(可能在某个地方有一个关闭)：

import numpy as np

p = [0.15,0.10]
n = len(p)

def get2(m,i,j):
    return m[i - 1,j - 1]


def set2(m,j,v):
    m[i - 1,j - 1] = v


def get1(m,i):
    return m[i - 1]


def set1(m,v):
    m[i - 1] = v


e = np.diag(q)
w = np.diag(q)
root = np.zeros((n,n + 1):
    for i in range(n - l + 2):
        j = i + l - 1
        set2(e,np.inf)
        set2(w,get2(w,j - 1) + get1(p,j) + get1(q,j))
        for r in range(i,j + 1):
            t = get2(e,r - 1) + get2(e,r + 1,j) + get2(w,j)
            if t < get2(e,j):
                set2(e,t)
                set2(root,r)

print(w)
print(e)

结果：

[[ 0.2   0.4   0.5   0.65  0.9   0.  ]
 [ 0.    0.2   0.3   0.45  0.7   0.  ]
 [ 0.    0.    0.1   0.25  0.5   0.  ]
 [ 0.    0.    0.    0.15  0.4   0.  ]
 [ 0.    0.    0.    0.    0.25  0.  ]
 [ 0.5   0.7   0.8   0.95  0.    0.3 ]]
[[ 0.2   0.6   0.8   1.2   1.95  0.  ]
 [ 0.    0.2   0.4   0.8   1.35  0.  ]
 [ 0.    0.    0.1   0.35  0.85  0.  ]
 [ 0.    0.    0.    0.15  0.55  0.  ]
 [ 0.    0.    0.    0.    0.25  0.  ]
 [ 0.7   1.2   1.5   2.    0.    0.3 ]]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!