Cấu trúc dữ liệu và Giải thuật Bài 112: Ghép cặp cực đại (Maximum Bipartite Matching & Hopcroft-Karp) - Giải quyết bài toán phân bổ nguồn lực hai phía.

Sau khi đã làm chủ bài toán Mạng luồng tổng quát (Max Flow) ở Bài 111, chúng ta tiến đến một dạng bài toán chuyên biệt nhưng xuất hiện dày đặc trong các hệ thống phần mềm thương mại thực tế: Bài toán Ghép cặp cực đại trên đồ thị hai phía (Maximum Bipartite Matching - MBM).

Trong kiến trúc hệ thống, bất cứ khi nào bạn cần giải quyết bài toán phân bổ nguồn lực hai phía (Two-sided Resource Allocation), bạn đang đối mặt với MBM:

• Hệ thống gọi xe & Giao vận (Ride-sharing / Delivery): Ghép nối các tài xế trống với các cuốc xe/đơn hàng mới sao cho số lượng đơn hàng được xử lý đồng thời là lớn nhất.

• Sàn thương mại điện tử & Việc làm (Job Portals): Ghép nối ứng viên phù hợp với các vị trí tuyển dụng dựa trên kỹ năng.

• Hạ tầng Cloud & Lên lịch tác vụ (Task Scheduling): Phân bổ các tác vụ tính toán cho các cụm máy chủ (Server nodes) có năng lực tương thích.

1. Định nghĩa Đồ thị hai phía (Bipartite Graph)

Một đồ thị $G = (V, E)$ được gọi là Đồ thị hai phía nếu tập hợp các đỉnh $V$ có thể chia thành hai tập con rời rạc $U$ và $V$ sao cho mọi cạnh trong $E$ đều nối một đỉnh thuộc $U$ với một đỉnh thuộc $V$ (không có cạnh nào nối hai đỉnh trong cùng một tập $U$ hoặc cùng một tập $V$).

• Matching (Ghép cặp): Là một tập hợp các cạnh không có đỉnh nào chung (mỗi nhân sự chỉ nhận 1 việc, mỗi việc chỉ giao cho 1 nhân sự).

• Maximum Bipartite Matching (Ghép cặp cực đại): Tìm một tập ghép cặp sao cho số lượng cạnh được chọn là lớn nhất có thể.

2. Từ Mạng luồng đến Thuật toán Hopcroft-Karp

Mọi bài toán Ghép cặp cực đại trên đồ thị hai phía thực chất đều có thể quy về Bài toán Luồng cực đại (Max Flow) bằng cách:

1. Thêm một đỉnh nguồn chung $S$ nối đến tất cả các đỉnh thuộc tập $U$ (dung lượng = 1).

2. Thêm một đỉnh đích chung $T$ nhận các đường đi từ tất cả các đỉnh thuộc tập $V$ (dung lượng = 1).

3. Chạy thuật toán Max Flow (như Edmonds-Karp). Tổng lưu lượng cực đại chính là số lượng cặp ghép lớn nhất.

Tuy nhiên, việc dùng Max Flow tổng quát đôi khi dư thừa. Các nhà khoa học Hopcroft và Karp đã phát minh ra Thuật toán Hopcroft-Karp tối ưu hóa chuyên biệt cho đồ thị hai phía bằng cách tìm đồng thời nhiều đường tăng luồng ngắn nhất trong mỗi bước BFS kết hợp DFS, đẩy độ phức tạp thời gian xuống mức cực kỳ ấn tượng: $O(E \sqrt{V})$, vượt trội hoàn toàn so với các cách tiếp cận thông thường.

3. Hiện thực hóa Maximum Bipartite Matching bằng Golang

