Cấu trúc dữ liệu và Giải thuật Bài 142: Thuật toán Cost-Scaling (Goldberg-Tarjan Min-Cost Flow) - Giải quyết bài toán luồng chi phí cực tiểu trong thời gian đa thức yếu và đa thức mạnh.

Ở Bài 141, chúng ta đã tối ưu bài toán luồng chi phí cực tiểu bằng thuật toán đường tăng luồng liên tiếp (Successive Shortest Path - SSP) kết hợp thế năng Johnson. Tuy nhiên, SSP tồn tại một điểm nghẽn nghiêm trọng: độ phức tạp thời gian $O(F \cdot E \log V)$ phụ thuộc trực tiếp vào tổng lượng luồng $F$. Khi dung lượng các cạnh lớn (ví dụ $c(e) \approx 10^9$), SSP là thuật toán đa thức giả (pseudo-polynomial) và có thể chạy hàng tỷ bước.

Để khắc phục hoàn toàn sự phụ thuộc vào $F$, Andrew V. Goldberg và Robert E. Tarjan (1987, 1990) đã phát triển Thuật toán Cost-Scaling (Tỷ lệ hóa chi phí). Bằng cách tổng quát hóa mô hình Push-Relabel từ bài toán Max-Flow sang Min-Cost Flow kết hợp nguyên lý xấp xỉ $\epsilon$-tối ưu ($\epsilon$-optimality), thuật toán đạt độ phức tạp đa thức yếu (Weakly Polynomial) $O(V^3 \log(V C))$ và có thể mở rộng thành đa thức mạnh (Strongly Polynomial) $O(V^2 E \log V)$, độc lập hoàn toàn với dung lượng luồng.

1. Bản chất Toán học: $\epsilon$-Tối ưu hóa và Hàm giá đỉnh

Cho mạng có hướng $G = (V, E)$ với dung lượng $c(u, v)$ và chi phí đơn vị $w(u, v)$.

Mỗi đỉnh $u \in V$ được gán một biến đối ngẫu gọi là giá đỉnh (price) hoặc thế năng $p(u) \in \mathbb{R}$.

Chi phí rút gọn (Reduced Cost)

Với mỗi cạnh $(u, v)$ trong đồ thị thặng dư $G_f$, chi phí rút gọn $w_p(u, v)$ được định nghĩa:

$$w_p(u, v) = w(u, v) - p(u) + p(v)$$

Khái niệm $\epsilon$-Tối ưu ($\epsilon$-Optimality)

Một luồng khả thi $f$ được gọi là $\epsilon$-tối ưu đối với vector giá đỉnh $p$ (với $\epsilon \ge 0$) nếu mọi cạnh thặng dư đều thỏa mãn:

$$\forall (u, v) \in E_f: \quad w_p(u, v) \ge -\epsilon$$

   Trường hợp c_p(u, v) >= 0: Cạnh thỏa mãn điều kiện tối ưu tuyệt đối (Complementary Slackness)
   Trường hợp -ε <= c_p(u, v) < 0: Cạnh được phép mang luồng vi phạm nhẹ trong ngưỡng sai số ε
   Trường hợp c_p(u, v) < -ε: Bị cấm hoàn toàn trong trạng thái ε-tối ưu!

Định lý Hội tụ nguyên (Integer Rounding Theorem)

Định lý: Giả sử tất cả chi phí cạnh $w(u, v)$ đều là số nguyên. Nếu luồng $f$ là $\epsilon$-tối ưu với:

$$\epsilon < \frac{1}{\vert{}V\vert{}}$$

thì $f$ chính là luồng có chi phí cực tiểu tối ưu tuyệt đối.

Chứng minh: Xét mọi chu trình đơn $C$ trong đồ thị thặng dư $G_f$. Chi phí thực của chu trình bằng tổng chi phí rút gọn của các cạnh trên chu trình:

$$\sum_{e \in C} w(e) = \sum_{e \in C} w_p(e) \ge \vert{}C\vert{} \cdot (-\epsilon) > \vert{}V\vert{} \cdot \left(-\frac{1}{\vert{}V\vert{}}\right) = -1$$

Vì mọi $w(e)$ là số nguyên, tổng chi phí $\sum_{e \in C} w(e)$ phải là số nguyên. Một số nguyên strictly lớn hơn $-1$ thì bắt buộc phải $\ge 0$. Đồ thị thặng dư không chứa bất kỳ chu trình âm nào, do đó $f$ đạt tối ưu toàn cục.

