最適な検索ツリーPythonを使用して - コード分析

Question

まず、素朴な質問を申し訳ありません。

：しかし、私は二つのリスト（一連のキーと周波数のセット）を受け取り、2つの答えを返すPythonで動的計画法を使用して、私は最適な検索ツリーを作成しようとしている他の場所

助ける見つけることができませんでした

1 - 最小パスコスト。

2 - その最小コストで生成されたツリー。

私は基本的に、最もアクセスされたアイテム（最もアクセスされたアイテムはルートです）によって編成されたツリーを作成し、そのダイナミックプログラミングソリューションを使用してそのツリーから最小のパスコストを返します。

私は、Pythonを使用して、次の実装コードました：私はその木の最小コスト1.答えは142（マトリックス位置に格納された値[0にしてください出力しようとしている

def optimalSearchTree(keys, freq, n): 
    #Create an auxiliary 2D matrix to store results of subproblems 
    cost = [[0 for x in xrange(n)] for y in xrange(n)] 

    #For a single key, cost is equal to frequency of the key 
    #for i in xrange (0,n): 
    # cost[i][i] = freq[i] 

    # Now we need to consider chains of length 2, 3, ... . 
    # L is chain length. 
    for L in xrange (2,n): 
     for i in xrange(0,n-L+1): 
      j = i+L-1 
      cost[i][j] = sys.maxint 
      for r in xrange (i,j): 
       if (r > i): 
        c = cost[i][r-1] + sum(freq, i, j) 
       elif (r < j): 
        c = cost[r+1][j] + sum(freq, i, j) 
       elif (c < cost[i][j]): 
        cost[i][j] = c 

    return cost[0][n-1] 

def sum(freq, i, j): 
    s = 0 
    k = i 
    for k in xrange (k,j): 
     s += freq[k] 
    return s 

keys = [10,12,20] 
freq = [34,8,50] 
n=sys.getsizeof(keys)/sys.getsizeof(keys[0]) 
print(optimalSearchTree(keys, freq, n)) 

を] [n-1]、ダイナミックプログラミングソリューションに従って）。しかし、残念ながらそれは0を返しています。私はそのコードで問題を見つけることができませんでした。何がうまくいかないの？

Answer 1

あなたのコードには、C/Javaプログラミングの習慣からはっきりと疑わしい記述がいくつかあります。例えば、

keys = [10,12,20] 
freq = [34,8,50] 
n=sys.getsizeof(keys)/sys.getsizeof(keys[0]) 

は、私はあなたがリスト内の項目の数を計算考えると思います。しかし、nは3ではありません。

sys.getsizeof(keys)/sys.getsizeof(keys[0]) 

3.142857142857143

あなたがこれで必要なもの：

n = len(keys) 

つ以上のfind：rがでているのでelif (r < j)は、常にTrueですi（両端を含む）とj（これを含まない）の間の範囲である。 elif (c < cost[i][j])の状態はチェックされません。行列cはループ内で更新されることはありません。そのため、常に0になります。

もう1つの提案：組み込み関数sum()を上書きしないでください。

sum(freq[i:j]) 

Answer 2

import sys 
def optimalSearchTree(keys, freq): 
#Create an auxiliary 2D matrix to store results of subproblems 
n = len(keys) 
cost = [[0 for x in range(n)] for y in range(n)] 
storeRoot = [[0 for i in range(n)] for i in range(n)] 

#For a single key, cost is equal to frequency of the key 
for i in range (0,n): 
    cost[i][i] = freq[i] 

# Now we need to consider chains of length 2, 3, ... . 
# L is chain length. 
for L in range (2,n+1): 
    for i in range(0,n-L+1): 
     j = i + L - 1 
     cost[i][j] = sys.maxsize 
     for r in range (i,j+1): 
      c = (cost[i][r-1] if r > i else 0) 
      c += (cost[r+1][j] if r < j else 0) 
      c += sum(freq[i:j+1]) 
      if (c < cost[i][j]): 
       cost[i][j] = c 
       storeRoot[i][j] = r 
return cost[0][n-1], storeRoot 

if __name__ == "__main__" : 

keys = [10,12,20] 
freq = [34,8,50] 
print(optimalSearchTree(keys, freq))