14.3K 214 1.7K

Đã đăng vào khoảng 13 giờ trước 7 phút đọc

Cấu trúc dữ liệu và Giải thuật Bài 144: Chu trình Hamilton và Bài toán Người bán hàng (Traveling Salesperson Problem - TSP) - Tối ưu hóa tổ hợp chính xác bằng Quy hoạch động Held-Karp và Phân nhánh chặn (Branch and Bound).

Trong lý thuyết đồ thị, trong khi Chu trình Euler (Bài 135) đi qua mỗi cạnh đúng một lần và giải quyết được trong thời gian đa thức $O(V + E)$ , thì Chu trình Hamilton (Hamiltonian Cycle) — chu trình đi qua mỗi đỉnh đúng một lần rồi quay về điểm xuất phát — lại là một trong 21 bài toán NP-complete kinh điển của Richard Karp (1972).

Khi mở rộng chu trình Hamilton sang đồ thị có trọng số, ta thu được Bài toán Người bán hàng (Traveling Salesperson Problem - TSP): Tìm chu trình Hamilton có tổng trọng số các cạnh là nhỏ nhất. TSP là bài toán NP-hard cốt lõi của tối ưu hóa tổ hợp. Phương pháp duyệt vét cạn tất cả hoán vị đòi hỏi thời gian $O(N!)$ — một con số bất khả thi ngay cả với $N = 20$ ( $19! / 2 \approx 6 \times 10^{16}$ phép tính).

Để tìm nghiệm chính xác (exact solution), hai phương pháp giải quyết tối ưu nhất bao gồm:

Quy hoạch động Held-Karp (Bellman-Held-Karp): Hạ độ phức tạp từ giai thừa $O(N!)$ xuống hàm mũ $O(N^2 \cdot 2^N)$ bằng kỹ thuật DP trạng thái bitmask.
Phân nhánh và Chặn (Branch and Bound): Sử dụng các hàm chặn dưới dựa trên Cây khung nhỏ nhất (MST Relaxation) kết hợp kỹ thuật cắt tỉa không gian trạng thái, tiết kiệm bộ nhớ $O(N)$ và giải quyết hiệu quả các tập dữ liệu thực tế.

1. Định nghĩa Toán học của Bài toán TSP

Cho một đồ thị có trọng số đầy đủ $G = (V, E, W)$ gồm $N = \vert{}V\vert{}$ đỉnh $\{0, 1, \dots, N-1\}$ . Ma trận khoảng cách $W = [w_{i, j}]$ biểu diễn chi phí di chuyển trực tiếp từ đỉnh $i$ sang đỉnh $j$ ( $w_{i, j} \ge 0$ ).

Một hành trình Hamilton là một hoán vị $\pi = (\pi_0, \pi_1, \dots, \pi_{N-1})$ của tập đỉnh $V$ .

Bài toán TSP tìm hoán vị $\pi$ cực tiểu hóa hàm mục tiêu:

$\min_{\pi} \left( \sum_{i=0}^{N-2} w_{\pi_i, \pi_{i+1}} + w_{\pi_{N-1}, \pi_0} \right)$

Phân loại bài toán:

Symmetric TSP: Khoảng cách hai chiều đối xứng ( $w_{i, j} = w_{j, i}$ với mọi $i, j$ ).
Asymmetric TSP (ATSP): Chi phí có hướng ( $w_{i, j} \neq w_{j, i}$ ).
Metric TSP: Thỏa mãn bất đẳng thức tam giác: $w_{i, j} \le w_{i, k} + w_{k, j}$ với mọi $i, j, k$ .

Vì chu trình là một vòng khép kín, ta luôn có thể cố định đỉnh xuất phát và kết thúc tại đỉnh $0$ mà không làm mất tính tổng quát.

2. Quy hoạch động Held-Karp (Bellman-Held-Karp Algorithm)

Năm 1962, Michael Held, Richard M. Karp và Richard Bellman độc lập phát minh ra phương pháp quy hoạch động trên tập con, khai thác tính chất cấu trúc con tối ưu (Optimal Substructure): Một đoạn hành trình con tối ưu từ đỉnh $0$ qua một tập đỉnh $S$ kết thúc tại $u$ phải chứa đường đi tối ưu đến đỉnh áp chót $v \in S \setminus \{u\}$ .

