14.2K 213 1.7K

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

Cấu trúc dữ liệu và Giải thuật Bài 140: Luồng cực đại và Luồng cực tiểu có ràng buộc dung lượng dưới (Max-Flow & Min-Flow with Lower Bounds) - Tối ưu hóa lưu lượng sau khi thỏa mãn luồng khả thi.

Ở Bài 139, chúng ta đã nắm vững kỹ thuật khử cận dưới để kiểm tra tính khả thi của một luồng tuần hoàn (Feasible Circulation). Tuy nhiên, trong hầu hết các bài toán vận trù học và tối ưu hóa hệ thống, việc tìm ra một luồng hợp lệ mới chỉ là bước khởi đầu. Chúng ta thường đối mặt với hai bài toán tối ưu đối lập trên mạng có nguồn $s$ và đích $t$ :

Luồng cực đại có cận dưới ( $s-t$ Max-Flow with Lower Bounds): Sau khi đã đáp ứng đầy đủ hạn mức tối thiểu $l(e)$ trên mọi cung, đẩy thêm tối đa lượng lưu lượng có thể từ $s$ đến $t$ .
Luồng cực tiểu có cận dưới ( $s-t$ Min-Flow with Lower Bounds): Tìm giá trị luồng nhỏ nhất phát ra từ $s$ và thu về tại $t$ sao cho vẫn vừa đủ thỏa mãn các ràng buộc cận dưới $l(e)$ của toàn bộ các cạnh trên mạng (ứng dụng trong việc tiết kiệm chi phí vận hành, giảm tải tiêu thụ năng lượng hoặc tối thiểu hóa băng thông dự phòng).

Cả hai bài toán đều được giải quyết chuẩn xác bằng cách kết hợp thuật toán tìm luồng khả thi (Bài 139) với thuật toán Dinic chạy trên đồ thị thặng dư.

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

Cho mạng đồ thị có hướng $G = (V, E)$ với đỉnh phát $s$ và đỉnh thu $t$ . Mỗi cạnh $e = (u, v)$ có cận dưới $l(e) \ge 0$ và dung lượng $c(e) \ge l(e)$ .

Mọi đỉnh $u \notin \{s, t\}$ phải tuân thủ điều kiện bảo toàn luồng nghiêm ngặt:

$\sum_{e \in \text{in}(u)} f(e) - \sum_{e \in \text{out}(u)} f(e) = 0$

Giá trị của luồng phát ra từ $s$ (và đi vào $t$ ) được định nghĩa là:

$\vert{}f\vert{} = \sum_{e \in \text{out}(s)} f(e) - \sum_{e \in \text{in}(s)} f(e) = \sum_{e \in \text{in}(t)} f(e) - \sum_{e \in \text{out}(t)} f(e)$

Mục tiêu 1 (Max-Flow): Tìm luồng $f$ khả thi sao cho $\vert{}f\vert{} \to \max$ .
Mục tiêu 2 (Min-Flow): Tìm luồng $f$ khả thi sao cho $\vert{}f\vert{} \to \min$ .

2. Thuật toán Luồng cực đại có Cận dưới ( $s-t$ Max-Flow)

Quy trình tìm luồng cực đại gồm 3 giai đoạn:

    Giai đoạn 1:                  Giai đoạn 2:                  Giai đoạn 3:
Thêm cạnh ảo t -> s           Tìm luồng khả thi qua         Xóa t -> s, chạy Max-Flow
với dung lượng [0, ∞]           Siêu nguồn S*, Siêu đích T*      từ s -> t trên đồ thị thặng dư
      [t]                           [S*] ---> [u]                     [s] ==========> [t]
       |                              |        |                       (Đẩy thêm luồng
       | c = ∞                        v        v                        tối đa có thể)
       v                            [v] ---> [T*]
      [s]                    (Bão hòa mọi cung ra từ S*)

Bước 1: Khép kín mạng thành Luồng tuần hoàn

Thêm một cạnh ảo từ $t$ về $s$ với cận dưới bằng $0$ và cận trên vô cùng:

