Thuật toán Hungary (bài toán phân công)
Thuật toán Hungary dạng thế năng giải bài toán phân công (cặp ghép hoàn hảo trọng số nhỏ nhất trên đồ thị hai phía đầy đủ) trong O(n^3). Kèm ví dụ chạy tay, chứng minh tối ưu qua chi phí rút gọn và cài đặt C++/Python.
Thuật toán Hungary (Hungarian algorithm, còn gọi là Kuhn-Munkres) giải bài toán phân công (assignment problem): cho ma trận chi phí kích thước (), chọn cho mỗi hàng (công nhân) một cột (công việc) khác nhau sao cho tổng chi phí nhỏ nhất. Nói theo ngôn ngữ đồ thị, đây là cặp ghép hoàn hảo trọng số nhỏ nhất trên đồ thị hai phía đầy đủ.
Vét cạn phải thử hoán vị, quy hoạch động bitmask tốn nên chỉ chạy được tới . Thuật toán Hungary chạy trong , tức với ma trận vuông, đủ nhanh cho cỡ trở lên. Đây là công cụ chuẩn mỗi khi bài quy về "ghép mỗi phần tử bên trái với đúng một phần tử bên phải, tối thiểu tổng chi phí", và ma trận chi phí dày (gần như mọi cặp đều được phép).
Ý tưởng / Trực giác
Tham lam không được. Cho mỗi công nhân lần lượt lấy việc rẻ nhất còn trống có thể sai rất nặng: với hai công nhân, chi phí của công nhân 1 cho hai việc là và của công nhân 2 là : công nhân 1 lấy việc 1 (chi phí 1) khiến công nhân 2 phải nhận việc 2 với chi phí 100, trong khi phương án đúng chỉ tốn . Cần một cách "đổi ý" có kiểm soát.
Thế năng (potential). Ta duy trì hai mảng số (cho hàng) và (cho cột) sao cho với mọi cặp
gọi là chi phí rút gọn. Bổ đề then chốt:
Nếu có một phép phân công hoàn chỉnh chỉ dùng các ô có thì phép phân công đó tối ưu.
Chứng minh: với một phép phân công bất kỳ, . Với ma trận vuông, mỗi cột xuất hiện đúng một lần nên hai tổng thế năng là hằng số chung cho mọi . Vì , tổng chi phí luôn , và phép phân công toàn ô đạt đúng giá trị này. (Với , thuật toán bên dưới chỉ làm giảm của những cột đã từng được thăm, các cột chưa thăm có , nên lập luận vẫn đúng.)
Đây chính là đối ngẫu quy hoạch tuyến tính: là cận dưới, và thuật toán đẩy cận dưới này lên cho tới khi chạm đáp án.
Thêm từng hàng một. Thuật toán có pha. Pha thêm hàng vào cặp ghép đã có của các hàng (cặp ghép này luôn chỉ dùng ô ). Từ hàng mới, ta tìm đường tăng (augmenting path): hàng mới lấy một cột, nếu cột đó đã có chủ thì chủ cũ phải chuyển sang cột khác, cứ thế cho tới khi chạm một cột trống. Ta chỉ được đi trên các ô . Khi không còn ô nào để mở rộng, ta dịch thế năng:
- Gọi là chi phí rút gọn nhỏ nhất từ một hàng đã thăm tới một cột chưa thăm.
- Tăng của mọi hàng đã thăm thêm , giảm của mọi cột đã thăm đi .
Ô giữa hàng đã thăm và cột đã thăm không đổi (), nên các ô trong cây tìm kiếm và trong cặp ghép vẫn là . Ô từ hàng đã thăm tới cột chưa thăm giảm đúng , nên vẫn và có ít nhất một ô mới trở thành : cây được mở rộng thêm một cột. Mỗi pha thăm tối đa cột, rồi lật đường tăng. Thực chất đây là Dijkstra tìm đường tăng ngắn nhất trên chi phí rút gọn, đúng tinh thần của Min Cost Flow nhưng tận dụng cấu trúc ma trận đầy đủ.
Mẹo cài đặt (dạng e-maxx). Thêm một cột ảo 0: đặt hàng mới làm "chủ" của cột 0 (), như vậy hàng mới cũng chỉ là chủ của một cột đã thăm và mọi bước đều đồng nhất. Mảng lưu chi phí rút gọn nhỏ nhất từ cây tới cột , lưu cột đứng trước trên đường tăng. Cuối cùng chính là tổng chi phí tối ưu.
Ví dụ chạy tay
Ma trận chi phí (hàng là công nhân, cột là công việc):
việc 1 việc 2 việc 3
người 1: 8 4 7
người 2: 5 2 3
người 3: 9 4 8
Tham lam theo hàng: người 1 lấy việc 2 (4), người 2 lấy việc 3 (3), người 3 phải lấy việc 1 (9), tổng . Đáp án đúng là .
Ban đầu . Ta theo dõi từng pha (các bước dưới đây được in ra từ chính đoạn code ở mục Cài đặt):
| Pha | Bước | Đang ở hàng | Cột chọn | Cột đó của ai | |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 4 | 2 | trống: dừng |
| 2 | 1 | 2 | 2 | 2 | người 1 |
| 2 | 2 | 1 | 1 | 3 | trống: dừng |
| 3 | 1 | 3 | 5 | 2 | người 1 |
| 3 | 2 | 1 | 2 | 3 | người 2 |
| 3 | 3 | 2 | 1 | 1 | trống: dừng |
- Pha 1: người 1 vào, ô rẻ nhất là việc 2 (chi phí 4), , . Việc 2 trống nên ghép ngay người 1 với việc 2.
- Pha 2: người 2 vào. Ô rẻ nhất là việc 2 () nhưng việc 2 đã thuộc người 1, nên người 1 được đưa vào cây. Sau khi dịch thế năng, chi phí rút gọn nhỏ nhất tới một cột chưa thăm là và đạt tại việc 3, mà giá trị này đến từ chính người 2 (; người 1 tới việc 3 cũng chỉ bằng , không nhỏ hơn). Việc 3 trống: người 2 nhận việc 3, người 1 giữ nguyên việc 2. Sau pha: , , .
- Pha 3: người 3 vào. Ô rẻ nhất là việc 2 (), thuộc người 1. Từ người 1, rẻ nhất là việc 3 (), thuộc người 2. Từ người 2, rẻ nhất là việc 1 (), trống: dừng. Lần ngược theo : việc 1 được đi tới từ việc 2 (tức qua người 1), việc 2 được đi tới từ cột ảo (người 3). Vậy đường tăng là người 3 lấy việc 2, người 1 chuyển sang việc 1; người 2 giữ việc 3 (người 2 chỉ là một nhánh được thăm, không nằm trên đường tăng).
Trạng thái cuối cùng sau pha 3:
Ma trận chi phí rút gọn :
việc 1 việc 2 việc 3
người 1: [0] 0 0
người 2: 1 2 [0]
người 3: 1 [0] 1
Mọi ô đều và cặp ghép (ô trong ngoặc) gồm người 1 làm việc 1, người 2 làm việc 3, người 3 làm việc 2, toàn ô . Tổng chi phí thật , bằng đúng : cận dưới đã chạm đáp án, nên là tối ưu (vét cạn hoán vị cũng cho ).
Cài đặt
Hàm nhận ma trận chi phí với (chỉ số từ 0), trả về chi phí nhỏ nhất và cột được giao cho từng hàng. Chi phí có thể âm.
#include <bits/stdc++.h>
using namespace std;
// Thuật toán Hungary dạng thế năng, O(n^2 m), yêu cầu n <= m.
// a[i][j] (chỉ số từ 0): chi phí giao hàng i cho cột j.
// Trả về {chi phí nhỏ nhất, ans} với ans[i] = cột được giao cho hàng i.
pair<long long, vector<int>> hungarian(const vector<vector<long long>>& a) {
int n = a.size(), m = a[0].size();
const long long INF = LLONG_MAX / 4;
// u: thế năng hàng, v: thế năng cột; nội bộ dùng chỉ số từ 1, cột 0 là cột ảo
vector<long long> u(n + 1, 0), v(m + 1, 0), minv(m + 1);
vector<int> p(m + 1, 0), way(m + 1, 0); // p[j]: hàng đang ghép với cột j (0 = trống)
vector<char> used(m + 1);
for (int i = 1; i <= n; i++) {
p[0] = i; // đặt hàng mới vào cột ảo 0 rồi tìm đường tăng từ đó
int j0 = 0;
fill(minv.begin(), minv.end(), INF);
fill(used.begin(), used.end(), 0);
do {
used[j0] = 1;
int i0 = p[j0], j1 = 0;
long long delta = INF;
for (int j = 1; j <= m; j++) {
if (used[j]) continue;
long long cur = a[i0 - 1][j - 1] - u[i0] - v[j]; // chi phí rút gọn
if (cur < minv[j]) minv[j] = cur, way[j] = j0;
if (minv[j] < delta) delta = minv[j], j1 = j;
}
// dịch thế năng một lượng delta: cạnh trong cây giữ nguyên chi phí rút gọn 0
for (int j = 0; j <= m; j++) {
if (used[j]) u[p[j]] += delta, v[j] -= delta;
else minv[j] -= delta;
}
j0 = j1;
} while (p[j0] != 0); // dừng khi chạm cột còn trống
do { // lần ngược đường tăng, dịch từng cột sang hàng mới
int j1 = way[j0];
p[j0] = p[j1];
j0 = j1;
} while (j0 != 0);
}
vector<int> ans(n);
for (int j = 1; j <= m; j++)
if (p[j] != 0) ans[p[j] - 1] = j - 1;
return {-v[0], ans}; // -v[0] đúng bằng tổng chi phí tối ưu
}
int main() { // đọc n m rồi ma trận n x m, in chi phí và cột của từng hàng
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<long long>> a(n, vector<long long>(m));
for (auto& r : a)
for (auto& x : r) cin >> x;
auto [cost, ans] = hungarian(a);
cout << cost << "\n";
for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? ' ' : '\n');
}
def hungarian(a):
"""Thuật toán Hungary dạng thế năng, O(n^2 m), yêu cầu n <= m.
a[i][j] (chỉ số từ 0): chi phí giao hàng i cho cột j.
Trả về (chi phí nhỏ nhất, ans) với ans[i] = cột được giao cho hàng i."""
n, m = len(a), len(a[0])
INF = float("inf")
u = [0] * (n + 1) # thế năng hàng (chỉ số từ 1)
v = [0] * (m + 1) # thế năng cột, cột 0 là cột ảo
p = [0] * (m + 1) # p[j]: hàng đang ghép với cột j (0 = trống)
way = [0] * (m + 1)
for i in range(1, n + 1):
p[0] = i # đặt hàng mới vào cột ảo 0 rồi tìm đường tăng từ đó
j0 = 0
minv = [INF] * (m + 1)
used = [False] * (m + 1)
while True:
used[j0] = True
i0, j1, delta = p[j0], 0, INF
row, ui = a[i0 - 1], u[i0]
for j in range(1, m + 1):
if used[j]:
continue
cur = row[j - 1] - ui - v[j] # chi phí rút gọn
if cur < minv[j]:
minv[j] = cur
way[j] = j0
if minv[j] < delta:
delta = minv[j]
j1 = j
# dịch thế năng một lượng delta: cạnh trong cây giữ nguyên chi phí rút gọn 0
for j in range(m + 1):
if used[j]:
u[p[j]] += delta
v[j] -= delta
else:
minv[j] -= delta
j0 = j1
if p[j0] == 0: # dừng khi chạm cột còn trống
break
while j0: # lần ngược đường tăng, dịch từng cột sang hàng mới
j1 = way[j0]
p[j0] = p[j1]
j0 = j1
ans = [0] * n
for j in range(1, m + 1):
if p[j]:
ans[p[j] - 1] = j - 1
return -v[0], ans # -v[0] đúng bằng tổng chi phí tối ưu
if __name__ == "__main__":
import sys
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
vals = list(map(int, data[2 : 2 + n * m]))
a = [vals[i * m : (i + 1) * m] for i in range(n)]
cost, ans = hungarian(a)
print(cost)
print(*ans)
Một số cách dùng thường gặp:
- Tối đa tổng trọng số: đổi dấu toàn bộ ma trận (), chạy hàm, rồi đổi dấu kết quả.
- Cặp bị cấm: gán chi phí rất lớn (ví dụ , đủ lớn hơn mọi tổng hợp lệ nhưng không làm tràn
long longkhi cộng lần). Nếu kết quả giá trị đó thì không có phép phân công hợp lệ. - Số hàng nhiều hơn số cột: chuyển vị ma trận, hoặc thêm cột ảo chi phí để thành ma trận vuông.
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Vét cạn hoán vị | ||
| Quy hoạch động bitmask | ||
| Thuật toán Hungary |
Vì sao ? Có pha. Trong pha , mỗi vòng do thăm thêm đúng một cột; mọi cột được thăm trước cột trống cuối cùng đều đang có chủ, mà chỉ có cột có chủ, nên pha có không quá vòng. Mỗi vòng quét cột để cập nhật minv và dịch thế năng. Tổng cộng , với ma trận vuông là . Với là khoảng phép tính đơn giản, chạy dưới 1 giây bằng C++. Bản Python chậm hơn nhiều lần, thoải mái với .
⚠️ Lỗi thường gặp
- Dùng tham lam hoặc ghép cặp không trọng số: chọn việc rẻ nhất cho từng người, hay chạy Bipartite Matching rồi cộng chi phí, đều sai với ví dụ hai hàng và (cho 101 thay vì 3).
- INF quá nhỏ hoặc quá lớn:
INFdùng chominvvàdeltaphải lớn hơn mọi chi phí rút gọn có thể có. Chi phí rút gọn có thể vượt (thế năng âm dần), nên đừng dùng1e9khi tới . Ngược lại dùngLLONG_MAXrồi cộng trừ sẽ tràn số, vì thế code dùngLLONG_MAX / 4. - Quên điều kiện : nếu , vòng
dokhông bao giờ gặp cột trống,j1giữ giá trị và vòng lặp chạy sai hoặc vô hạn. Chuyển vị ma trận trước. - Lẫn chỉ số: bên trong dùng chỉ số từ 1 vì cột là cột ảo, còn ma trận vào dùng chỉ số từ 0. Quên trừ 1 khi đọc
a[i0 - 1][j - 1]cho kết quả lệch mà vẫn "trông hợp lý". - Không cập nhật
minvcủa cột chưa thăm khi dịch thế năng: bỏ dòngminv[j] -= deltathì các lần chọndeltasau dùng giá trị cũ, thế năng bị dịch sai và kết quả không còn tối ưu. Lỗi này qua được ví dụ nhỏ, nên luôn đối chiếu với vét cạn. - Đọc đáp án từ
u,vmà quên dấu: tổng chi phí là (hoặc tính lại cho chắc), không phải hay .
Biến thể / Mở rộng
- Luồng chi phí nhỏ nhất: bài phân công là trường hợp đặc biệt của Min Cost Flow (nguồn tới mỗi hàng, mỗi hàng tới mỗi cột, mỗi cột tới đích, sức chứa 1). Khi đồ thị thưa, có sức chứa khác 1 hoặc mỗi người nhận nhiều việc, dùng min cost flow. Khi ma trận dày và vuông, Hungary gọn và nhanh hơn.
- Ghép cặp không trọng số: chỉ cần số cặp tối đa thì dùng Bipartite Matching hoặc Hopcroft-Karp. Lưu ý nhiều tài liệu gọi thuật toán Kuhn (DFS tìm đường tăng) là "thuật toán Hungary"; đó là bản không trọng số.
- Nhiều đơn vị tại một đỉnh: nếu điểm cần ghép lần, nhân bản hàng thành hàng giống nhau. Đây đúng là cách bài icpc26mnh dựng ma trận.
- Chi phí từ khoảng cách: thường ma trận được tính trước bằng BFS hoặc Dijkstra từ mỗi điểm nguồn, rồi mới đưa vào Hungary.
- Phân công tối ưu theo cổ chai (tối thiểu chi phí lớn nhất thay vì tổng): không cần Hungary, chỉ cần tìm kiếm nhị phân ngưỡng kết hợp ghép cặp không trọng số.
Bài tập luyện
- Gán Công Việc Bitmask (knapbitmask): (Hard) Phân công người cho việc với tổng chi phí nhỏ nhất; đề gợi ý quy hoạch động bitmask nhưng Hungary giải thẳng trong , tiện để kiểm tra cài đặt.
- Bài Toán Phân Công (assgn): (Expert) Bài phân công thuần với , phải in cả cách phân công; quy hoạch động bitmask không còn chạy được, cần đúng thuật toán Hungary.
- Khôi phục DNA (icpc26mnh): (Expert) Xâu ngắn nhất chứa mọi -mer cho trước, quy về đường đi Euler trên đồ thị de Bruijn với ít cạnh lặp nhất; bước cuối là ghép các đỉnh thừa cạnh vào với các đỉnh thiếu cạnh vào theo khoảng cách BFS bằng thuật toán Hungary trên ma trận cỡ .
Bình luận