ปัญหา
มีชุดจำนวนเต็มเรียงลำดับ และอาร์เรย์ freq (Frequency) ต้องสร้าง Binary Search Tree ที่ให้ ต้นทุนค้นหาต่ำสุด (Minimum Search Cost)
วิธีแก้: Dynamic Programming
สร้างอาร์เรย์ช่วย cost[n][n] เก็บคำตอบ Subproblems แบบ Bottom-up
ตัวอย่าง
Keys = {10, 12, 20} Frequency = {34, 8, 50}
Output: Minimum Cost = 142
การคำนวณต้นทุน
- Case 1: (34×1) + (8×2) + (50×3) = 200
- Case 2: (8×1) + (34×2) + (50×2) = 176
- Case 5 (Optimal): (50×1) + (34×2) + (8×3) = 142 (Minimum)
อัลกอริทึม
optCostBst(keys, freq, n)
define cost[n][n]
for i = 0 to n-1: cost[i][i] := freq[i]
for length = 2 to n:
for i = 0 to n-length:
j := i + length - 1
cost[i][j] := ∞
for r = i to j:
c := (r > i ? cost[i][r-1] : 0) + (r < j ? cost[r+1][j] : 0) + sum(freq, i, j)
if c < cost[i][j]: cost[i][j] := c
return cost[0][n-1]
โค้ด C++
// ฟังก์ชัน sum, minCostBST, main - ดูรายละเอียดในต้นฉบับ
Output
Cost of Optimal BST is: 142