$e_{\text{cycle}} = (t \to s), \quad l(e_{\text{cycle}}) = 0, \quad c(e_{\text{cycle}}) = \infty$

Lúc này, toàn bộ mạng trở thành một bài toán tìm luồng tuần hoàn khả thi (Circulation).

Bước 2: Tìm luồng khả thi ban đầu

Áp dụng kỹ thuật ở Bài 139: Khử cận dưới $c'(e) = c(e) - l(e)$ , tính độ lệch $\Delta(u)$ , nối các cung phụ tới siêu nguồn $S^*$ và siêu đích $T^*$ .
Chạy Max-Flow từ $S^*$ đến $T^*$ .
Nếu không bão hòa hết các cung đi ra từ $S^*$ , kết luận: Mạng không tồn tại luồng khả thi (bài toán vô nghiệm).
Nếu bão hòa hoàn toàn, ta đã thu được một luồng hợp lệ ban đầu. Giá trị của luồng $s-t$ hợp lệ này chính bằng lượng luồng đã chảy qua cạnh ảo:

$f_0 = f(e_{\text{cycle}}) = f'(t \to s)$

Bước 3: Đẩy thêm luồng tối đa từ $s$ đến $t$

Xóa bỏ cạnh ảo $(t \to s)$ khỏi đồ thị thặng dư (bằng cách đặt dung lượng và luồng của nó về $0$ ).
Giữ nguyên trạng thái thặng dư hiện tại của tất cả các cạnh gốc trong mạng.
Tiếp tục chạy thuật toán Max-Flow từ $s$ đến $t$ trên đồ thị thặng dư này. Gọi lượng luồng đẩy thêm được là $\Delta f$ .
Tổng luồng cực đại:

$\vert{}f_{\max}\vert{} = f_0 + \Delta f$

3. Thuật toán Luồng cực tiểu có Cận dưới ( $s-t$ Min-Flow)

Trong khi bài toán Max-Flow đẩy thêm luồng từ $s$ đến $t$ , bài toán Min-Flow đòi hỏi rút bớt (hủy) luồng nhiều nhất có thể mà không vi phạm cận dưới của bất kỳ cạnh nào.

Nguyên lý Hủy luồng (Flow Cancellation / Push-Back)

Sau khi hoàn thành Bước 2 ở trên, ta có một luồng khả thi với giá trị ban đầu là $f_0 = f(t \to s)$ .

Trên đồ thị thặng dư, nếu một cạnh $e = (u, v)$ đang mang luồng $f(e) > l(e)$ , cạnh ngược $(v \to u)$ trên đồ thị thặng dư sẽ có dung lượng thặng dư là $f(e) - l(e) > 0$ .
Việc đẩy một đơn vị luồng dọc theo cạnh ngược $(v \to u)$ tương đương với việc giảm một đơn vị luồng trên cạnh xuôi $e = (u, v)$ .
Do đó, việc tìm cách giảm bớt lượng luồng truyền từ $s$ sang $t$ tương đương với việc đẩy luồng cực đại từ $t$ ngược về $s$ trên đồ thị thặng dư!

Quy trình thực hiện Min-Flow:

Xây dựng mạng phụ trợ với cạnh ảo $e_{\text{cycle}} = (t \to s)$ và tìm luồng khả thi ban đầu qua cặp $S^*, T^*$ . Ghi nhận giá trị luồng ban đầu $f_0 = f(t \to s)$ .
Xóa bỏ cạnh ảo $(t \to s)$ khỏi đồ thị thặng dư.
Chạy thuật toán Max-Flow từ $t$ ngược về $s$ trên đồ thị thặng dư. Gọi lượng luồng đẩy ngược được là $f_{\text{cancel}}$ .
Tổng luồng cực tiểu:

$\vert{}f_{\min}\vert{} = f_0 - f_{\text{cancel}}$

4. Hiện thực hóa bằng Golang

Đoạn mã dưới đây cài đặt hoàn chỉnh cấu trúc mạng luồng có cận dưới, hỗ trợ tính toán cả Max-Flow và Min-Flow:

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

type FlowEdge struct {
	to   int
	rev  int
	cap  int64
	flow int64
}