Thiết lập Trạng thái DP (Bitmask DP)

Biểu diễn tập đỉnh đã đi qua bằng một mặt nạ bit (Bitmask) $S \subseteq \{0, 1, \dots, N-1\}$ :

Nếu bit thứ $i$ của $S$ bật ( $S \ \& \ (1 \ll i) \neq 0$ ), đỉnh $i$ đã được ghé thăm.

Định nghĩa hàm trạng thái:

$dp(S, u)$

là chi phí nhỏ nhất của đường đi xuất phát từ đỉnh $0$ , đi qua chính xác tất cả các đỉnh thuộc tập $S$ (mỗi đỉnh đúng một lần), và kết thúc tại đỉnh $u$ ( $0 \in S, u \in S$ ).

Hệ thức truy hồi (State Transition)

Để đến được trạng thái $(S, u)$ , đỉnh liền trước $u$ phải là một đỉnh $v \in S \setminus \{u\}$ . Do đó:

$dp(S, u) = \min_{v \in S \setminus \{u\}} \left( dp(S \setminus \{u\}, v) + w_{v, u} \right)$

Điều kiện cơ sở và Đáp án tối ưu

Cơ sở: Xuất phát tại đỉnh $0$ , tập đỉnh chỉ gồm $\{0\}$ :

$dp(\{0\}, 0) = dp(1, 0) = 0$
Mọi trạng thái khác khởi tạo bằng $\infty$ .
Đáp án toàn cục: Sau khi đã đi qua toàn bộ $N$ đỉnh (tương ứng mask đầy đủ $2^N - 1$ ), ta cộng thêm chi phí quay trở về đỉnh $0$ :

$\text{OPT} = \min_{u \neq 0} \left( dp((1 \ll N) - 1, u) + w_{u, 0} \right)$

   Tập đã thăm: S \ {u}                     Thêm đỉnh u vào hành trình:
      (0) ---> (a) ---> (v)        +      (v) ---> (u)
       \_________________/
          dp(S \ {u}, v)                     w(v, u)
                            ==> dp(S, u)

3. Phân nhánh và Chặn (Branch and Bound - B&B) với Chặn dưới MST

Dù thuật toán Held-Karp giảm chi phí từ $O(N!)$ xuống $O(N^2 2^N)$ , rào cản lớn nhất của nó là bộ nhớ $O(N \cdot 2^N)$ . Với $N \ge 25$ , bộ nhớ RAM cần thiết vượt quá hàng trăm Gigabyte.

Phương pháp Phân nhánh và Chặn (Branch and Bound) giải quyết giới hạn này:

Không gian bộ nhớ chỉ là $O(N)$ (tương ứng độ sâu ngăn xếp DFS).
Tại mỗi nút của cây tìm kiếm (tương ứng một hành trình cục bộ $P = (v_0, v_1, \dots, v_k)$ ), thuật toán tính toán một chặn dưới (Lower Bound - LB) cho chi phí của toàn bộ hành trình hoàn chỉnh xuất phát từ $P$ .
Nếu $\text{LB} \ge \text{BestCost}$ hiện tại, toàn bộ nhánh con lập tức bị cắt tỉa (pruned).

Kỹ thuật tính Chặn dưới bằng Cây khung nhỏ nhất (1-Tree / MST Relaxation)

Giả sử hành trình hiện tại đã đi qua đoạn $P = (v_0 \to v_1 \to \dots \to v_k)$ , và tập các đỉnh chưa thăm là $U = V \setminus P$ .

Bất kỳ chu trình TSP hợp lệ nào mở rộng từ $P$ cũng bắt buộc phải:

