Bài 19: Đèn giao thông thông minh và luồng cực đại – Tìm nút cổ chai của thành phố

Giờ cao điểm, bao nhiêu xe có thể đi từ khu dân cư vào trung tâm thành phố mỗi phút? Đường nào là "nút cổ chai"? Câu hỏi này có lời giải chính xác nhờ một thuật toán đồ thị kinh điển: luồng cực đại.

Bài thứ mười chín của chuyên mục "Thuật toán trong đời sống": mạng giao thông, luồng cực đại và đèn tín hiệu thông minh.

1. Mạng đường phố là một đồ thị có sức chứa

Coi mỗi ngã tư là một đỉnh, mỗi đoạn đường là một cạnh có hướng, và mỗi cạnh có một sức chứa – số xe tối đa đi qua mỗi phút. Bài toán luồng cực đại hỏi: tối đa bao nhiêu xe mỗi phút có thể đi từ điểm xuất phát (nguồn) đến đích?

2. Thuật toán Ford–Fulkerson (1956)

Năm 1956, L. R. Ford và D. R. Fulkerson công bố bài báo "Maximal Flow Through a Network" trên Canadian Journal of Mathematics. Ý tưởng:

1. Tìm một đường đi từ nguồn đến đích mà mọi đoạn còn "chỗ trống" (gọi là đường tăng luồng).
2. Cho thêm xe đi theo đường đó, nhiều nhất bằng đoạn hẹp nhất trên đường.
3. Lặp lại đến khi không còn đường tăng luồng.

Khi tìm đường tăng luồng bằng BFS (tìm kiếm theo chiều rộng), ta được thuật toán Edmonds–Karp – phiên bản hay dùng trong lập trình thi đấu.

Luồng cực đại bằng Edmonds–Karp

#include <bits/stdc++.h>
using namespace std;
// Luồng cực đại bằng Edmonds–Karp (Ford–Fulkerson + BFS)
int n; vector<vector<int>> cap;
int maxflow(int s, int t){
    int flow = 0;
    while(true){
        vector<int> par(n, -1); par[s] = s;
        queue<int> q; q.push(s);
        while(!q.empty() && par[t] == -1){
            int u = q.front(); q.pop();
            for(int v = 0; v < n; v++)
                if(par[v] == -1 && cap[u][v] > 0){ par[v] = u; q.push(v); }
        }
        if(par[t] == -1) return flow;          // không còn đường tăng luồng
        int push = INT_MAX;
        for(int v = t; v != s; v = par[v]) push = min(push, cap[par[v]][v]);
        for(int v = t; v != s; v = par[v]){ cap[par[v]][v] -= push; cap[v][par[v]] += push; }
        flow += push;
    }
}
int main(){
    // 0 = Khu dân cư, 1 = Ngã tư A, 2 = Ngã tư B, 3 = Ngã tư C, 4 = Trung tâm
    // sức chứa: số xe / phút mà mỗi đoạn đường cho đi qua
    n = 5; cap.assign(n, vector<int>(n, 0));
    cap[0][1] = 40; cap[0][2] = 30;
    cap[1][2] = 10; cap[1][3] = 25;
    cap[2][3] = 15; cap[2][4] = 20;
    cap[3][4] = 35;
    cout << "Luong xe toi da: " << maxflow(0, 4) << " xe/phut\n";
}

from collections import deque

def max_flow(cap, s, t):
    # Edmonds–Karp: liên tục tìm đường tăng luồng ngắn nhất bằng BFS
    n, flow = len(cap), 0
    while True:
        par = [-1] * n; par[s] = s
        q = deque([s])
        while q and par[t] == -1:
            u = q.popleft()
            for v in range(n):
                if par[v] == -1 and cap[u][v] > 0:
                    par[v] = u; q.append(v)
        if par[t] == -1:
            return flow
        push, v = float("inf"), t
        while v != s:
            push = min(push, cap[par[v]][v]); v = par[v]
        v = t
        while v != s:
            cap[par[v]][v] -= push; cap[v][par[v]] += push; v = par[v]
        flow += push