type Dinic struct {
	n     int
	adj   [][]FlowEdge
	level []int
	ptr   []int
}

func NewDinic(n int) *Dinic {
	return &Dinic{
		n:     n,
		adj:   make([][]FlowEdge, n),
		level: make([]int, n),
		ptr:   make([]int, n),
	}
}

func (d *Dinic) AddEdge(from, to int, cap int64) int {
	fwd := FlowEdge{to: to, rev: len(d.adj[to]), cap: cap, flow: 0}
	bwd := FlowEdge{to: from, rev: len(d.adj[from]), cap: 0, flow: 0}
	d.adj[from] = append(d.adj[from], fwd)
	d.adj[to] = append(d.adj[to], bwd)
	return len(d.adj[from]) - 1
}

func (d *Dinic) bfs(s, t int) bool {
	for i := 0; i < d.n; i++ {
		d.level[i] = -1
	}
	d.level[s] = 0
	queue := []int{s}

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for _, e := range d.adj[u] {
			if e.cap-e.flow > 0 && d.level[e.to] == -1 {
				d.level[e.to] = d.level[u] + 1
				queue = append(queue, e.to)
			}
		}
	}
	return d.level[t] != -1
}

func (d *Dinic) dfs(u, t int, pushed int64) int64 {
	if pushed == 0 || u == t {
		return pushed
	}

	for ; d.ptr[u] < len(d.adj[u]); d.ptr[u]++ {
		e := &d.adj[u][d.ptr[u]]
		tr := e.to

		if d.level[u]+1 != d.level[tr] || e.cap-e.flow == 0 {
			continue
		}

		pushVal := pushed
		if e.cap-e.flow < pushVal {
			pushVal = e.cap - e.flow
		}

		trPushed := d.dfs(tr, t, pushVal)
		if trPushed == 0 {
			continue
		}

		e.flow += trPushed
		d.adj[tr][e.rev].flow -= trPushed
		return trPushed
	}
	return 0
}

func (d *Dinic) MaxFlow(s, t int) int64 {
	var totalFlow int64 = 0
	for d.bfs(s, t) {
		for i := 0; i < d.n; i++ {
			d.ptr[i] = 0
		}
		for {
			pushed := d.dfs(s, t, INF)
			if pushed == 0 {
				break
			}
			totalFlow += pushed
		}
	}
	return totalFlow
}

type RawEdge struct {
	from, to int
	lower    int64
	upper    int64
	edgeIdx  int
}

type BoundedFlowNetwork struct {
	n        int
	edges    []RawEdge
	s, t     int
	dinic    *Dinic
	sStar    int
	tStar    int
	cycleIdx int
	baseFlow int64
}

func NewBoundedFlowNetwork(n, s, t int) *BoundedFlowNetwork {
	return &BoundedFlowNetwork{
		n: n,
		s: s,
		t: t,
	}
}

func (bfn *BoundedFlowNetwork) AddEdge(from, to int, lower, upper int64) {
	bfn.edges = append(bfn.edges, RawEdge{
		from:  from,
		to:    to,
		lower: lower,
		upper: upper,
	})
}