2. Khung thuật toán Cost-Scaling và Thủ tục Refine

Thuật toán chia quá trình tính toán thành nhiều pha (Scaling Phases). Bắt đầu với một giá trị $\epsilon$ rất lớn, sau mỗi pha ta giảm $\epsilon$ đi một nửa ($\epsilon \leftarrow \lfloor \epsilon / 2 \rfloor$) cho đến khi $\epsilon < 1 / \vert{}V\vert{}$ (hoặc $\epsilon = 0$ khi chi phí đã được nhân tỷ lệ trước).

Cấu trúc tổng thể:

1. Khởi tạo: Nhân tất cả chi phí cạnh với $(\vert{}V\vert{} + 1)$ để chuyển điều kiện dừng về $\epsilon < 1$.

   Đặt $\epsilon = \max_{(u, v) \in E} \vert{}w(u, v)\vert{}$, vector giá $p(u) = 0$, luồng $f(e) = 0$.

2. Vòng lặp Scaling: Khi $\epsilon \ge 1$:

   • Gọi hàm Refine(f, p, \epsilon) để biến luồng hiện tại từ $2\epsilon$-tối ưu thành $\epsilon$-tối ưu.

   • Cập nhật $\epsilon \leftarrow \lfloor \epsilon / 2 \rfloor$.

3. Cơ chế hoạt động của thủ tục Refine (Push-Relabel for Min-Cost)

Mục tiêu của Refine(f, p, \epsilon) là loại bỏ tất cả các cạnh có $w_p(u, v) < 0$ mà vẫn giữ cho mọi cạnh thặng dư thỏa mãn $w_p(u, v) \ge -\epsilon$:

Bước 1: Bão hòa cạnh âm (Push to Saturate)

Với mọi cạnh thặng dư $(u, v) \in E_f$ có $w_p(u, v) < 0$:

• Đẩy toàn bộ dung lượng thặng dư còn lại qua cạnh: $\Delta = c_f(u, v)$.

• Thao tác này triệt tiêu cạnh xuôi khỏi đồ thị thặng dư. Cạnh ngược $(v, u)$ sinh ra sẽ có chi phí rút gọn $w_p(v, u) = -w_p(u, v) > 0 \ge -\epsilon$ (hoàn toàn thỏa mãn tính $\epsilon$-tối ưu).

• Việc đẩy luồng tạo ra số dư luồng (excess) tại các đỉnh: $e(u) = \text{in\_flow}(u) - \text{out\_flow}(u)$.

Bước 2: Khử số dư bằng Push và Relabel

Định nghĩa cạnh chấp nhận được (Admissible Edge): Cạnh $(u, v) \in E_f$ thỏa mãn $w_p(u, v) < 0$.

Lặp lại khi còn đỉnh $u$ có $e(u) > 0$:

1. Push: Nếu tồn tại cạnh chấp nhận được $(u, v)$, đẩy một lượng luồng $\delta = \min(e(u), c_f(u, v))$ từ $u$ sang $v$.

2. Relabel (Tăng giá đỉnh): Nếu không còn cạnh chấp nhận được nào xuất phát từ $u$ (tức là $w_p(u, v) \ge 0$ với mọi $(u, v) \in E_f$), ta nâng giá đỉnh $p(u)$:

   $$p(u) \gets \min_{(u, v) \in E_f} \{ p(v) + w(u, v) + \epsilon \}$$

Tính chất then chốt: Khi relabel, giá $p(u)$ tăng ít nhất $\epsilon$. Cạnh đạt giá trị cực tiểu sẽ có $w_p(u, v^*) = -\epsilon < 0$, lập tức trở thành cạnh chấp nhận được cho bước Push tiếp theo mà không làm bất kỳ cạnh thặng dư nào khác vi phạm ngưỡng $-\epsilon$.

4. Hiện thực hóa Cost-Scaling bằng Golang

Chương trình Golang dưới đây giải quyết bài toán Min-Cost Circulation với nhu cầu tại các đỉnh (Node Demands) bằng thuật toán Cost-Scaling của Goldberg-Tarjan:

Go

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

type Edge struct {
	to      int
	rev     int
	cap     int64
	flow    int64
	cost    int64 // Chi phí đã scale
	rawCost int64 // Chi phí gốc
}

