給定一系列矩陣 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 遍歷。# 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)
INFINITY = 1.0/0.0Ruby 中 Float::INFINITY 亦可,此處用除零產生無窮大,作為初始最小值比較基準。
數學公式通常 1-based,Ruby 陣列 0-based。代碼中 p[i-1]、p[k]、p[j] 精確對應維度陣列,m、s 索引 1..n 直接對應矩陣編號,避免腦內轉換負擔。
print_optimal_parens 利用 s[i][j] 記錄的分割點,遞歸向左、向右展開,自然生成 ((A1(A2A3))((A4A5)A6)) 格式字串。
腳本尾部自動生成隨機維度陣列並再次跑流程,方便快速驗證演算法正確性。
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 表。矩陣鏈乘法是動態規劃教科書級範例,Ruby 簡潔的語法使核心邏輯一目了然。掌握「區間 DP:枚舉長度→枚舉起點→枚舉分割點」範式,即可舉一反三解決大量區間優化問題。