// Tìm luồng khả thi ban đầu
func (bfn *BoundedFlowNetwork) findFeasibleCirculation() bool {
	bfn.sStar = bfn.n
	bfn.tStar = bfn.n + 1
	bfn.dinic = NewDinic(bfn.n + 2)

	delta := make([]int64, bfn.n)
	for i := range bfn.edges {
		e := &bfn.edges[i]
		delta[e.from] += e.lower
		delta[e.to] -= e.lower
		e.edgeIdx = bfn.dinic.AddEdge(e.from, e.to, e.upper-e.lower)
	}

	// Thêm cạnh tuần hoàn ảo: t -> s có dung lượng [0, INF]
	bfn.cycleIdx = bfn.dinic.AddEdge(bfn.t, bfn.s, INF)

	var expectedFlow int64 = 0
	for i := 0; i < bfn.n; i++ {
		if delta[i] > 0 {
			bfn.dinic.AddEdge(i, bfn.tStar, delta[i])
		} else if delta[i] < 0 {
			bfn.dinic.AddEdge(bfn.sStar, i, -delta[i])
			expectedFlow += -delta[i]
		}
	}

	maxFlow := bfn.dinic.MaxFlow(bfn.sStar, bfn.tStar)
	if maxFlow != expectedFlow {
		return false
	}

	// Ghi nhận luồng khả thi ban đầu trên cạnh t -> s
	bfn.baseFlow = bfn.dinic.adj[bfn.t][bfn.cycleIdx].flow

	// Xóa cạnh tuần hoàn t -> s khỏi mạng thặng dư
	bfn.dinic.adj[bfn.t][bfn.cycleIdx].cap = 0
	bfn.dinic.adj[bfn.t][bfn.cycleIdx].flow = 0
	revIdx := bfn.dinic.adj[bfn.t][bfn.cycleIdx].rev
	bfn.dinic.adj[bfn.s][revIdx].cap = 0
	bfn.dinic.adj[bfn.s][revIdx].flow = 0

	return true
}

// SolveMaxFlow giải bài toán Luồng cực đại có cận dưới
func (bfn *BoundedFlowNetwork) SolveMaxFlow() (bool, int64, []int64) {
	if !bfn.findFeasibleCirculation() {
		return false, 0, nil
	}

	// Đẩy thêm luồng từ s sang t trên đồ thị thặng dư
	additionalFlow := bfn.dinic.MaxFlow(bfn.s, bfn.t)
	totalMaxFlow := bfn.baseFlow + additionalFlow

	// Khôi phục luồng thực tế
	flows := make([]int64, len(bfn.edges))
	for i, e := range bfn.edges {
		fPrime := bfn.dinic.adj[e.from][e.edgeIdx].flow
		flows[i] = fPrime + e.lower
	}

	return true, totalMaxFlow, flows
}

// SolveMinFlow giải bài toán Luồng cực tiểu có cận dưới
func (bfn *BoundedFlowNetwork) SolveMinFlow() (bool, int64, []int64) {
	if !bfn.findFeasibleCirculation() {
		return false, 0, nil
	}

	// Hủy luồng bằng cách đẩy tối đa từ t ngược về s
	canceledFlow := bfn.dinic.MaxFlow(bfn.t, bfn.s)
	totalMinFlow := bfn.baseFlow - canceledFlow

	// Khôi phục luồng thực tế
	flows := make([]int64, len(bfn.edges))
	for i, e := range bfn.edges {
		fPrime := bfn.dinic.adj[e.from][e.edgeIdx].flow
		flows[i] = fPrime + e.lower
	}

	return true, totalMinFlow, flows
}

func main() {
	// Mô phỏng mạng gồm 4 đỉnh (0: nguồn s, 3: đích t)
	// Đỉnh: 0 (s), 1, 2, 3 (t)
	// Cạnh:
	// 0 -> 1: [2, 5]
	// 0 -> 2: [1, 4]
	// 1 -> 2: [0, 2]
	// 1 -> 3: [1, 3]
	// 2 -> 3: [2, 6]
	n := 4
	s := 0
	t := 3

	// 1. Tính Luồng Cực Đại (Max-Flow with Lower Bounds)
	netMax := NewBoundedFlowNetwork(n, s, t)
	netMax.AddEdge(0, 1, 2, 5)
	netMax.AddEdge(0, 2, 1, 4)
	netMax.AddEdge(1, 2, 0, 2)
	netMax.AddEdge(1, 3, 1, 3)
	netMax.AddEdge(2, 3, 2, 6)

	feasibleMax, maxFlowVal, maxFlows := netMax.SolveMaxFlow()
	if !feasibleMax {
		fmt.Println("Không tồn tại luồng khả thi cho bài toán Max-Flow!")
		return
	}

	fmt.Printf("=== KẾT QUẢ LUỒNG CỰC ĐẠI CÓ CẬN DƯỚI ===\n")
	fmt.Printf("Giá trị Luồng Cực Đại: %d\n", maxFlowVal)
	for i, e := range netMax.edges {
		fmt.Printf("- Cạnh %d -> %d: Luồng = %d / [%d, %d]\n",
			e.from, e.to, maxFlows[i], e.lower, e.upper)
	}

	// 2. Tính Luồng Cực Tiểu (Min-Flow with Lower Bounds)
	netMin := NewBoundedFlowNetwork(n, s, t)
	netMin.AddEdge(0, 1, 2, 5)
	netMin.AddEdge(0, 2, 1, 4)
	netMin.AddEdge(1, 2, 0, 2)
	netMin.AddEdge(1, 3, 1, 3)
	netMin.AddEdge(2, 3, 2, 6)

	feasibleMin, minFlowVal, minFlows := netMin.SolveMinFlow()
	if !feasibleMin {
		fmt.Println("Không tồn tại luồng khả thi cho bài toán Min-Flow!")
		return
	}

	fmt.Printf("\n=== KẾT QUẢ LUỒNG CỰC TIỂU CÓ CẬN DƯỚI ===\n")
	fmt.Printf("Giá trị Luồng Cực Tiểu: %d\n", minFlowVal)
	for i, e := range netMin.edges {
		fmt.Printf("- Cạnh %d -> %d: Luồng = %d / [%d, %d]\n",
			e.from, e.to, minFlows[i], e.lower, e.upper)
	}
}