type CostScalingMCMF struct {
	n       int
	adj     [][]Edge
	demands []int64
	excess  []int64
	price   []int64
	scale   int64
}

func NewCostScalingMCMF(n int) *CostScalingMCMF {
	return &CostScalingMCMF{
		n:       n,
		adj:     make([][]Edge, n),
		demands: make([]int64, n),
		excess:  make([]int64, n),
		price:   make([]int64, n),
		scale:   int64(n + 1), // Hệ số scale để epsilon < 1 tương đương tối ưu
	}
}

func (cs *CostScalingMCMF) SetDemand(u int, d int64) {
	cs.demands[u] = d
}

func (cs *CostScalingMCMF) AddEdge(from, to int, cap, cost int64) {
	scaledCost := cost * cs.scale
	fwd := Edge{to: to, rev: len(cs.adj[to]), cap: cap, flow: 0, cost: scaledCost, rawCost: cost}
	bwd := Edge{to: from, rev: len(cs.adj[from]), cap: 0, flow: 0, cost: -scaledCost, rawCost: -cost}
	cs.adj[from] = append(cs.adj[from], fwd)
	cs.adj[to] = append(cs.adj[to], bwd)
}

func (cs *CostScalingMCMF) reducedCost(u int, e *Edge) int64 {
	return e.cost - cs.price[u] + cs.price[e.to]
}

// Bão hòa các cạnh âm và đẩy luồng trong một pha epsilon
func (cs *CostScalingMCMF) refine(eps int64) {
	// 1. Bão hòa mọi cạnh có chi phí rút gọn âm
	for u := 0; u < cs.n; u++ {
		for i := range cs.adj[u] {
			e := &cs.adj[u][i]
			resCap := e.cap - e.flow
			if resCap > 0 && cs.reducedCost(u, e) < 0 {
				e.flow += resCap
				cs.adj[e.to][e.rev].flow -= resCap
				cs.excess[u] -= resCap
				cs.excess[e.to] += resCap
			}
		}
	}

	// 2. Thu thập các đỉnh có số dư dương vào hàng đợi
	queue := make([]int, 0, cs.n)
	inQueue := make([]bool, cs.n)
	for u := 0; u < cs.n; u++ {
		if cs.excess[u] > 0 {
			queue = append(queue, u)
			inQueue[u] = true
		}
	}

	// 3. Vòng lặp Push - Relabel
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		inQueue[u] = false

		for cs.excess[u] > 0 {
			pushed := false

			// Tìm cạnh chấp nhận được để Push
			for i := range cs.adj[u] {
				e := &cs.adj[u][i]
				resCap := e.cap - e.flow
				if resCap > 0 && cs.reducedCost(u, e) < 0 {
					delta := cs.excess[u]
					if resCap < delta {
						delta = resCap
					}

					e.flow += delta
					cs.adj[e.to][e.rev].flow -= delta
					cs.excess[u] -= delta
					cs.excess[e.to] += delta

					if cs.excess[e.to] > 0 && !inQueue[e.to] {
						queue = append(queue, e.to)
						inQueue[e.to] = true
					}

					pushed = true
					if cs.excess[u] == 0 {
						break
					}
				}
			}

			// Nếu không thể Push, tiến hành Relabel
			if cs.excess[u] > 0 && !pushed {
				var minPrice int64 = INF
				for _, e := range cs.adj[u] {
					if e.cap-e.flow > 0 {
						val := cs.price[e.to] + e.cost + eps
						if val < minPrice {
							minPrice = val
						}
					}
				}
				if minPrice < INF {
					cs.price[u] = minPrice
				}
			}
		}
	}
}

// Solve giải bài toán Min-Cost Flow bằng Cost-Scaling
func (cs *CostScalingMCMF) Solve() (bool, int64) {
	// Khởi tạo excess ban đầu từ nhu cầu các đỉnh
	// demand > 0: đỉnh tiêu thụ -> cần nhận luồng -> excess ban đầu âm (-d)
	// demand < 0: đỉnh cung cấp -> dư luồng -> excess ban đầu dương (-d)
	var maxCost int64 = 0
	for u := 0; u < cs.n; u++ {
		cs.excess[u] = -cs.demands[u]
		for _, e := range cs.adj[u] {
			if e.cap > 0 {
				absC := e.cost
				if absC < 0 {
					absC = -absC
				}
				if absC > maxCost {
					maxCost = absC
				}
			}
		}
	}

	eps := maxCost
	if eps == 0 {
		eps = 1
	}

	// Vòng lặp Scaling
	for eps >= 1 {
		cs.refine(eps)
		eps /= 2
	}

	// Kiểm tra tính khả thi: mọi excess phải triệt tiêu về 0
	for u := 0; u < cs.n; u++ {
		if cs.excess[u] != 0 {
			return false, 0
		}
	}

	var totalCost int64 = 0
	for u := 0; u < cs.n; u++ {
		for _, e := range cs.adj[u] {
			if e.flow > 0 {
				totalCost += e.flow * e.rawCost
			}
		}
	}

	return true, totalCost
}

