08.2-Thảo luận bài tập

Tài liệu tham khảo

• Lecture slides of Kevin Wayne, via www.cs.princeton.edu

• Phạm Trọng Khiêm, THPT chuyên Hoàng Lê Kha, Tây Ninh, chuyên đề Duyên Hải Bắc Bộ 2021

• Đoàn Nguyễn Thành Lương, Đại học Việt Hàn, contest giao lưu đội tuyển 1 (luồng)

Bài tập ví dụ

Luồng cực đại

Cho mạng G có n đỉnh và m cạnh, đỉnh phát là 0, và đỉnh thu là n-1. Hãy tìm luồng f* trong mạng sao cho giá trị val(f*) của luồng f* là lớn nhất.

Input: AMAXFLOW.INP

·       Dòng 1: Ghi 2 số nguyên n, m cho biết số đỉnh và số cung trong mạng G.

·       m dòng tiếp theo: Mỗi dòng ghi 3 số nguyên u, v, c cho biết cung nối từ u đến v có trọng số là c

Output: AMAXFLOW.OUT

·       Ghi một số nguyên dương cho biết giá trị luồng cực đại tìm được

Ví dụ: 

Phân tích

Đầu tiên, chúng ta sẽ sử dụng thuật toán Ford-Fulkerson gốc như đã dẫn ở phần lý thuyết nền (Lecture slides of Kevin Wayne).

nhắc lại ý tưởng chính:

1/ Bắt đầu với khởi tạo luồng f* = 0

2/ Trong khi <tồn tại đường tăng luồng (augmenting path) từ s đến t>, ta thực hiện tăng luồng f dọc theo đường tăng luồng tìm được.

  3/ Trả về giá trị luồng f* 

Một số khái niệm liên quan

Mạng thặng dư

Là mạng Gf có số đỉnh là V, số cung là 2*E. Gf cho biết khả năng có thể tăng thêm cho luồng f trên mỗi cung. Một số đặc điểm

·       Mỗi cung e(u,v) trong mạng thặng dư có một cung ngược e’(v,u) tương ứng. Mỗi cung có một giá trị thặng dư thông qua (Residual Capacity - RC(e)). Đây chính là khả năng tăng thêm cho luồng f(e) trên cung e tương ứng. Giá trị RC(e) được tính:

- Cung thuận e(u, v): RC(e) = C(e) – f(e)

- Cung ngược e’(v, u): RC(e’) = f(e)

Ví dụ: Cung e(u,v) như hình sau

Trong mạng thặng dư tương ứng, ta có cung thuận e(u,v), và cung ngược e’(v,u) lần lượt có RC(e) = c(e) – f(e) = 17 – 6 = 11, RC(e’) = f(e) = 6 như sau: 

·       Nếu có một đường đi từ s đến T trên mạng thặng dư sao cho các cung trên đường đi đều có giá trị RC(e) > 0, thì đây chính là đường tăng luồng.

• Nếu không còn tìm được đường tăng luồng thì khi đó luồng là cực đại.

• Để tìm đường tăng luồng ta có thể sử dụng các thuật toán DFS, BFS, PFS (Priority First Search) trên mạng thặng dư.

Nếu gọi B là giá trị thặng dư thông qua nhỏ nhất trên đường tăng luồng tìm được (B còn được gọi là “bottleneck capacity” ),

Ta có: B = min(RC(e)), với e là cung thuộc đường tăng luồng tìm được. Ta tiến hành cập nhật luồng trên các cung của G thuộc đường tăng luồng như sau:

f((u,v)) += B  và f((v,u)) -= B 

Việc tại sao cần có cung ngược trên mạng thặng dư các em xem lại trong phần trình bày của Kevin Weyne trong phần lý thuyết nền. Nhưng về cơ bản là để khắc phục yếu điểm của thuật toán tham lam gây ra khi kết thúc việc đẩy luồng đi (luôn lựa cung có khả năng thông qua lớn nhất để đẩy). Lúc này ta không có cách gì biết luồng đó có cực đại hay chưa, giả sử biết là chưa ta cũng không thể quay ngược lại. Cung ngược ở đây như một cơ chế cho phép ta hồi lại lượng luồng đã tăng lên trước đó.

Bây giờ đã đủ các khái niệm để ta mô phỏng thuật toán Ford-Fulkerson cho test mẫu của đề bài:

Mạng G(V,E) của test mẫu được khởi tạo luồng bằng 0 như hình sau: 

Tăng luồng lần 1:

Ta có mạng thặng dư, đường tăng luồng là: s, 2, 5, t è B = 8  è f = 0 + B = 0 + 8 = 8. 

Tăng luồng lần 2:

Ta có mạng thặng dư, đường tăng luồng là: s, 2, 3, 5, t è B = 2 è f = 8 + 2 = 10 

Tăng luồng lần 3:

Ta có mạng thặng dư, đường tăng luồng là: s, 3, 5, 4, t è B = 6 è f = 10 + 6 = 16 

Tăng luồng lần 4:

Ta có mạng thặng dư, đường tăng luồng là: s, 3, 2, 4, t è B = 2 è f = 16 + 2 = 18 

Tăng luồng lần 5:

Ta có mạng thặng dư, đường tăng luồng là: s, 3, 5, 2, 4, t è B = 1 è f = 18 + 1 = 19 

Ta thấy không thể tìm thấy đường tăng luồng trên mạng thặng dư Gf 

==> Luồng đã đạt giá trị cực đại |f*| = 19 

Độ phức tạp

Ta phải thực hiện 1 vòng lặp while nhiều lần để xác định đường tăng luồng. Việc xác định đường tăng luồng có thể dùng DFS hoặc BFS, cả 2 đều cho độ phức tạp là O(E). Và trong trường hợp xấu nhất ta sẽ tăng f thêm 1 đơn vị cho mỗi lần lặp cho đến khi đạt cực đại f*. Vì vậy độ phức tạp thuật toán Ford – Fulkerson là O(E|f*|).

      Thông thường, để giảm số lần tăng luồng, người ta hay tìm cách tăng tốc ở một trong hai bước: số lượng đường tăng luồng và số lần thực hiện thực hiện thuật toán. 

Nhiệm vụ 1. Cài đặt thử bài tập trên -->Link chấm: VNOJ

Khuyến khích cài bằng nhiều thuật khác nhau để so sánh tốc độ

Các bạn đã học trước về luồng cực đại có thể chuyển qua làm nhiệm vụ 2:

Nhiệm vụ 2: Thực hiện contest Luyện tập luồng cực đại - 1

Đối với các bạn đã rành về luồng, có thể chuyên sang làm nhiệm vụ 3:

Nhiệm vụ 3: Thực hiện contest giao lưu đội tuyển - luồng(thầy Lương)