Đoạn code dưới đây cài đặt thuật toán ghép cặp cực đại hiệu quả sử dụng phương pháp đường tăng luồng qua DFS (Kuhn's Algorithm / Augmenting Path), dạng cơ sở cực kỳ phổ biến và dễ bảo trì trong các hệ thống backend:

Go

package main

import (
	"fmt"
)

type BipartiteMatcher struct {
	nU, nV int      // Số lượng phần tử tập U và tập V
	adj    [][]int  // Danh sách kề từ U sang V
	matchV []int    // Lưu vết: Đỉnh v thuộc V đang ghép với đỉnh nào bên U (-1 nếu chưa ghép)
	vis    []bool   // Mảng đánh dấu đã thăm trong lượt tìm kiếm đường tăng
}

func NewBipartiteMatcher(nU, nV int) *BipartiteMatcher {
	return &BipartiteMatcher{
		nU:     nU,
		nV:     nV,
		adj:    make([][]int, nU),
		matchV: make([]int, nV),
		vis:    make([]bool, nU),
	}
}

func (bm *BipartiteMatcher) AddEdge(u, v int) {
	bm.adj[u] = append(bm.adj[u], v)
}

// Hàm DFS tìm đường tăng luồng (Augmenting Path)
func (bm *BipartiteMatcher) dfs(u int) bool {
	for _, v := range bm.adj[u] {
		if !bm.vis[v] { // Chú ý: vis ở đây có thể quản lý theo phía V hoặc U tùy cài đặt
			// Đơn giản hóa: quản lý mảng visited cho tập V trong lượt chạy
			// (Trong code chuẩn, ta dùng mảng visited riêng cho U hoặc V)
		}
	}
	return false
}

// Cài đặt chuẩn Kuhn's Algorithm (DFS-based Augmenting Paths)
func (bm *BipartiteMatcher) MaxMatch() int {
	// Khởi tạo mảng matchV ban đầu chưa ghép ai (-1)
	for i := range bm.matchV {
		bm.matchV[i] = -1
	}

	maxMatching := 0

	// Thử tìm cặp ghép cho từng đỉnh u thuộc tập U
	for u := 0; u < bm.nU; u++ {
		visited := make([]bool, bm.nV)
		if bm.findMatch(u, visited) {
			maxMatching++
		}
	}

	return maxMatching
}

func (bm *BipartiteMatcher) findMatch(u int, visited []bool) bool {
	for _, v := range bm.adj[u] {
		if !visited[v] {
			visited[v] = true
			// Nếu đỉnh v chưa được ghép với ai, hoặc đỉnh đang ghép với v có thể tìm được cặp thay thế khác
			if bm.matchV[v] < 0 || bm.findMatch(bm.matchV[v], visited) {
				bm.matchV[v] = u
				return true
			}
		}
	}
	return false
}

func main() {
	// Giả lập hệ thống ghép cặp 4 Nhân sự (Tập U: 0, 1, 2, 3) với 4 Công việc (Tập V: 0, 1, 2, 3)
	nU, nV := 4, 4
	matcher := NewBipartiteMatcher(nU, nV)

	// Thiết lập khả năng đáp ứng công việc của từng nhân sự
	matcher.AddEdge(0, 0) // Nhân sự 0 làm được việc 0
	matcher.AddEdge(0, 1) // Nhân sự 0 làm được việc 1
	matcher.AddEdge(1, 0) // Nhân sự 1 làm được việc 0
	matcher.AddEdge(2, 1) // Nhân sự 2 làm được việc 1
	matcher.AddEdge(2, 2) // Nhân sự 2 làm được việc 2
	matcher.AddEdge(3, 2) // Nhân sự 3 làm được việc 2
	matcher.AddEdge(3, 3) // Nhân sự 3 làm được việc 3

	totalMatches := matcher.MaxMatch()
	fmt.Printf("Số lượng phân bổ nguồn lực ghép cặp tối đa: %d\n", totalMatches)

	fmt.Println("Chi tiết phân bổ (Công việc -> Nhân sự thực hiện):")
	for v, u := range matcher.matchV {
		if u != -1 {
			fmt.Printf("Công việc %d được giao cho Nhân sự %d\n", v, u)
		}
	}
}

4. Ứng dụng thực tế trong Kỹ thuật phần mềm

• Hệ thống phân phối đơn hàng tự động (Order Dispatching): Các nền tảng gọi xe công nghệ hoặc giao đồ họa dùng thuật toán ghép cặp liên tục mỗi vài giây để tối ưu hóa tổng quãng đường di chuyển và số lượng đơn hoàn thành.

• Phân quyền truy cập động & Ghép cặp tài nguyên phần cứng: Quản lý việc cấp phát các tác vụ tính toán nặng cho các worker node trong hệ thống phân tán sao cho tải trọng được cân bằng hoàn hảo.

Ghép cặp cực đại khép lại mảng kiến thức nền tảng về tối ưu hóa đồ thị nâng cao, chuẩn bị bước sang các chuyên đề chuyên sâu tiếp theo của lộ trình.