萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Ruby 實現矩陣鏈乘法最優括號化:動態規劃完整解析與代碼

問題背景

給定一系列矩陣 A₁, A₂, …, Aₙ,其維度由陣列 p = [p₀, p₁, …, pₙ] 表示(矩陣 Aᵢ 為 pᵢ₋₁ × pᵢ)。矩陣乘法滿足結合律,但不同的括號順序會導致標量乘法次數差異極大。目標是找出使總乘法次數最小的最優括號化順序。

動態規劃核心思路

  • 狀態定義:m[i][j] 表示計算 Aᵢ…Aⱼ 的最小乘法次數;s[i][j] 記錄最優分割點 k。
  • 遞推公式:m[i][j] = min(m[i][k] + m[k+1][j] + pᵢ₋₁·pₖ·pⱼ),對 i ≤ k < j 遍歷。
  • 邊界條件:m[i][i] = 0(單一矩陣無需乘法)。
  • 填表順序:按鏈長 r = 2..n 遞增,再按起始索引 i 遍歷。

完整 Ruby 實現代碼

# encoding: utf-8
# Matrix Chain Multiplication - Dynamic Programming
# Author: xu jin
# Date: Oct 28, 2012

INFINITY = 1.0 / 0.0

# 經典測試數據
p = [30, 35, 15, 5, 10, 20, 25]

# 初始化 DP 表
n = p.size - 1
m = Array.new(n + 1) { Array.new(n + 1, 0) }
s = Array.new(n + 1) { Array.new(n + 1, 0) }

# 1. 計算最小乘法次數與分割點
def matrix_chain_order(p, m, s)
  n = p.size - 1
  (1..n).each { |i| m[i][i] = 0 }

  (2..n).each do |r|           # 鏈長
    (1..n - r + 1).each do |i| # 起始矩陣
      j = i + r - 1
      m[i][j] = INFINITY
      (i...j).each do |k|      # 嘗試所有分割點
        q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
        if q < m[i][j]
          m[i][j] = q
          s[i][j] = k
        end
      end
    end
  end
end

# 2. 遞歸列印最優括號化順序
def print_optimal_parens(s, i, j)
  if i == j
    print "A#{i}"
  else
    print "("
    print_optimal_parens(s, i, s[i][j])
    print_optimal_parens(s, s[i][j] + 1, j)
    print ")"
  end
end

# 3. 封裝處理流程
def process(p, m, s)
  matrix_chain_order(p, m, s)
  print "The optimum order is:"
  print_optimal_parens(s, 1, p.size - 1)
  printf("\nThe total number of multiplications is: %d\n\n", m[1][p.size - 1])
end

# ---- 執行測試 ----
puts "The given array is: #{p}"
process(p, m, s)

# 隨機測試
p_rand = Array.new(rand(10) + 1) { rand(10) + 1 }
puts "The random array is: #{p_rand}"
m_rand = Array.new(p_rand.size) { Array.new(p_rand.size, 0) }
s_rand = Array.new(p_rand.size) { Array.new(p_rand.size, 0) }
process(p_rand, m_rand, s_rand)

代碼關鍵點解析

1. 無窮大常數 INFINITY = 1.0/0.0

Ruby 中 Float::INFINITY 亦可,此處用除零產生無窮大,作為初始最小值比較基準。

2. 索引對應

數學公式通常 1-based,Ruby 陣列 0-based。代碼中 p[i-1]、p[k]、p[j] 精確對應維度陣列,m、s 索引 1..n 直接對應矩陣編號,避免腦內轉換負擔。

3. 遞歸列印括號

print_optimal_parens 利用 s[i][j] 記錄的分割點,遞歸向左、向右展開,自然生成 ((A1(A2A3))((A4A5)A6)) 格式字串。

4. 隨機測試驗證

腳本尾部自動生成隨機維度陣列並再次跑流程,方便快速驗證演算法正確性。

執行範例輸出

The given array is: [30, 35, 15, 5, 10, 20, 25]
The optimum order is: ((A1(A2A3))((A4A5)A6))
The total number of multiplications is: 15125

The random array is: [5, 8, 8, 2, 5, 9]
The optimum order is: ((A1(A2A3))(A4A5))
The total number of multiplications is: 388

複雜度分析

  • 時間複雜度:O(n³) — 三層巢狀迴圈(鏈長、起點、分割點)。
  • 空間複雜度:O(n²) — 兩張 n×n 表。

擴展應用

  • 同樣 DP 結構可用於最優二叉搜尋樹、多邊形三角剖分、石頭合併 等區間 DP 問題。
  • 若需輸出實際乘法順序(而非僅括號),可在遞歸中執行真實矩陣乘法或記錄操作序列。

總結

矩陣鏈乘法是動態規劃教科書級範例,Ruby 簡潔的語法使核心邏輯一目了然。掌握「區間 DP:枚舉長度→枚舉起點→枚舉分割點」範式,即可舉一反三解決大量區間優化問題。

copyright © 萬盛學電腦網 all rights reserved