Cấu trúc dữ liệu và Giải thuật Bài 88: Đối sánh đồ thị hai phía (Bipartite Matching) - Ứng dụng Max Flow vào phân công công việc tối ưu.

Giả sử khi vận hành hệ thống thu phí tự động (AFC) cho tuyến Metro Line 1, bạn có một danh sách các Kỹ sư bảo trì (Tập $U$) và một danh sách các Cổng soát vé đang bị lỗi (Tập $V$). Mỗi kỹ sư chỉ sở hữu chứng chỉ và chuyên môn để sửa chữa một vài model cổng nhất định. Tương tự, tại Hasaki, bạn cần phân công các Shipper đi giao hàng tại các khu vực mà họ thông thạo đường đi.

Bài toán đặt ra: Làm sao để phân công sao cho số lượng công việc (cổng AFC / đơn hàng) được giải quyết là nhiều nhất, với điều kiện khắt khe là mỗi nhân sự chỉ nhận 1 việc và mỗi việc chỉ do 1 người phụ trách?

Đây là bài toán kinh điển mang tên Đối sánh đồ thị hai phía (Bipartite Matching). Đồ thị hai phía là một mạng lưới nơi các đỉnh được chia làm 2 tập hợp biệt lập ($U$ và $V$), và các đường nối (Edges) chỉ được phép bắc cầu từ tập này sang tập kia, không bao giờ có đường nối nội bộ trong cùng một tập.

1. Phép thuật Biến đổi: Đưa Bipartite Matching về Max Flow

Cách tiếp cận ngây thơ là dùng thuật toán Tham lam (Greedy): Kỹ sư nào rảnh thì vơ đại một công việc có thể làm. Tuy nhiên, Greedy sẽ nhanh chóng rơi vào ngõ cụt nếu một kỹ sư đa năng "giành" mất công việc của một kỹ sư chỉ biết làm duy nhất một việc đó, dẫn đến hiệu suất tổng thể bị giảm sút.

Để tìm ra cách ghép cặp hoàn hảo và cực đại nhất, chúng ta áp dụng lại thuật toán Luồng cực đại (Max Flow) từ Bài 87 bằng một mẹo "bẻ cong không gian" cực kỳ thông minh:

1. Thêm Nút siêu nguồn (Super Source - $S$): Nối $S$ đến tất cả các Kỹ sư trong tập $U$. Đặt sức chứa (Capacity) của mỗi đường nối này là $1$. (Ý nghĩa: Mỗi kỹ sư chỉ được cung cấp tối đa 1 đơn vị sức lao động).

2. Định hướng công việc: Nối các đường chuyên môn từ Kỹ sư sang Công việc tương ứng. Sức chứa cũng là $1$.

3. Thêm Nút siêu đích (Super Sink - $T$): Nối tất cả các Công việc trong tập $V$ về $T$ với sức chứa là $1$. (Ý nghĩa: Mỗi công việc chỉ cần 1 người làm là xong).

Lúc này, toàn bộ bài toán phân công công việc đã biến thành một Mạng lưới ống dẫn nước. Nếu bạn chạy thuật toán Ford-Fulkerson để bơm luồng từ $S$ đến $T$, giá trị Max Flow thu được chính là số lượng cặp lớn nhất có thể ghép, và những con đường nào có luồng nước chảy qua chính là sơ đồ phân công tối ưu!

2. Triển khai DFS Tối ưu (Thuật toán Kuhn) bằng Golang

Nếu chúng ta xây dựng nguyên một ma trận Edmonds-Karp đầy đủ cho bài toán có Capacity = 1 thì sẽ hơi lãng phí bộ nhớ. Dựa trên bản chất của đường tăng luồng (Augmenting Path), Kuhn's Algorithm sử dụng DFS để thực hiện đúng logic của Max Flow một cách ngắn gọn và thanh lịch hơn rất nhiều.

Hàm đệ quy bpm() dưới đây mô phỏng khả năng "thương lượng": Nếu công việc $V$ đã bị Kỹ sư khác chiếm, thuật toán sẽ đi hỏi Kỹ sư kia xem anh ta có thể chuyển sang làm công việc khác được không (chính là cơ chế Đi ngược đồ thị thặng dư của Ford-Fulkerson).

Go

package main

import "fmt"

// u: Kỹ sư hiện tại đang xét
// match: Mảng lưu trữ trạng thái phân công (match[v] = u nghĩa là việc v do kỹ sư u làm)
// visited: Đánh dấu các công việc đã thử thương lượng trong vòng lặp hiện tại
// graph: Ma trận kề, graph[u][v] == 1 nghĩa là kỹ sư u có thể làm việc v
func bpm(u int, match []int, visited []bool, graph [][]int) bool {
	jobsCount := len(graph[0])

	for v := 0; v < jobsCount; v++ {
		// Nếu kỹ sư u có thể làm việc v và việc v chưa được hỏi tới trong lượt này
		if graph[u][v] == 1 && !visited[v] {
			visited[v] = true

			// Nếu việc v chưa ai nhận (match[v] < 0)
			// HOẶC người đang giữ việc v (match[v]) có thể chuyển sang làm việc khác
			if match[v] < 0 || bpm(match[v], match, visited, graph) {
				match[v] = u // Phân công việc v cho kỹ sư u
				return true  // Tìm được đường tăng luồng thành công
			}
		}
	}
	return false
}

