邏輯錯誤時尋找優化的二進制搜索樹在Python

Question

我適於僞代碼用於從Cormen優化的二叉搜索樹算法運行一些樣本數據，但有一個邏輯錯誤的地方，是防止正確的輸出在根目錄。

我覈對Cormen幾次的代碼，它出現的問題是在我的名單指數（標）。

但由於在這種情況下Cormen在圖中同時使用零基礎和一家立足陣列，我完全不知道如何修改我的列表索引來解決這個問題。看來作者打破了這個特定算法典型的基於文本的慣例。

任何對OBST經驗可以看到必要的調整以糾正下面的Python？

def obst(p,q): 
    """Adapted from Cormen, pg. 402""" 
    n = len(q) 
    rn = range(n) 
    e = [[99999]*n for _ in rn] 
    w = [[0]*n for _ in rn] 
    root = [[0]*n for _ in rn] 

    for i in range(1, n): 
     e[i][i - 1] = w[i][i - 1] = q[i - 1] 


    for l in range(1,n): 
     for i in range(1, n-l): 
      j = i+l-1 
      w[i][j] = w[i][j-1] + p[j] + q[j] 
      for r in range(i,j+1): 
       t = e[i][r-1] + e[r+1][j] + w[i][j] 
       if t < e[i][j]: 
        e[i][j] = t 
        root[i][j] = r 
    return (e,root) 

if __name__ == "__main__": 
    p = [0, 0.15, 0.1, 0.05, 0.1, 0.2] 
    q = [0.05, 0.1, 0.05, 0.05, 0.05, 0.1] 
    assert len(p) == len(q) 
    d = obst(p,q,len(p)) 
    print(d[1]) 

編輯：我改變了一些指數。根據Cormen，對於單獨的根表（其是在返回的元組的第二元件）的預期的輸出如下所示：

[ 
    [0, 0, 0, 0, 0, 0], 
    [0, 1, 1, 2, 2, 2], 
    [0, 0, 2, 2, 2, 4], 
    [0, 0, 0, 3, 4, 5], 
    [0, 0, 0, 0, 4, 5], 
    [0, 0, 0, 0, 0, 5], 
    [0, 0, 0, 0, 0, 0] 
] 

我的輸出，當n爲len(p)：

[ 
    [0, 0, 0, 0, 0, 0], 
    [0, 1, 2, 3, 4, 0], 
    [0, 0, 2, 3, 4, 0], 
    [0, 0, 0, 3, 4, 0], 
    [0, 0, 0, 0, 4, 0], 
    [0, 0, 0, 0, 0, 0] 
] 

Answer 1

鑑於你可以映射1..1 + 1回落到0到n，那麼它使事情變得稍微簡單處理：

def obst(p, q): 
    pn = len(p) 
    qn = len(q) 
    e = [[0]*qn for _ in range(qn)] 
    w = [[0]*qn for _ in range(qn)] 
    root = [[0]*pn for _ in range(pn)] 

    for i in range(qn): 
     e[i][i] = q[i] 
     w[i][i] = q[i] 

    for l in range(1, qn): 
     for i in range(0, qn-l): 
      j = i + l 
      e[i][j] = float('inf') 
      w[i][j] = w[i][j-1] + p[j-1] + q[j] 
      for r in range(i, j): 
       t = e[i][r] + e[r+1][j] + w[i][j] 
       if t < e[i][j]: 
        e[i][j] = t 
        root[i][j-1] = r+1 
    return (e, root) 

這僅在矩陣的三角形運行。
輸出：

>>> p = [0.15, 0.1, 0.05, 0.1, 0.2] 
>>> q = [0.05, 0.1, 0.05, 0.05, 0.05, 0.1] 
>>> d = obst(p, q) 
>>> d[1] 
[[1, 1, 2, 2, 2], 
[0, 2, 2, 2, 4], 
[0, 0, 3, 4, 5], 
[0, 0, 0, 4, 5], 
[0, 0, 0, 0, 5]] 
>>> d[0] 
[[0.05, 0.45000000000000007, 0.9, 1.25, 1.75, 2.75], 
[0, 0.1, 0.4, 0.7, 1.2, 2.0], 
[0, 0, 0.05, 0.25, 0.6, 1.2999999999999998], 
[0, 0, 0, 0.05, 0.30000000000000004, 0.9], 
[0, 0, 0, 0, 0.05, 0.5], 
[0, 0, 0, 0, 0, 0.1]] 

注：我除去填充0.0 P中
注：I加1到r，以輸出的確切相同的例子
注：我檢查值e和w和這些也是正確的