func main() {
	// Khởi tạo mạng 4 đỉnh:
	// Đỉnh 0: Nguồn cung (+4 đơn vị -> demand = -4)
	// Đỉnh 3: Đích tiêu thụ (+4 đơn vị -> demand = +4)
	// Đỉnh 1, 2: Trạm trung gian (demand = 0)
	n := 4
	solver := NewCostScalingMCMF(n)

	solver.SetDemand(0, -4)
	solver.SetDemand(1, 0)
	solver.SetDemand(2, 0)
	solver.SetDemand(3, 4)

	// Các cạnh: (from, to, capacity, unit_cost)
	solver.AddEdge(0, 1, 3, 2)
	solver.AddEdge(0, 2, 3, 5)
	solver.AddEdge(1, 2, 2, 1)
	solver.AddEdge(1, 3, 4, 4)
	solver.AddEdge(2, 3, 3, 1)

	feasible, minCost := solver.Solve()
	if !feasible {
		fmt.Println("Không tìm thấy cấu hình luồng khả thi!")
		return
	}

	fmt.Println("=== KẾT QUẢ THUẬT TOÁN GOLDBERG-TARJAN COST-SCALING ===")
	fmt.Printf("Tổng chi phí tối thiểu toàn mạng: %d\n", minCost)
	fmt.Println("\nPhân bổ luồng trên các cung:")
	for u := 0; u < n; u++ {
		for _, e := range solver.adj[u] {
			if e.cap > 0 && e.flow > 0 {
				fmt.Printf("- Cung %d -> %d: Luồng = %d/%d | Đơn giá = %d | Chi phí = %d\n",
					u, e.to, e.flow, e.cap, e.rawCost, e.flow*e.rawCost)
			}
		}
	}
}

5. Phân tích Độ phức tạp: Đa thức yếu và Đa thức mạnh

Tại sao đạt được chặn thời gian đa thức?

1. Số pha scaling: Giá trị $\epsilon$ ban đầu là $O(V \cdot C)$. Mỗi pha giảm $\epsilon$ đi một nửa, do đó có tối đa $O(\log(V C))$ pha.

2. Số lần Relabel trong mỗi pha: Tổng mức tăng giá đỉnh của mỗi nút trong một pha bị chặn bởi $O(V \epsilon)$. Vì mỗi lần relabel giá đỉnh tăng ít nhất $\epsilon$, mỗi đỉnh chỉ bị relabel tối đa $O(V)$ lần. Tổng số lần relabel toàn mạng trong một pha là $O(V^2)$.

3. Số lần Push bão hòa: Mỗi cạnh chỉ có thể bị push bão hòa khi giá hai đầu mút thay đổi, bị chặn bởi $O(V E)$ lần mỗi pha.

6. So sánh toàn diện các Thuật toán Min-Cost Flow

7. Ứng dụng Thực tế

• Công cụ Tối ưu hóa CS2 (Goldberg's Engine): Thư viện chuẩn mực giải Min-Cost Flow trong công nghiệp (như thư viện OR-Tools của Google và LEDA) triển khai thuật toán Cost-Scaling làm lõi xử lý chính cho các đồ thị có hàng triệu đỉnh.

• Lập lịch tài nguyên điện toán đám mây (Cloud Datacenter Workload Allocation): Điều phối hàng trăm nghìn máy ảo (VM) tới các cụm máy chủ vật lý với ràng buộc điện năng và độ trễ mạng cực thấp mà không bị ảnh hưởng bởi dung lượng tài nguyên khổng lồ.

• Quy hoạch mạng lưới Logistics thời gian thực: Giải các bài toán chuỗi cung ứng quy mô toàn cầu khi ma trận chi phí vận tải biến động theo từng phút.