func MaxBipartiteMatching(graph [][]int) int {
	engineersCount := len(graph)
	jobsCount := len(graph[0])

	// match[i] lưu ID của kỹ sư được phân công cho công việc i. Ban đầu là -1 (chưa phân công).
	match := make([]int, jobs(Count)
	for i := 0; i < jobsCount; i++ {
		match[i] = -1
	}

	maxMatch := 0
	// Thử tìm công việc cho từng kỹ sư
	for u := 0; u < engineersCount; u++ {
		visited := make([]bool, jobsCount)
		if bpm(u, match, visited, graph) {
			maxMatch++
		}
	}

	// In ra danh sách phân công chi tiết
	fmt.Println("Sơ đồ phân công tối ưu:")
	for v := 0; v < jobsCount; v++ {
		if match[v] != -1 {
			fmt.Printf("- Cổng AFC số %d do Kỹ sư số %d phụ trách\n", v, match[v])
		}
	}

	return maxMatch
}

func main() {
	// Giả lập: 4 Kỹ sư và 4 Cổng AFC cần sửa
	// Hàng i, Cột j = 1 nghĩa là Kỹ sư i sửa được Cổng j
	graph := [][]int{
		{0, 1, 1, 0}, // Kỹ sư 0 làm được việc 1, 2
		{1, 0, 0, 0}, // Kỹ sư 1 làm được việc 0
		{0, 0, 1, 0}, // Kỹ sư 2 làm được việc 2
		{0, 0, 1, 1}, // Kỹ sư 3 làm được việc 2, 3
	}

	fmt.Printf("Tổng số lượng công việc được xử lý cùng lúc: %d\n", MaxBipartiteMatching(graph))
	/* 
	Kỳ vọng kết quả:
	Kỹ sư 1 sẽ bị "đẩy" sang làm việc khác nếu xảy ra xung đột,
	nhờ cơ chế đệ quy đàm phán luồng ngược.
	*/
}

3. Phân tích Hiệu năng (Big-O)

• Thời gian thực thi (Time Complexity): $O(V \cdot E)$. Vòng lặp chính chạy qua $V$ đỉnh thuộc tập $U$. Mỗi đỉnh gọi hàm DFS duyệt qua tối đa $E$ cạnh. Vì mọi đồ thị hai phía đều phân lớp rất mỏng, thuật toán phản hồi gần như tức thời trên các tập dữ liệu thực tế.

• Không gian (Space Complexity): $O(V)$ cho các mảng match, visited và call stack của đệ quy, hoàn toàn tối ưu cho mọi hệ thống hạn chế RAM.

• (Lưu ý chuyên sâu: Nếu sử dụng thuật toán Hopcroft-Karp bằng cách kết hợp cả BFS để tìm nhiều đường cùng lúc và DFS để chốt luồng, độ phức tạp sẽ giảm xuống mức thần tốc $O(E \sqrt{V})$, chuyên trị các mạng lưới khổng lồ hàng triệu node).

4. Ứng dụng Thực tế tại Enterprise

Bipartite Matching là trái tim của các thuật toán ghép cặp tự động trên toàn cầu:

• Logistics & Giao nhận (Uber, Grab, Hasaki): Hệ thống liên tục nhận tín hiệu tài xế rảnh (Tập U) và đơn hàng mới (Tập V). Dựa trên bán kính khoảng cách để vẽ các cạnh nối, Max Flow sẽ chạy mỗi giây để đảm bảo lượng đơn hàng được "khớp lệnh" là tối đa.

• Hẹn hò trực tuyến (Tinder, Bumble): Khớp các hồ sơ nam/nữ dựa trên bộ lọc tương thích (Swipe Right) sao cho số lượng Match tổng thể trên toàn hệ thống đạt đỉnh cực đại.

• Mạng Y tế (Hiến tạng chéo - Kidney Exchange): Cứu sống bệnh nhân bằng cách sử dụng các đồ thị tương thích sinh học để tạo ra các vòng tròn hoặc các cặp trao đổi nội tạng cực đại giữa những gia đình người hiến tặng không cùng huyết thống.

Chúng ta đã chinh phục hoàn toàn bài toán phân công. Trong kỹ thuật đồ thị chuyên sâu, đôi khi một mạng lưới máy chủ khổng lồ có thể bị chia cắt thành nhiều cụm (Cluster), nơi các máy chủ trong cụm giao tiếp chéo được với nhau nhưng lại bị nghẽn một chiều với bên ngoài. Để gom nhóm và tối ưu hóa hạ tầng này, chúng ta cần công cụ mạnh nhất để phân tích cấu trúc liên thông của hệ thống.