Trả chi phí của đoạn đường đã đi: $\text{cost}(P) = \sum_{i=0}^{k-1} w_{v_i, v_{i+1}}$ .
Rời khỏi đỉnh $v_k$ để đi vào tập $U$ : Tốn ít nhất $\min_{u \in U} w_{v_k, u}$ .
Kết nối toàn bộ các đỉnh trong $U$ : Tốn ít nhất chi phí của Cây khung nhỏ nhất $\text{MST}(U)$ .
Rời khỏi tập $U$ để quay về đỉnh gốc $v_0$ : Tốn ít nhất $\min_{u \in U} w_{u, v_0}$ .

$\text{LB} = \text{cost}(P) + \min_{u \in U} w_{v_k, u} + \text{Weight}(\text{MST}(U)) + \min_{u \in U} w_{u, v_0}$

Vì $\text{LB}$ luôn $\le$ chi phí thực tế của bất kỳ chu trình nào đi qua nhánh này, việc cắt tỉa đảm bảo không bao giờ bỏ sót nghiệm tối ưu toàn cục.

4. Hiện thực hóa Thuật toán Held-Karp bằng Golang

Chương trình dưới đây cài đặt hoàn chỉnh thuật toán Held-Karp:

Tính toán chi phí TSP nhỏ nhất bằng Bitmask DP.
Cơ chế Lần vết mảng cha (parent) để khôi phục chính xác chuỗi thứ tự các đỉnh trong hành trình tối ưu.

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

type TSPResult struct {
	MinCost int64
	Tour    []int
}

// SolveTSP sử dụng Quy hoạch động Held-Karp: O(N^2 * 2^N)
func SolveTSP(n int, dist [][]int64) TSPResult {
	if n <= 1 {
		return TSPResult{MinCost: 0, Tour: []int{0, 0}}
	}

	numStates := 1 << n
	// dp[mask][u]: chi phí nhỏ nhất thăm tập đỉnh 'mask' kết thúc tại 'u'
	dp := make([][]int64, numStates)
	// parent[mask][u]: lưu đỉnh áp chót 'v' để phục vụ truy vết hành trình
	parent := make([][]int, numStates)

	for i := 0; i < numStates; i++ {
		dp[i] = make([]int64, n)
		parent[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dp[i][j] = INF
			parent[i][j] = -1
		}
	}

	// 1. Điều kiện cơ sở: Bắt đầu tại đỉnh 0
	dp[1][0] = 0 // Mask 1 tương ứng bit 0 được bật ({0})

	// 2. Tính toán quy hoạch động theo kích thước mask tăng dần
	for mask := 1; mask < numStates; mask++ {
		// Chỉ xét các mask chứa đỉnh gốc 0
		if (mask & 1) == 0 {
			continue
		}

		for u := 0; u < n; u++ {
			// Đỉnh u phải thuộc tập mask hiện tại
			if (mask & (1 << u)) == 0 || dp[mask][u] == INF {
				continue
			}

			// Thử mở rộng sang đỉnh kế tiếp v chưa thuộc mask
			for v := 0; v < n; v++ {
				if (mask & (1 << v)) == 0 {
					nextMask := mask | (1 << v)
					newCost := dp[mask][u] + dist[u][v]
					if newCost < dp[nextMask][v] {
						dp[nextMask][v] = newCost
						parent[nextMask][v] = u
					}
				}
			}
		}
	}

	// 3. Khép kín chu trình: Quay từ đỉnh kết thúc u về đỉnh 0
	fullMask := numStates - 1
	var minTotalCost int64 = INF
	lastNode := -1

	for u := 1; u < n; u++ {
		if dp[fullMask][u] < INF {
			cycleCost := dp[fullMask][u] + dist[u][0]
			if cycleCost < minTotalCost {
				minTotalCost = cycleCost
				lastNode = u
			}
		}
	}

	if lastNode == -1 {
		return TSPResult{MinCost: -1, Tour: nil} // Không tồn tại chu trình Hamilton
	}

	// 4. Lần vết tìm lại chuỗi hành trình
	tour := make([]int, 0, n+1)
	currMask := fullMask
	currNode := lastNode

	for currNode != -1 {
		tour = append(tour, currNode)
		prevNode := parent[currMask][currNode]
		currMask ^= (1 << currNode)
		currNode = prevNode
	}

	// Đảo ngược hành trình để có thứ tự từ đỉnh 0 đi tiếp
	for i, j := 0, len(tour)-1; i < j; i, j = i+1, j-1 {
		tour[i], tour[j] = tour[j], tour[i]
	}
	// Thêm đỉnh 0 vào cuối để khép kín vòng chu trình
	tour = append(tour, 0)

	return TSPResult{
		MinCost: minTotalCost,
		Tour:    tour,
	}
}