5. Phân tích Độ phức tạp và Tính chất Đại số

Thao tác	Giai đoạn 1 (Khả thi)	Giai đoạn 2 (Tối ưu hóa)	Tổng độ phức tạp thời gian	Chi phí bộ nhớ
Luồng Cực Đại ( $s-t$ )	Dinic ( $S^* \to T^*$ )	Dinic ( $s \to t$ )	$O(V^2 E)$	$O(V + E)$
Luồng Cực Tiểu ( $s-t$ )	Dinic ( $S^* \to T^*$ )	Dinic ( $t \to s$ )	$O(V^2 E)$	$O(V + E)$

Số lần chạy Dinic: Cả hai thuật toán đều thực hiện đúng 2 lần chạy Dinic: một lần trên mạng mở rộng $(V + 2)$ đỉnh để tìm luồng khả thi, và một lần trên mạng gốc để tối ưu hóa.
Khoảng giá trị khả thi: Nếu bài toán tồn tại nghiệm, tập các giá trị luồng hợp lệ từ $s$ đến $t$ tạo thành một đoạn liên tục khép kín $[\vert{}f_{\min}\vert{}, \vert{}f_{\max}\vert{}]$ . Mọi giá trị $K \in [\vert{}f_{\min}\vert{}, \vert{}f_{\max}\vert{}]$ đều tương ứng với ít nhất một cấu hình luồng khả thi.

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

Tối thiểu hóa tiêu thụ điện trong Mạng truyền dẫn (Energy-efficient Routing): Các trạm viễn thông có mức lưu lượng truy cập duy trì tối thiểu (SLA baseline). Chạy Min-Flow with Lower Bounds giúp xác định tổng lưu lượng nhỏ nhất cần phát từ trung tâm điều khiển, cho phép đưa các kênh dự phòng không cần thiết vào chế độ ngủ (Sleep Mode) để tiết kiệm điện năng.
Quy hoạch phân bổ tài nguyên nước & Thủy lợi: Các con đập và hồ chứa có lưu lượng xả đáy tối thiểu bắt buộc để duy trì hệ sinh thái hạ lưu ( $l(e)$ ). Bài toán Min-Flow cho biết lượng nước tối thiểu cần xả từ hồ thượng nguồn $s$ về hạ lưu $t$ trong mùa khô hạn.
Lập lịch chuyến bay và phi hành đoàn tối thiểu (Fleet Sizing & Turnaround): Mỗi chặng bay phải có tối thiểu một số lượng phi công/tiếp viên có chứng chỉ chuyên môn. Bài toán tìm số lượng nhân sự tối thiểu cần điều động từ sân bay căn cứ $s$ qua chuỗi hành trình để hoàn thành tất cả các chuyến bay bắt buộc.

cấu trúc dữ liệu