Tiểu luận Thiết kế và phân tích thuật toán luồng cực đại

Giống như trường hợp lập mô hình một bản đồ đường xá dưới dạng một đồ thị có hướng để tìm ra lộ trình ngắn nhất từ điểm này đến điểm kia, ta cũng có thể diễn dịch một đồ thị có hướng dưới dạng một "mạng luồng" và dùng nó để giải đáp các câu hỏi về các luồng vật chất [material flows]. Hãy tưởng tượng một luồng di chuyển vật chất qua một hệ thống từ nguồn, ở đó vật chất được tạo, đến một bồn [sink], ở đó nó được tiêu thụ. Nguồn tạo ra vật chất theo một tốc độ đều đặn, và bồn tiêu thụ vật chất theo cùng tốc độ. "Luồng di chuyển" (flow) của vật chất tại một điểm bất kỳ trong hệ thống theo trực giác là tốc độ và vật chất di chuyển. Có thể dùng các mạng luồng để lập mô hình các chất lỏng chảy qua các ống dẫn, các linh kiện qua các dây chuyền lắp ráp, dòng điện qua các mạng lưới điện, thông tin qua các mạng truyền thông, và . Mỗi cạnh có hướng trong một hạng luồng có thể được xem như một ống dẫn cho vật chất. Mỗi ống dẫn có một dung lượng đã định, được nêu dưới dạng tốc độ cực đại qua đó vật chất có thể lưu chuyển qua ống dẫn, như 200 gallon chất lỏng mỗi giờ qua một ống dẫn hoặc 20 ampere dòng điện qua một dây dẫn. Các đỉnh là các khớp nối của ống dẫn, và khác với nguồn và bồn, vật chất chảy qua các đỉnh mà không ứ đọng lại trong chúng. Nói cách khác, tốc độ mà vật chất này là "sự bảo toàn luồng lưu", và nó giống như Luật Dòng Điện [Current Law] của Kirchhoff khi vật chất là dòng điện. Bài toán luồng cực đại là bài toán đơn giản nhất liên quan đến các mạng luồng. Nó đặt vấn đề, Đâu là tốc độ lớn nhất mà vật có thể chuyển đi từ nguồn đến bồn mà không vi phạm bất kỳ hạn chế dung lượng nào? Như sẽ thấy trong chương này, bài toán này có thể được giải quyết bằng các thuật toán hiệu quat. Hơn nữa, ta có thể thích ứng các kỹ thuật căn bản mà các thuật toán này sử dụng để giải quyết các bài toán luồng mạng khác. Chương này trình bày hai phương pháp chung để giải quyết bài toán luồng cực đại. Đoạn 26, trình bày các khái niệm về các mạng luồng và các luồng lưu chuyển, chính thức định nghĩa bài toán luồng cực đại. Đoạn 26.2 mô tả phương pháp cổ điển của Ford và Fulkerson để tìm các luồng cực đại. Đoạn 26.3 mô tả một ứng dụng của phương pháp này: tìm một so khớp cực đại trong một đồ thị hai nhánh không hướng. Đoạn 26.4 trình bày phương pháp đẩy luồng trước [preflow - push], làm cơ sở cho nhiều thuật toán nhanh nhất để giải quyết các bài toán luồng mạng. Đoạn 26.5 đề cập thuật toán "nâng tới trước" [lift - to - front], một thực thi cụ thể của phương pháp đẩy luồng trước chạy trong thời gian O(V3). Tuy thật toán này không phải là thuật toán nhanh nhất được biết, song nó minh họa vài kỹ thuật được dùng trong các thuật toán nhanh nhất theo tiệm cận, và nó tương đối hiệu quả trong thực tế.

TÀI LIỆU LUẬN VĂN CÙNG DANH MỤC