func main() {
	// Ma trận khoảng cách giữa 5 thành phố (0 đến 4)
	n := 5
	dist := [][]int64{
		{0, 10, 8, 9, 7},
		{10, 0, 10, 5, 6},
		{8, 10, 0, 8, 9},
		{9, 5, 8, 0, 6},
		{7, 6, 9, 6, 0},
	}

	res := SolveTSP(n, dist)

	fmt.Printf("=== KẾT QUẢ BÀI TOÁN TSP BẰNG HELD-KARP (N = %d) ===\n", n)
	fmt.Printf("Chi phí hành trình tối ưu: %d\n", res.MinCost)
	fmt.Printf("Hành trình tối ưu chi tiết: ")
	for i, node := range res.Tour {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Printf("Thành phố %d", node)
	}
	fmt.Println()

	// Liệt kê chi phí từng chặng
	fmt.Println("\nChi tiết khoảng cách từng chặng:")
	for i := 0; i < len(res.Tour)-1; i++ {
		u := res.Tour[i]
		v := res.Tour[i+1]
		fmt.Printf("- Chặng %d -> %d: %d\n", u, v, dist[u][v])
	}
}

5. Phân tích Độ phức tạp và So sánh các Chiến lược giải TSP

Phương pháp giải	Tính chất nghiệm	Độ phức tạp thời gian	Chi phí bộ nhớ	Ngưỡng giải quyết ( $N$ )
Duyệt hoán vị (Brute Force)	Chính xác 100%	$O(N!)$	$O(N)$	$N \le 11$
Held-Karp DP	Chính xác 100%	$O(N^2 \cdot 2^N)$	$O(N \cdot 2^N)$	$N \le 23$
Branch and Bound (MST bound)	Chính xác 100%	Thực nghiệm nhanh hơn DP	$O(N)$	$N \approx 40 - 100$
Concorde TSP Solver (Branch & Cut)	Chính xác 100%	Phụ thuộc tập dữ liệu	Biến thiên	$N \approx 10^3 - 10^4$
Christofides-Serdyukov	Xấp xỉ $\le 1.5 \times \text{OPT}$	$O(N^3)$ (Đa thức)	$O(N^2)$	$N \approx 10^5$
Lin-Kernighan-Helsgaun (LKH)	Heuristic gần tối ưu	Thực nghiệm $O(N^{2.2})$	$O(N)$	$N \approx 10^6$

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

Khoan mạch in điện tử (PCB Hole Drilling): Máy CNC cần khoan hàng chục nghìn lỗ trên một bo mạch chủ máy tính. Mỗi lần đầu khoan di chuyển giữa hai tọa độ lỗ tiêu tốn thời gian và làm mài mòn trục cơ khí. TSP tối ưu hóa lộ trình di chuyển của đầu kim khoan, tiết kiệm hàng trăm giờ sản xuất công nghiệp.
Quy hoạch chặng bay và Giao hàng chặng cuối (Last-Mile Routing): Tìm chuỗi lộ trình giao hàng tối ưu cho xe chở bưu kiện xuất phát từ kho trung tâm, giao hết các kiện hàng cho khách và quay trở lại kho trước khi hết ca làm việc.
Tái tạo trình tự DNA (Genomics Sequence Re-assembly): Khi giải trình tự chuỗi gen bằng phương pháp bắn phá phân đoạn (Shotgun Sequencing), các đoạn đọc ngắn (reads) có các vùng chồng lấn (overlaps). Việc ghép các đoạn này thành chuỗi DNA hoàn chỉnh tương đương bài toán tìm đường đi Hamilton ngắn nhất trên đồ thị chồng lấn.

cấu trúc dữ liệu