# 0 = Khu dân cư, 1 = Ngã tư A, 2 = Ngã tư B, 3 = Ngã tư C, 4 = Trung tâm
cap = [[0] * 5 for _ in range(5)]
cap[0][1], cap[0][2] = 40, 30
cap[1][2], cap[1][3] = 10, 25
cap[2][3], cap[2][4] = 15, 20
cap[3][4] = 35
print("Luong xe toi da:", max_flow(cap, 0, 4), "xe/phut")

Kết quả chạy:

Luong xe toi da: 55 xe/phut

3. Định lý lát cắt cực tiểu: tìm nút cổ chai

Kết quả nổi tiếng trong bài báo của Ford và Fulkerson: luồng cực đại bằng tổng sức chứa nhỏ nhất của một "lát cắt" – tập các đoạn đường mà nếu chặn hết thì không xe nào đến được đích.

Trong ví dụ, hai đoạn đường đổ vào Trung tâm có sức chứa 20 + 35 = 55 xe/phút – đúng bằng luồng cực đại. Đây chính là nút cổ chai: mở rộng các đường khác cũng vô ích nếu không mở rộng hai đoạn này.

4. Đèn giao thông thông minh ngoài đời

• SCATS (Úc): được Sở Giao thông bang New South Wales phát triển từ năm 1975, theo trang chính thức hiện được lắp tại hơn 65.000 nút giao ở 218 thành phố thuộc 33 quốc gia.
• SCOOT (Anh): hệ thống điều khiển đèn tín hiệu thích ứng theo thời gian thực, do Phòng thí nghiệm Nghiên cứu Giao thông (TRL) phát triển năm 1979.
• Google Project Green Light: dùng AI và dữ liệu bản đồ để đề xuất chỉnh thời gian đèn; theo Google, số liệu ban đầu cho thấy tiềm năng giảm đến 30% số lần dừng xe và 10% khí thải tại các nút được phối hợp.
• Hà Nội: ngày 13/12/2025, Công an TP Hà Nội khánh thành Trung tâm điều khiển giao thông thông minh, kết nối 1.837 camera tại 195 nút giao trọng điểm, điều khiển đèn tín hiệu thích ứng theo thời gian thực (theo VnEconomy).

Các hệ thống này dùng nhiều kỹ thuật khác nhau; luồng cực đại ở đây là mô hình giúp hiểu bản chất "sức chứa" và "nút cổ chai" của mạng đường.

5. Nghịch lý Braess: thêm đường có thể làm tắc hơn!

Năm 1968, nhà toán học Dietrich Braess chỉ ra rằng trong mạng giao thông mà mỗi tài xế tự chọn đường nhanh nhất cho mình, việc mở thêm một con đường mới có thể làm thời gian đi lại của mọi người tăng lên. Lý do: lựa chọn "tốt nhất cho từng người" không phải lúc nào cũng tốt nhất cho cả hệ thống.

6. Bạn học được gì từ đây?

• BFS – thuật toán bạn học rất sớm – là "động cơ" bên trong luồng cực đại.
• Luồng cực đại giải được rất nhiều bài toán khác: ghép cặp, phân công công việc, cắt ảnh…
• Tối ưu cho từng cá nhân khác với tối ưu cho cả hệ thống.

Bài tập luyện tập

• CSES – Download Speed (luồng cực đại cơ bản)
• CSES – Police Chase (lát cắt cực tiểu)
• CSES – School Dance (ghép cặp bằng luồng)

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 20: Spotify và YouTube nén âm thanh, video ra sao? Biến đổi Fourier giải thích đơn giản

Đọc tiếp: nén âm thanh & Fourier →

← Bài trước: thang máy & SCANXem tất cả 27 bài →

Nguồn tham khảo

• Ford & Fulkerson (1956) – Maximal Flow Through a Network, Canadian Journal of Mathematics
• Google Research – Project Green Light
• SCATS – About us
• Hull City Council – SCOOT urban traffic control
• VnEconomy (13/12/2025) – Hà Nội vận hành Trung tâm điều khiển giao thông thông minh
• UMass Amherst – Braess Paradox