Cấu trúc dữ liệu và Giải thuật Bài 105: Quy hoạch động trên cây (Tree DP) - Giải quyết các bài toán tối ưu trên cấu trúc phân cấp.

Sau khi đã nắm vững các kỹ thuật quy hoạch động trên mảng tuyến tính và trạng thái bitmask, hôm nay chúng ta bước vào một dạng toán cực kỳ tao nhã và thực tế: Quy hoạch động trên cây (Tree Dynamic Programming - Tree DP).

Trong kiến trúc phần mềm cũng như thực tế kỹ thuật, rất nhiều cấu trúc mang tính phân cấp (Hierarchical Structure) như cây thư mục, sơ đồ tổ chức công ty, hệ thống phân quyền (RBAC), hay các mạng lưới phân phối đều có dạng đồ thị vô hướng không chu trình thông suốt gọi là Cây (Tree). Khi cần tối ưu hóa một bài toán trên cây (ví dụ: chọn tập hợp nhân sự sao cho tối đa hóa tổng năng lực mà không có 2 người quản lý - nhân viên trực tiếp nào bị chọn cùng lúc), phương pháp quy hoạch động tuyến tính sẽ thất bại. Lúc này, Tree DP kết hợp với thuật toán DFS (Post-order Traversal) chính là chìa khóa vàng.

1. Bản chất của Quy hoạch động trên cây

Điểm mấu chốt của một cái cây là tính phân rã từ gốc xuống lá và tổng hợp ngược từ lá lên gốc:

1. Một nút gốc $u$ phụ thuộc hoàn toàn vào kết quả của các nút con trực tiếp của nó ($v_1, v_2, \dots, v_k$).

2. Để tính giá trị tối ưu cho nút $u$, ta thực hiện DFS (Depth-First Search) đi sâu xuống tận các nút lá cùng, sau đó tính toán ngược từ dưới lên trên (Post-order).

3. Trạng thái của cây con gốc $u$ chỉ được quyết định dựa trên các trạng thái độc lập của các cây con con cháu bên dưới.

2. Bài toán kinh điển: Maximum Weight Independent Set (MWIS) trên Cây

• Đề bài: Cho một cái cây gồm $N$ đỉnh. Mỗi đỉnh $u$ gắn một trọng số dương $w[u]$ (đại diện cho điểm số hoặc giá trị). Hãy tìm một tập hợp các đỉnh sao cho tổng trọng số lớn nhất, với điều kiện không có hai đỉnh nào kề nhau (có cạnh nối trực tiếp) được cùng chọn.

• Xây dựng trạng thái DP cho mỗi nút $u$:

  • $\text{dp}[u][0]$: Tổng trọng số lớn nhất của cây con gốc $u$ nếu KHÔNG chọn đỉnh $u$. Khi đó, các nút con trực tiếp $v$ của $u$ có thể được chọn hoặc không (ta lấy max(dp[v][0], dp[v][1]) cho từng con).

  • $\text{dp}[u][1]$: Tổng trọng số lớn nhất của cây con gốc $u$ nếu CÓ CHỌN đỉnh $u$. Khi đó, các nút con trực tiếp $v$ của $u$ tuyệt đối không được chọn (ta bắt buộc phải dùng dp[v][0]).

Công thức chuyển trạng thái (Recurrence Relations):

$$\text{dp}[u][0] = \sum_{v \in \text{children}(u)} \max(\text{dp}[v][0], \text{dp}[v][1])$$

$$\text{dp}[u][1] = w[u] + \sum_{v \in \text{children}(u)} \text{dp}[v][0]$$

3. Cài đặt thuật toán Tree DP bằng Golang

Đoạn code Golang dưới đây giải quyết bài toán MWIS trên cây biểu diễn bằng danh sách kề (Adjacency List) với độ phức tạp tối ưu $O(N)$:

Go

package main

import (
	"fmt"
)

var (
	weights []int
	adj     [][]int
	dp      [][2]int // dp[u][0]: không chọn u, dp[u][1]: chọn u
)

func dfs(u int, parent int) {
	// Khởi tạo giá trị ban đầu cho nút u
	dp[u][0] = 0
	weights[u] // Nếu chọn u, lấy trọng số của u
	dp[u][1] = weights[u]

	// Duyệt qua tất cả các nút con
	for _, v := range adj[u] {
		if v == parent {
			continue
		}
		
		// Đệ quy tính toán cho cây con v trước (Post-order)
		dfs(v, u)

		// Công thức chuyển trạng thái Tree DP
		dp[u][0] += max(dp[v][0], dp[v][1])
		dp[u][1] += dp[v][0]
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	// Giả lập một cái cây gồm 5 đỉnh (0 đến 4)
	n := 5
	weights = []int{10, 20, 30, 40, 50} // Trọng số các đỉnh
	adj = make([][]int, n)

	// Thêm các cạnh của cây
	addEdge := func(u, v int) {
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	addEdge(0, 1)
	addEdge(0, 2)
	addEdge(1, 3)
	addEdge(1, 4)

	// Khởi tạo mảng dp
	dp = make([][2]int, n)

	// Chạy DFS từ gốc (đỉnh 0)
	dfs(0, -1)

	// Kết quả lớn nhất tại gốc 0 là max giữa chọn hoặc không chọn gốc 0
	ans := max(dp[0][0], dp[0][1])
	fmt.Printf("Tổng trọng số tập độc lập lớn nhất trên cây: %d\n", ans)
}

4. Ứng dụng thực tế của Tree DP

• Tối ưu hóa sơ đồ tổ chức doanh nghiệp: Chọn danh sách lãnh đạo tham gia hội nghị sao cho tổng năng lực cao nhất mà không xảy ra xung đột cấp trên - cấp dưới trực tiếp.

• Mạng lưới cảm biến không dây (Wireless Sensor Networks): Bài toán chọn các trạm phát sóng phủ kín vùng mà không gây nhiễu sóng lẫn nhau giữa các trạm liền kề.

• Xử lý cú pháp mã nguồn (Abstract Syntax Tree - AST): Tối ưu hóa biểu thức hoặc phân tích ngữ nghĩa trong trình biên dịch.

Tree DP thu gọn các bài toán cấu trúc phân cấp phức tạp thành các bài toán con tuyến tính trong thời gian tuyến tính $O(N)$, thể hiện sức mạnh vượt trội của tư duy quy hoạch động.

Maximum Independent Set in Trees tutorial cung cấp thêm một góc nhìn trực quan và phân tích chi tiết bằng hình ảnh về cách thuật toán vét cạn qua cây tìm ra tập độc lập trọng số lớn nhất trong thời gian tuyến tính.