您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 更多程式設計知識

Ruby 實現最優二叉搜尋樹 (Optimal BST) 動態規劃演算法

編輯：更多程式設計知識

最優二叉搜尋樹問題：給定 n 個鍵值的搜尋機率 p[i] 與 n+1 個虛擬鍵（查找失敗）機率 q[i]，建構一棵二叉搜尋樹，使預期搜尋成本最小化。本文提供基於《演算法導論》動態規劣解法的完整 Ruby 實作，包含成本計算、根節點記錄、樹結構列印。

問題定義

實際鍵：k1...kn，搜尋機率 p[1..n]
虛擬鍵：d0...dn（查找落在區間），機率 q[0..n]
目標：最小化 Σ p[i]*(depth(ki)+1) + Σ q[i]*depth(di)

完整程式碼


# encoding: utf-8
INFINITY = 1.0 / 0.0

# 輸入資料 (導論範例)
keys = ['', 'k1', 'k2', 'k3', 'k4', 'k5']
p = [0, 0.15, 0.10, 0.05, 0.10, 0.20]  # p[1..5]
q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10] # q[0..5]
n = p.size - 1

# DP 表格
e = Array.new(n + 2) { Array.new(n + 1) }   # e[i][j] = i..j 子樹最小期望成本
root = Array.new(n + 2) { Array.new(n + 1) } # root[i][j] = i..j 子樹的根索引

def optimal_bst(p, q, n, e, root)
  w = Array.new(n + 2) { Array.new(n + 1) }  # w[i][j] = i..j 總機率

  # 基底情況：空子樹
  (1..n+1).each do |i|
    e[i][i-1] = q[i-1]
    w[i][i-1] = q[i-1]
  end

  # 子樹長度 l = 1..n
  (1..n).each do |l|
    (1..n-l+1).each do |i|
      j = i + l - 1
      e[i][j] = INFINITY
      w[i][j] = w[i][j-1] + p[j] + q[j]

      # 嘗試每個 r 作為根
      (i..j).each do |r|
        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
        end
      end
    end
  end
end

def print_bst(root, i, j, depth=0, parent=nil, is_left=nil)
  return if i > j
  r = root[i][j]
  indent = "  " * depth
  if parent.nil?
    puts "#{indent}k#{r} is the root of the tree."
  elsif is_left
    puts "#{indent}k#{r} is the left child of k#{parent}."
  else
    puts "#{indent}k#{r} is the right child of k#{parent}."
  end
  print_bst(root, i, r-1, depth+1, r, true)
  print_bst(root, r+1, j, depth+1, r, false)
end

# 執行
optimal_bst(p, q, n, e, root)
print_bst(root, 1, n)
puts "\nThe expected cost is #{e[1][n]}."

執行輸出


k2 is the root of the tree.
  k1 is the left child of k2.
    d0 is the left child of k1.
    d1 is the right child of k1.
  k5 is the right child of k2.
    k4 is the left child of k5.
      k3 is the left child of k4.
        d2 is the left child of k3.
        d3 is the right child of k3.
      d4 is the right child of k4.
    d5 is the right child of k5.

The expected cost is 2.75.

演算法複雜度

時間：O(n³) — 三層巢狀迴圈 (l, i, r)
空間：O(n²) — e, root, w 表格
Knuth 優化：若滿足四邊形不等式與單調性，可降至 O(n²)

關鍵資料結構

表格	含義	索引範圍
`e[i][j]`	鍵 i..j 組成的最優子樹期望成本	1 ≤ i ≤ j ≤ n, 另含 e[i][i-1]
`root[i][j]`	子樹 i..j 的根鍵索引	i ≤ root ≤ j
`w[i][j]`	i..j 總機率和 (p+q)	w[i][j] = w[i][j-1] + p[j] + q[j]