CHƯƠNG 5 CÁC THUẬT TOÁN TỐI ƯU MẠNG
5.2. MÔ HÌNH DÒNG LỚN NHẤT
1
2
3
4
5
6 8
7
9 Nguoàn
Các trạm trung chuyeồn
Nơi nhận
24 – Mô hình dòng lớn nhất
Những trạm bơm đƣợc đặt ở những vị trí thích hợp để đƣa chất lỏng di chuyển đều trong các ống dẫn. Mỗi đoạn đường ống có dung tích chứa giới hạn. Tùy theo thiết kế, mỗi đoạn đường ống có thể được dùng để tải chất lỏng theo 1 hoặc 2 chiều.
Những đoạn 1 chiều thì có năng suất giới hạn theo chiều đó, còn chiều ngƣợc lại thì năng suất là 0.
Hình 24 minh họa mạng đường ống dẫn đặc trưng. Bài toán đặc ra là cần xác định dung lƣợng lớn nhất của toàn bộ mạng ống dẫn giữa các nguồn và nơi nhận.
Giải quyết đƣợc bài toán này kết hợp với ma trận O - D (Origin - Destination) thì chúng ta có thể xác lập được đường đi để đảm bảo thông lượng là cực đại.
Mạng đường ống tiêu biểu
Để giải đƣợc bài toán, cần biến đổi hệ thống ống dẫn thành mạng với 1 nguồn (điểm khởi đầu) và 1 bể chứa (điểm kết thúc). Trên hình 24, ta thêm vào những đường truyền một chiều với sức chứa không giới hạn.
Trong quá trình giải toán sẽ dùng ký hiệu (i,j) với i < j. Và Cij, Cj i là ký hiệu cho dung lƣợng dòng chảy theo 2 chiều i j, và j i. Để tránh tình trạng nhầm lẫn, Cij
sẽ đƣợc đặt gần nút i và Cj i sẽ đặt gần nút j.
Khái niệm vết cắt
Vết cắt xác định những đoạn ống dẫn mà nếu loại bỏ chúng thì sẽ gây ra sự rối loạn của dòng chảy giữa nguồn và bể chứa. Dung lƣợng tại vết cắt (cut capacity) bằng dung lƣợng của những đoạn ống dẫn liên quan. Trong tất cả những vết cắt có thể, thì vết cắt với dung lƣợng nhỏ nhất (smallest capacity) sẽ cho dòng chảy lớn nhất trong mạng.
Thuật toán dòng lớn nhất
Ý tưởng chung của thuật toán là tìm những đoạn đường đi đặc biệt (breakthrough path) với dòng chảy tuyệt đối từ nguồn đến bể chứa. Dựa trên ý tưởng này, chúng ta phát triển thuật toán.
Xét đoạn (i,j) với dung lƣợng dòng chảy ban đầu là Cij, Cj i . Theo những tính toán trong quá trình phát triển thuật toán, một phần dung lƣợng này sẽ mất theo dòng chảy qua các ống. Phần dung lƣợng còn lại trong các ống dẫn sẽ thay đổi theo.
Dùng (c ij , c ji ) ký hiệu phần dung lƣợng còn lại này.
Với nút j nhận dòng chảy từ nút i, ta gán nhãn [a j , i], trong đó a j là dòng chảy từ i đến j. Các bước của thuật toán được tóm tắt như sau:
Bước 1: Với tất cả đoạn (i,j), giả sử dung lượng còn lại bằng với dung lượng ban đầu: (c ij , c ji ) = Cij, Cj i . Đặt a 1 = , và gán nhãn cho nguồn nút 1 là [,—]. Xét i = 1, đến bước 2.
Bước 2: Xác định S i là tập những nút j không được gán nhãn mà có thể đến trực tiếp từ i với dung lượng còn lại là dương (c ij >0, j S i )
- Nếu S i , đến bước 3 - Nếu S i = , đến bước 4 Bước 3: Xác định k S i sao cho
c ik = max {c ij } (j S i )
Đặt a k = c ik và gán nhãn cho k là [ak, i]. Nếu điểm kết thúc của mạng cũng đã được gán nhãn (ví dụ k = n) thì đường đi đặt biệt đã được tìm thấy, tiếp tục đến bước 5. Ngược lại, đặt i = k, và đi trở lại bước 2.
Bước 4: Nếu i = 1, không có đường đi đặc biệt nào hiện hữu; qua bước 6.
Ngược lại, cho r là điểm đã được gán nhãn ngay trước điểm i hiện tại và loại i khỏi tập các điểm sát cận r. Cho i = r và trở lại bước 2.
Bước 5: Cho N p = { 1,k 1 , k 1 , …, n } xác định các điểm thuộc đường đặc biệt p từ nguồn 1 cho tới đích n. Dòng lớn nhất đƣợc tính nhƣ sau:
f p = min { a 1 , a k1 , a k2, …, a n }
Dung lượng còn lại của mỗi cung dọc theo đường đặc biệt giảm một lượng bằng f b theo hướng dòng chảy và tăng một lượng bằng f b theo hướng ngược lại – nghĩa là, cho các điểm i và j trên đường đạc biệt, dung lƣợng còn lại thay đổi từ giá trị hiện tại (c ij , c ji ) thành
(a) (c ij - f b , c ji + f b ) nếu dòng chảy từ i sang j (b) (c ij + f b , c ji - f b ) nếu dòng chảy từ j sang i
Phục hồi lại các điểm đã bị loại bỏ trong bước 4. Cho i = 1, trở lại bước 2 để thử một đường đặc biệt khác.
Bước 6: Giải pháp
(a) Giả sử m đường đặc biệt đã được xác định, dòng chảy tối đa quan mạng đƣợc tính nhƣ sau:
(b) Giả sử dung lƣợng còn lại ban đầu và cuối cùng của cung (i,j) là Cij, Cj i và (c ij , c ji ), dòng chảy tối ƣu đƣợc tính nhƣ sau:
Cho (, ) = Cij- Cij, Cj i Cji . Nếu > 0, dong2 chảy tối ƣu từ i tới j là . Ngƣợc lại, nếu >0 dòng chảy tối ƣu từ j tới i là (, không thể đồng thời cùng dương).
Quy trình tại bước 4 được sử dụng khi thuật toán bi nghẽn ngay tại điểm trước khi đường đặc biệt có thể hoàn thành. Các hiệu chỉnh dòng chảy trong bước 5 có thể giải thích thông qua sơ đồ mạng dòng chảy nhƣ hình 25.
Mạng (a) cho đường đặc biệt thứ nhất N 1 ={1,2,3,4} với dung lượng tối đa f 1 = 5.
Nhƣ vậy, dung lƣợng còn lại của mỗi cung (1,2), (2,3), (3,4) thay đổi từ (5,0), (0,5), theo bước 5. Mạng (b) cho ta đường đặc biệt thứ hai N 2 ={1,2,3,4} với dung lượng tối đa f 2 = 5. Sau khi thực hiện các hiệu chỉnh dòng chảy cần thiết, ta có mạng (c) với không đường đặc biệt nào. Mạng (c) khác (b) là hướng dòng chảy từ 2 3 bị loại bỏ. Thuật toán cho phép ta ―nhớ‖ hướng dòng chảy từ 2 tới 3 đã được thực hiện nhờ ta tăng dung lượng trong hướng ngược lại từ 0 tới 5 (trong bước 5).
2
1 4
3
2
1 4
3
2
1 4
3 5
5 0
0
0 0 0
5 5
5
5 5
5 0
0
0 0
5 0
5
0
0 5
5 0
5
5 5 0
0 [5,1]
[5,2]
[5,3]
[5,1]
[5,3]
[5,2]
Path: 1 - 2 - 3 - 4, f1 = 5 Path: 1 - 3 - 2 - 4, f1 = 5 No breakthrough
(a) (b) (c)
25 - Sơ đồ mạng dòng chảy trong bài toán maximum flow