Luận văn Nghiên cứu một số vấn đề của lý thuyết đồ thị ứng dụng trong giải quyết một số bài toán thực tế

KH OA C NT T – Đ H KH TN TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP.HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM TẠ TRƯỜNG ĐỨC ANH - NGUYỄN NHẬT QUỲNH NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG GIẢI QUYẾT MỘT SỐ BÀI TOÁN THỰC TẾ LUẬN VĂN CỬ NHÂN TIN HỌC TP.HỒ CHÍ MINH, 2004 KH OA C NT T – Đ H KH TN TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP.HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM TẠ TRƯỜNG ĐỨC ANH _0012007 NGUYỄN NHẬT QUỲNH_0012082 NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG GIẢI QUYẾT MỘT SỐ BÀI TOÁN THỰC TẾ LUẬN VĂ CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN T.S DƯƠNG ANH ĐỨC NIÊN KHÓA 2000 - 2004 KH OA C NT T – Đ H KH TN NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… KH OA C NT T – Đ H KH TN NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… KH OA C NT T – Đ H KH TN LỜI CẢM ƠN Luận văn của chúng em sẽ rất khó hoàn thành nếu không có sự truyền đạt kiến thức quí báu và sự hướng dẫn tận tình của Thầy Dương Anh Đức và thầy Lê Thụy Anh. Chúng em xin chân thành cám ơn sự chỉ bảo của các thầy. Chúng con xin gửi tất cả lòng biết ơn, sự kính trọng đến ông bà, cha mẹ, cùng toàn thể gia đình, những người đã nuôi dạy, đã cho chúng con niềm tin và nghị lực để vượt qua mọi khó khăn. Chúng em xin trân trọng cám ơn quý Thầy cô trong Khoa Công nghệ thông tin trường Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng dạy, truyền đạt những kiến thức quý báu và tạo điều kiện cho chúng em được thực hiện luận văn này. Xin chân thành cám ơn sự giúp đỡ, động viên và chỉ bảo rất nhiệt tình của các anh chị đi trước và tất cả bạn bè. Các anh chị, các bạn luôn có mặt trong những thời điểm khó khăn nhất, tiếp thêm động lực và ý chí, giúp chúng tôi hoàn thành được luận văn. Mặc dù đã cố gắng nỗ lực hết sức mình, song chắc chắn luận văn không khỏi còn nhiều thiếu sót. Chúng em rất mong nhận được sự thông cảm và chỉ bảo tận tình của quý Thầy cô và các bạn. Tp.HCM, 7/2004 Nhóm sinh viên thực hiện Tạ Trường Đức Anh Nguyễn Nhật Quynh KH OA C NT T – Đ H KH TN MỤC LỤC CHƯƠNG 1 : MỞ ĐẦU ....................................................................................1 1.1. Ý nghĩa và mục tiêu của đề tài..........................................................................1 1.2. Nội dung của luận văn .......................................................................................2 CHƯƠNG 2 : TỔNG QUAN VỀ BÀI TOÁN LUỒNG TRÊN MẠNG........3 2.1. Một số khái niệm................................................................................................3 2.1.1. Đồ thị ...........................................................................................................3 2.1.2. Các phép biến đổi đồ thị ..............................................................................3 2.2. Các bài toán luồng trên mạng...........................................................................4 2.3. Một số ứng dụng cho bài toán luồng trên mạng .............................................4 2.3.1. Đường đi ngắn nhất......................................................................................4 2.3.2. Luồng cực đại ..............................................................................................4 2.3.3. Luồng có chi phí cực tiểu.............................................................................6 2.3.4. Phân công và xếp cặp...................................................................................7 2.4. Tóm tắt chương 2 ...............................................................................................7 CHƯƠNG 3 : LUỒNG CỰC ĐẠI ....................................................................8 3.1. ịnh nghĩa và ký hiệu.......................................................................................8 3.2. Luồng và lát cắt..................................................................................................8 3.2.1. Mạng thặng dư .............................................................................................9 3.2.2. Lát cắt s-t......................................................................................................9 3.2.3. Độ thông qua thặng dư của một lát cắt s-t .................................................10 3.2.4. Luồng qua một lát cắt s-t ...........................................................................10 3.3. Thuật toán đường tăng trưởng.......................................................................11 3.4. Thuật toán gán nhãn và định lý lát cắt tối thiểu ...........................................12 3.4.1. Độ phức tạp của thuật toán gán nhãn.........................................................14 3.4.2. Hạn chế của thuật toán gán nhãn ...............................................................14 3.5. Luồng có chặn dưới .........................................................................................15 3.5.1. Xác định luồng cực đại ..............................................................................16 3.5.2. Xây dựng luồng khả thi..............................................................................16 3.5.3. Mô tả đặc điểm của luồng khả thi trên mạng lưu thông ............................17 3.6. Cải tiến thuật toán đường tăng trưởng..........................................................19 3.6.1. Các nhãn khoảng cách ...............................................................................20 3.6.2. Thuật toán tỉ lệ với độ thông qua ...............................................................21 3.6.3. Thuật toán đường đi tăng trưởng ngắn nhất...............................................23 3.6.4. Thuật toán đẩy luồng .................................................................................25 3.7. Tóm tắt chương 3 .............................................................................................27 CHƯƠNG 4 : LUỒNG VỚI CHI PHÍ CỰC TIỂU ......................................28 4.1. Giới thiệu ..........................................................................................................28 4.1.1. Các giả thiết ...............................................................................................28 4.1.2. Đồ thị thặng dư ..........................................................................................29 4.2. Các điều kiện tối ưu cho bài toán ...................................................................29 4.2.1. Các điều kiện tối ưu về chu trình âm .........................................................29 4.2.2. Các điều kiện tối ưu về chi phí rút gọn......................................................29 4.2.3. Các điều kiện tối ưu bổ sung......................................................................31 4.3. Liên hệ các luồng tối ưu và các khả năng tối ưu của đỉnh ...........................31 KH OA C NT T – Đ H KH TN 4.4. Thuật toán khử chu trình âm và tính chất nguyên.......................................33 4.5. Thuật toán đường đi ngắn nhất liên tiếp .......................................................35 4.6. Thuật toán Primal-dual...................................................................................39 4.7. Các thuật toán cải tiến.....................................................................................42 4.7.1. Cải tiến thuật toán đường đi ngắn nhất liên tiếp ........................................43 4.7.2. Một số cách cải tiến khác...........................................................................43 4.8. Tóm tắt chương 4 .............................................................................................46 CHƯƠNG 5 : SỰ PHÂN CÔNG VÀ XẾP CẶP ...........................................48 5.1. Giới thiệu ..........................................................................................................48 5.1.1. Các cạnh bắt cặp và các nút bắt cặp...........................................................48 5.1.2. Đường đi xen kẽ và chu trình xen kẽ .........................................................48 5.1.3. Đường tăng trưởng.....................................................................................49 5.1.4. Sự khác biệt đối xứng ................................................................................50 5.2. Bài toán bắt cặp lớn nhất trên đồ thị phân đôi .............................................50 5.2.1. Chuyển về bài toán luồng cực đại trong mạng đơn giản ...........................50 5.2.2. Thuật toán bắt cặp lớn nhất trên đồ thị phân đôi .......................................51 5.3. Bài toán bắt cặp có trọng số trên đồ thị phân đôi .........................................55 5.3.1. Thuật toán đường đi ngắn nhất liên tiếp ....................................................55 5.3.2. Thuật toán Hungary ...................................................................................55 5.3.3. Thuật toán tỉ lệ theo chi phí .......................................................................56 5.4. Bài toán bắt cặp trên đồ thị tổng quát ...........................................................56 5.4.1. Các khó khăn gặp phải trong thuật toán bắt cặp trên mạng phân đôi ........57 5.4.2. Hoa và nụ ...................................................................................................58 5.4.3. Sự thu nhỏ nụ .............................................................................................59 5.4.4. Thuật toán bắt cặp trên đồ thị không phân đôi...........................................60 5.5. Tóm tắt chương 5 .............................................................................................64 CHƯƠNG 6 : LUỒNG TỔNG QUÁT...........................................................65 6.1. Giới thiệu ..........................................................................................................65 6.2. Các cấu trúc rừng tăng trưởng.......................................................................66 6.2.1. Luồng trên đường đi ..................................................................................66 6.2.2. Luồng trên chu trình...................................................................................68 6.2.3. Cây tăng trưởng và rừng tăng trưởng.........................................................69 6.2.4. Các cấu trúc rừng tăng trưởng và các điều kiện tối ưu ..............................71 6.3. Xác định các khả năng và luồng cho một cấu trúc rừng tăng trưởng ........73 6.3.1. Xác định khả năng của đỉnh cho một cấu trúc rừng tăng trưởng...............73 6.3.2. Xác định luồng cho một cấu trúc rừng tăng trưởng ...................................75 6.4. Tóm tắt chương 6 .............................................................................................80 CHƯƠNG 7 : XÂY DỰNG ỨNG DỤNG DISTRIBUTION........................81 7.1. Yêu cầu thực tế và lý do xây dựng ứng dụng ................................................81 7.2. Mục tiêu của ứng dụng ....................................................................................81 7.3. Tiếp cận bài toán..............................................................................................82 7.3.1. Phát biểu bài toán.......................................................................................82 7.3.2. Mô hình toán học .......................................................................................82 7.3.3. Nhận xét .....................................................................................................83 7.3.4. Hướng tiếp cận của luận văn......................................................................83 7.4. Phân tích ...........................................................................................................89 7.4.1. Yêu cầu chức năng.....................................................................................89 KH OA C NT T – Đ H KH TN 7.4.2. Mô hình Use Case......................................................................................90 7.5. Thiết kế .............................................................................................................97 7.5.1. Thiết kế dữ liệu ..........................................................................................97 7.5.2. Thiết kế xử lý ...........................................................................................102 7.5.3. Thiết kế giao diện.....................................................................................105 7.6. Biểu đồ tương tác ...........................................................................................111 7.6.1. Xem thông tin các đại lý ..........................................................................111 7.6.2. Thay đổi nhu cầu của các đại lý...............................................................113 7.6.3. Xem thông tin các phương tiện................................................................115 7.6.4. Thay đổi thông tin về các phương tiện ....................................................117 7.6.5. Tìm phương pháp vận chuyển tối ưu .......................................................119 7.6.6. Tìm đường đi ngắn nhất từ nhà cung cấp đến các đại lý .........................121 7.6.7. Xuất lịch giao hàng ..................................................................................122 7.7. Cài đặt .............................................................................................................123 7.8. Hướng dẫn sử dụng .......................................................................................124 7.8.1. Di chuyển bản đồ đến vị trí khác : ...........................................................124 7.8.2. Phóng to, thu nhỏ bản đồ : .......................................................................124 7.8.3. Để tìm đường đi ngắn nhất từ nhà cung cấp đến các đại lý:....................125 Để tìm đường đi ngắn nhất từ nhà cung cấp đến 1 đại lý nào đó:.....................125 7.8.4. Để tính toán các đường đi có chi phí thấp nhất thỏa mãn nhu cầu của các đại lý: 126 7.8.5. Xem thông tin và cập nhật nhu cầu của tất cả các đại lý .........................127 7.8.6. Xem, cập nhật thông tin hoặc thêm các phương tiện chuyên chở mới: ...129 7.8.7. Xem lịch giao hàng trong ngày của các phương tiện...............................130 7.9. Tổng kết ..........................................................................................................132 7.9.1. Kết luận....................................................................................................132 7.9.2. Hướng phát triển ......................................................................................132 KH OA C NT T – Đ H KH TN DANH SÁCH CÁC ĐỊNH LÝ, TÍNH CHẤT, MỆNH ĐỀ Tính chất 3.1. .....................................................................................................................11 Tính chất 3.2 ......................................................................................................................11 Định lý 3.3: định lý Ford – Fullkerson về lát cắt nhỏ nhất ................................................14 Định lý 3.4: định lý về đường tăng trưởng ........................................................................14 Định lý 3.5: định lý về tính nguyên ...................................................................................14 Định lý 3.6: Định lý lát cắt nhỏ nhất mở rộng ...................................................................16 Định lý 3.7: điều kiện tồn tại luồng khả thi trên mạng lưu thông......................................19 Định lý 3.8 .........................................................................................................................19 Tính chất 3.9 ......................................................................................................................21 Tính chất 3.10 ...................................................................................................................21 Định lý 4.1: Các điều kiện tối ưu về chu trình âm.............................................................29 Tính chất 4.2 .....................................................................................................................30 Định lý 4.3: Các điều kiện tối ưu với chi phí rút gọn ........................................................30 Định lý 4.4 :Các điều kiện tối ưu bổ sung .........................................................................31 Định lý 4.5: Tính chất nguyên ...........................................................................................35 Bổ đề 4.6 ...........................................................................................................................36 Bổ đề 4.7 ............................................................................................................................36 Định lý 5.1: định lý về đường tăng trưởng ........................................................................49 Tính chất 5.2 ......................................................................................................................50 Tính chất 5.3 ......................................................................................................................58 Tính chầt 5.4 ......................................................................................................................59 Bổ đề 5.5 ............................................................................................................................64 Tính chất 6.1 ......................................................................................................................67 Tính chất 6.2 ......................................................................................................................68 Tính chất 6.3 ......................................................................................................................69 Tính chất 6.4 ......................................................................................................................69 Định lý 6.5: Các điều kiện tối ưu về luồng tổng quát ........................................................71 Tính chất 6.6: Các điều kiện tối ưu về cấu trúc rừng tăng trưởng .....................................72 KH OA C NT T – Đ H KH TN DANH SÁCH CÁC HÌNH Hình 2-1 ...............................................................................................................................6 Hình 3-1 Mô tả mạng thặng dư............................................................................................9 Hình 3-2 Ví dụ về một lát cắt s – t.....................................................................................10 Hình 3-3 Ví dụ về một mạng tăng trưởng ....................................................................11 Hình 3-4: Bài toán luồng cực đại không có luồng tương thích..........................................15 Hình 3-5 Minh họa đồ thị thặng dư ...................................................................................22 Hình 4-1 Minh họa thuật toán Khử chu trình âm..............................................................34 Hình 4-2 Minh họa thuật toán đường đi ngắn nhất liên tiếp..............................................39 Hình 4-3 Minh họa thuật toán Primal - dual ......................................................................42 Hình 5-1 Minh họa sự bắt cặp gồm 2 phần tử ...................................................................48 Hình 5-2 Minh họa sự bắt cặp gồm 3 phần tử ...................................................................49 Hình 5-3: Chuyển đổi bài toán bắt cặp các thành phần thành bài toán luồng cực đại .......51 Hình 5-4 Phát triển 1 cây xen kẽ........................................................................................52 Hình 5-5 Hai vì dụ về hoa..................................................................................................58 Hình 5-6 Sự thu gọn hoa....................................................................................................59 Hình 5-7 Xác định 1 luồng tăng trưởng trong mạng thu gọn ............................................63 Hình 5-8 Xác định 1 đường tăng trưởng trong mạng ban đầu...........................................64 Hình 6-1: Luồng trên đường đi trong 1 đồ thị tổng quát ...................................................67 Hình 6-2 Ví dụ về cây tăng trưởng và luồng tăng trưởng..................................................70 Hình 6-3 Minh họa tính toán các khả năng của đỉnh .........................................................75 Hình 6-4 Tính luồng trên các cung thuộc cây....................................................................76 Hình 6-5 Minh họa quá trình tính luồng cho 1 cây tăng trưởng ........................................78 Hình 7-1 Mô hình bài toán phân phối hàng .......................................................................85 Hình 7-2 Biểu đồ Use Case................................................................................................90 Hình 7-3 Sơ đồ các lớp dữ liệu ..........................................................................................97 Hình 7-4 Mô tả dữ liệu tính toán .....................................................................................102 Hình 7-5 Sơ đồ lớp sử lý..................................................................................................102 Hình 7-6 Sơ đồ các màn hình ..........................................................................................105 Hình 7-7 Thực đơn của ứng dụng ....................................................................................105 Hình 7-8 Thanh công cụ của ứng dụng............................................................................106 Hình 7-9 Màn hình chính.................................................................................................108 Hình 7-10 Màn hình thay đổi nhu cầu của một đại lý .....................................................108 Hình 7-11 Màn hình thay đổi nhu cầu của tất cả các đại lý.............................................109 Hình 7-12 Màn hình xem thông tin, cập nhật thêm mới phương tiện .............................110 Hình 7-13 Màn hình xem lịch giao hàng tối ưu về chi phí ..............................................110 Hình 7-14 Sequence Diagram: Xem thông tin các đại lý ................................................111 Hình 7-15 Collaboration Diagram: Xem thông tin các đại lý..........................................112 Hình 7-16 Sequence Diagram: Thay đổi nhu cầu của các đại lý .....................................113 Hình 7-17 Collaboration Diagram: Thay đổi nhu cầu của các đại lý ..............................114 Hình 7-18 Sequence Diagram: Xem thông tin các phương tiện ......................................115 Hình 7-19 Collaboration Diagram: Xem thông tin các phương tiện ...............................116 Hình 7-20 Sequence Diagram: Thay đổi thông tin về các phương tiện...........................117 Hình 7-21 Collaboration Diagram: Thay đổi thông tin về các phương tiện ....................118 Hình 7-22 Sequence Diagram: Tìm phương pháp vận chuyển tối ưu .............................119 Hình 7-23 Collaboration Diagram: Tìm phương pháp vận chuyển tối ưu.......................120 Hình 7-24 Sequence Diagram: Tìm đường đi ngắn nhất từ nhà cung cấp đến các đại lý121 Hình 7-25 Collaboration Diagram: Tìm đường đi ngắn nhất từ nhà cung cấp đến các đại lý ......................................................................................................................................121 KH OA C NT T – Đ H KH TN Hình 7-26 Sequence Diagram: Xuất lịch giao hàng ........................................................122 Hình 7-27 Collaboration Diagram: Xuất lịch giao hàng..................................................123 Hình 7-28 Màn hình chính..............................................................................................124 Hình 7-29 Đường đi ngắn nhất từ nhà cung cấp đến các đại lý.......................................125 Hình 7-30 Đường đi ngắn nhất từ nhà cung cấp đến một đại lý......................................126 Hình 7-31 Đường đi có chi phí thấp nhất ........................................................................127 Hình 7-32 Màn hình cập nhật thông tin các đại lý...........................................................128 Hình 7-33 Màn hình cập nhật nhu cầu cho 1 đại lý .........................................................129 Hình 7-34 Màn hình thêm mới, cập nhật thông tin cho các phương tiện ........................130 Hình 7-35 Màn hình hiển thị lịch giao hàng....................................................................131 Hình 7-36 Lịch giao hàng dưới dạng văn bản .................................................................131 KH OA C NT T – Đ H KH TN BẢNG TỪ ANH_VIỆT Tiếng Anh Tiếng Việt Admissible path Đường đi có thể chấp nhận Advance Tiến tới Alternating Xen kẽ Alternating tree Cây xen kẽ Assigment Sự phân công Augmented forest structures Các cấu trúc rừng tăng trưởng Augmenting path algorithm Thuật toán đường tăng trưởng Bucket Ngăn Capacity Độ thông qua Composite cost Chi phí kết hợp Cut Lát cắt Cycle-canceling Khử chu trình Decomposition Sự phân rã Distance label Nhãn khoảng cách Feasible flow Luồng khả thi Feasible solution Lời giải khả thi Flower and blossom Hoa và nụ Flows with lower bound Luồng có chặn dưới Generalized flow Luồng tổng quát Label-correcting algorithm Thuật toán hiệu chỉnh nhãn Label-setting algorithm Thuật toán gán nhãn Matching Sự bắt cặp Network flows Luồng trên mạng Nonsaturating Chưa bão hòa NP-complete NP-đầy đủ ε -optimal flows Luồng tối ưu ε Priority list Danh sách ưu tiên KH OA C NT T – Đ H KH TN Pseudoflow Luồng giả Reduced cost Chi phí rút gọn Residual capacity Độ thông qua thặng dư Residual network Mạng thặng dư Retreat Quay lui Saturating Bão hòa ∆ -scaling phase Pha tỉ lệ ∆ Symmetric difference Sự khác biệt đối xứng KH OA C NT T – Đ H KH TN CHƯƠNG 1: MỞ ĐẦU CHƯƠNG 1 : MỞ ĐẦU 1.1. Ý nghĩa và mục tiêu của đề tài Lý thuyết đồ thị là ngành khoa học xuất hiện từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi nhà toán học Thụy Sĩ Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán cây cầu Konigsberg nổi tiếng. Từ đó lý thuyết đồ thị ngày càng khẳng định được vị trí quan trọng của mình trong việc áp dụng để giải các bài toán thực tế nhờ vào việc tìm ra ngày càng nhiều của các định lý, công thức và thuật toán. Một bộ phận quan trọng của lý thuyết đồ thị là dạng bài toán luồng trên mạng, xuất hiện từ những nghiên cứu của Gustav Kirchhoff, và được những nhà nghiên cứu tiên phong như Lester Ford và Ray Fulkerson phát triển thành một lĩnh vực khoa học độc lập. Bài toán này có nhiều biến thể như: bài toán luồng có chi phí cực tiểu, bài toán đường đi ngắn nhất, bài toán luồng cực đại, bài toán vận chuyển, bài toán luồng tổng quát, bài toán luồng nhiều mặt hàng… Với sự xuất hiện ngày càng nhiều của các hệ thống mạng như: hệ thống mạng điện, mạng sản xuất và phân phối hàng hóa, mạng giao thông …, và phổ biến nhất hiện nay là mạng internet đã làm nảy sinh ra nhu cầu vận chuyển các chất liệu trên các mạng này sao cho đạt hiệu quả cao nhất; chất liệu ở đây có thể là dòng điện, dữ liệu, hàng hóa…; hiệu quả ở đây có thể xét theo tiêu chuẩn về thời gian, độ dài quãng đường, chi phí tiền bạc, mức độ an toàn…, bài toán luồng trên mạng ngày càng khẳng định được tính quan trọng của nó trong các ngành khoa học hiện đại. Sự phát triển mạnh mẽ của ngành công nghệ thông tin cùng với khả năng tính toán rất nhanh của máy tính đã giúp việc giải quyết các bài toán luồng trên mạng hiệu quả hơn và đem lại nhiều ứng dụng thực tiễn hơn. Với sự hướng dẫn của Tiến sĩ Dương Anh Đức, chúng em đã tập trung thực hiện đề tài “NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG VIỆC GIẢI QUYẾT BÀI TOÁN THỰC TẾ” nhằm tìm hiểu, thử nghiệm và ứng dụng các thuật toán của bài toán luồng trên mạng, nhất là bài toán luồng có chi phí cực tiểu, dạng tổng quát nhất của bài toán luồng trên 1 KH OA C NT T – Đ H KH TN CHƯƠNG 1: MỞ ĐẦU mạng, trong đó bao gồm việc xây dựng ứng dụng Distribution phục vụ cho việc lập kế hoạch giao hàng của nhà phân phối đến các đại lý với chi phí tối thiểu. 1.2. Nội dung của luận văn Luận văn gồm 7 chương: Chương 1: Mở đầu giới thiệu tổng quan về đề tài. Chương 2: Tổng quan về lý thuyết đồ thị giới thiệu một số khái niệm, phép biến đổi được sử dụng trong bài toán luồng trên mạng và một số lớp bài toán luồng trên mạng cùng ứng dụng của chúng. Chương 3: Bài toán luồng cực đại mô tả bài toán luồng cực đại, giới thiệu khái niệm lát cắt cùng với thuật toán tổng quát, và đưa ra một số thuật toán cải tiến để giải bài toán này. Chương 4: Bài toán luồng có chi phí cực tiểu định nghĩa bài toán luồng có chi phí cực tiểu, các điều kiện tối ưu của bài toán, các thuật giải tổng quát và một số cải tiến nhằm tối ưu hóa thời gian chạy của thuật toán. Chương 5: Bài toán phân công và bắt cặp giới thiệu 3 dạng tiêu biểu là bài toán bắt cặp lớn nhất trên đồ thị phân đôi, bài toán bắt cặp có trọng số trên đồ thị phân đôi, bài toán bắt cặp trên đồ thị tổng quát. Chương này cũng đưa ra một ví dụ và các thuật toán để giải các bài toán này. Chương 6: Luồng tổng quát tập trung vào các cấu trúc cây tăng trưởng và rừng tăng trưởng, cách xác định khả năng và luồng cho một cấu trúc rừng tăng trưởng. Chương 7: Xây dựng ứng dụng Distribution trình bày về thuật toán cơ bản để xây dựng nên chương trình, cơ sở dữ liệu, hướng dẫn sử dụng chương trình. 2 KH OA C NT T – Đ H KH TN CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ CHƯƠNG 2 : TỔNG QUAN VỀ BÀI TOÁN LUỒNG TRÊN MẠNG 2.1. Một số khái niệm Trong phần này, chúng ta liệt kê một số khái niệm cơ bản và các phép biến đổi đồ thị sẽ được sử dụng trong luận văn: 2.1.1. Đồ thị ™ Đồ thị có hướng và vô hướng. ™ Đỉnh đầu và đỉnh cuối. ™ Bậc của đỉnh. ™ Đường đi. ™ Chu trình. ™ Sự liên thông. ™ Lát cắt. ™ Cây. ™ Mạng thặng dư. 2.1.2. Các phép biến đổi đồ thị Một số phép biến đổi đồ thị được sử dụng nhằm biến đổi một đồ thị tổng quát thành một đồ thị đơn giản, nhờ đó, ta có thể áp dụng các thuật toán vào những đồ thị này. Đó là các phép biến đổi: ™ Loại bỏ chặn dưới khác 0 của cạnh. ™ Loại bỏ chặn trên của cạnh. ™ Đảo cạnh. ™ Tách nút. 3 KH OA C NT T – Đ H KH TN CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ 2.2. Các bài toán luồng trên mạng Các bài toán thuộc lớp bài toán luồng trên mạng: ™ Bài toán luồng có chi phí cực tiểu (minimum cost flow problem). ™ Bài toán đường đi ngắn nhất (shortest path problem). ™ Bài toán luồng cực đại (maximum flow problem). ™ Bài toán phân công (assignment problem). ™ Bài toán vận tải (transportation problem). ™ Bài toán lưu thông (circulation problem). ™ Bài toán luồng đa hàng hóa (multicommodity flow problem). ™ Bài toán cây khung tối tiểu (minimum spanning tree problem). ™ Bài toán cặp ghép (matching problem). 2.3. Một số ứng dụng cho bài toán luồng trên mạng Bài toán luồng trên mạng có rất nhiều ứng dụng trong thực tế. Có những bài toán ta dễ dàng nhận thấy sự hiện diện của mạng, nhưng cũng có những bài toán mạng bị che khuất bởi phát biểu của nó. Để áp dụng được các thuật toán luồng trên mạng ta phải thiết lập được mô hình mạng cho các bài toán này. Sau đây là một số ứng dụng thực tế, được trình bày theo các lớp bài toán luồng trên mạng. 2.3.1. Đường đi ngắn nhất ™ Bài toán chở hàng trên tàu. ™ Lập lịch cho tổng đài viên. ™ Xếp sách trong thư viện. ™ Bài toán đổi tiền (có thể ứng dụng với máy bán hàng tự động). 2.3.2. Luồng cực đại 2.3.2.1. Ứng dụng 1 : Luồng khả thi Bài toán luồng khả thi là bài toán xác định một luồng trên mạng thỏa mãn các ràng buộc sau : ∑ ∑ ∈ ∈ ∈∀=− }),(:{ }),(:{ )( Ajij Aijj ijij Niibxx (2.1) 4 KH OA C NT T – Đ H KH TN CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ Ajiux ijij ∈∀≤≤ ),(0 (2.2) Trong đó : 0)( =∑ ∈Ni ib Ta có thể giải bài toán luồng khả thi bằng cách tìm luồng cực đại trên một mạng G’ như sau: ta thêm vào hai nút mới, một nút nguồn s và một nút đích t. Với mỗi nút có b(i) > 0, ta thêm vào cung (s,i) với độ thông qua là b(i), và với mỗi nút b(i) có b(i) < 0, ta thêm vào cung (i,t) với độ thông qua là –b(i). Sau đó giải bài toán luồng cực đại truyền từ s đến t trên mạng này. Nếu tất cả các cung (s,i) và (j,t) đều bão hoà (nghĩa là xsi = usi và xjt = ujt ) thì bài toán có luồng khả thi, ngược lại là không có luồng khả thi. Bài toán luồng khả thi có một số ứng dụng thực tế, chẳng hạn: ứng dụng về phân phối hàng hoá. Trên một mạng lưới các hải cảng một số cảng có hàng hoá khác mà những cảng khác cần. Ta biết lượng hàng có tại các cảng, biết nhu cầu về các loại hàng hoá này cũng như biết khả năng vận chuyển tối đa trên mỗi tuyến đường. Ta cần biết liệu có thể đáp ứng được mọi nhu cầu dựa trên các nguồn cung cấp trong mạng hay không. Ứng dụng 2 : Bài toán bầu chọn đại biểu 2.3.2.2. Một thị trấn có r cư dân : R1 , R2 , …, Rr; q câu lạc bộ : C1 , C2 ,…, Cq; và p đảng phái chính trị : P1 , P2 , …, Pp. Mỗi người dân tham gia ít nhất 1 CLB và theo duy nhất một đảng. Mỗi CLB phải chọn 1 trong số các thành viên của nó làm đại diện cho hội đồng thị trấn sao cho số thành viên hội đồng của một đảng Pk không quá uk người. Bài toán đặt ra nhằm trả lời: có thể tìm đựơc một hội đồng đáp ứng được yêu cầu trên hay không? Giả sử r = 7 , q = 4 , p = 3 . Ta biểu diễn bài toán trên như sau : 5 KH OA C NT T – Đ H KH TN CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ Hình 2-1 Ri biểu diễn cho cư dân i Cj biểu diễn cho câu lạc bộ j Pk biểu diễn cho tổ chức chính trị k Cạnh (Ci, Rj) cho biết cư dân Rj là thành viên của câu lạc bộ Cj. Cạnh (Rj, Pk) cho biết cư dân Rj tham gia đảng Pk. Cạnh (Pk, t) có trọng lượng là uk đơn vị . Các cạnh còn lại có trọng lượng 1 đơn vị . Bài toán trên giải bằng cách giải bài toán luồng cực đại từ đỉnh s đến đỉnh t. Nếu luồng cực đại có giá trị bằng q thì ta có lời giải tối ưu . 2.3.3. Luồng có chi phí cực tiểu Ứng dụng của bài toán luồng có chi phí cực tiểu là bài toán giao hàng từ một nhà phân phối đến các đại lý sẽ được mô tả chi tiết trong phần chương trình ứng dụng. 6 KH OA C NT T – Đ H KH TN CHƯƠNG 2: TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ 2.3.4. Phân công và xếp cặp Trong một số trường hợp, chúng ta muốn phân bổ con người với các công việc, phòng ở hoặc với một người khác. Mỗi sự phân công này đều được đánh giá mức độ hợp lý và chúng ta mong muốn phân công sao cho đạt được mức đánh giá cao nhất. Sau đây là một số ứng dụng về phân công nhân sự. Ví dụ: Một công ty cần thuê n nhân viên cho n chỗ làm dựa trên các cuộc kiểm tra về khả năng , điểm tốt nghiệp và thư giới thiệu. Dùng chỉ số uij biểu diễn sự phân công nhân viên i vào công việc j. Giá trị của uij là sự đánh giá cho sự phân công này. Mục tiêu của chúng ta là xác định một cách phân công sao cho tổng chỉ số uij là lớn nhất. Một huấn luyện viên bơi lội phải lựa chọn từ 8 vận động viên xuất sắc nhất một đội bơi tiếp sức gồm 4 người. Mỗi người sẽ bơi một kiểu (bơi sấp, bơi ngửa, bơi bướm, bơi tự do). Huấn luyện viên biết rõ thời gian cho mỗi vận động viên thực hiện kiểu bơi của mình. Vấn đề đặt ra là phải tìm ra một đội với các vận động viên và thứ tự bơi phù hợp sao cho tổng thời gian tiếp sức giữa hai kiểu bơi là ít nhất. Nhận thấy bài toán phân công này có |N1|>|N2|. Tuy nhiên, chúng ta có thể thêm vào một số các nút giả nhằm làm cho |N1| = |N2| . 2.4. Tóm tắt chương 2 Trong chương 2, chúng em liệt kê một số khái niệm, và một số phép biến đổi đồ thị mà chúng em sẽ dùng trong luận văn này. Ngoài ra, chúng em cũng mô tả sơ lược về một số ứng dụng của bài toán luồng trên mạng trong thực tế. Các thuật toán để giải các bài toán này sẽ được chúng em trình bày trong các chương sau. 7 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI CHƯƠNG 3 : LUỒNG CỰC ĐẠI 3.1. Định nghĩa và ký hiệu Cho đồ thị G = (N,A) có độ thông qua của mỗi cạnh uij ≥ 0. Đặt U = max {uij: (i. j) ∈ A}. A(i) là tập các cạnh kề với nút i. G có chứa 2 nút đặc biệt: nút nguồn s và nút đích t. Vấn đề đặt ra là xác định luồng cực đại từ nút nguồn s đến nút đích t thỏa độ thông qua của các cạnh và ràng buộc cân bằng khối lượng của từng nút. Ta có thể phát biểu bài toán như sau: Cực đại giá trị v thỏa mãn: ⎪⎭ ⎪⎫ ⎪⎩ ⎪⎨⎧ v for i=s 0 for all i ∈ -v for i - t N -{s and t}=− ∑∑ ∈∈ }),(:{}),(:{ Aijj ji Ajij ij xx (3.1) 0≤xij≤uij (i,j)∀ ∈ A (3.2) Chúng ta gọi vectơ x = {xij} thỏa mãn (3.1) và (3.2) là một luồng và giá trị tương ứng của v là giá trị luồng. Không mất tính tổng quát, chúng ta sẽ chỉ xem xét bài toán luồng cực đại thỏa mãn các điều kiện sau (vì mọi bài toán luồng cực đại đều có thể được biến đổi để thỏa các điều kiện này): 1) Đồ thị liên thông. 2) Trọng lượng cạnh là số nguyên không âm. 3) Đồ thị không chứa đường đi có hướng từ đỉnh s đến đỉnh t gồm toàn các cung có độ thông qua không xác định. 4) Nếu (i,j)∈A thì (j,i)∈A. 5) Đồ thị không chứa cạnh song song. 3.2. Luồng và lát cắt Trước khi nêu ra các thuật toán giải quyết các bài toán luồng trên mạng, ta đưa ra một số khái niệm: 8 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI 3.2.1. Mạng thặng dư Khái niệm mạng thặng dư sẽ đóng vai trò trung tâm trong quá trình xây dựng các thuật toán tìm luồng cực đại mà chúng ta sẽ đề cập. Giả sử có 1 luồng x, độ thông qua thặng dư rij của 1 cung (i,j) bất kỳ là giá trị luồng tối đa có thể gửi từ nút i đến nút j thông qua cung (i,j) và cung (j,i). Khả năng thông qua thặng dư rij có 2 thành phần: 6) uij - xij là khả năng thông qua còn chưa dùng của cung (i,j). 7) giá trị luồng hiện hành xij trên cung (i,j) và ta có thể loại bỏ để tăng luồng từ nút i đến nút j. Như vậy, rij = uij - xij + xji. Ta gọi mạng G(x) chứa các cung với độ thông qua thặng dư không âm rij (ứng với luồng x) là mạng thặng dư. Hình 3-1 Mô tả mạng thặng dư 3.2.2. Lát cắt s-t Lát cắt là một phân hoạch chia tập nút N thành 2 tập con S và S = N - S Ký hiệu: [S, S ]. Mỗi lát cắt là một tập các cạnh, mỗi cạnh có 1 nút thuộc tập S, nút còn lại thuộc tập S . Lát cắt s-t: là lát cắt có s∈ S và t ∈ S . 9 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Ta gọi cung (i,j) với i∈S và j ∈ S là cung tới;cung (i,j) với j∈S và i∈ S là cung lùi của lát cắt [S, S ]. 3 Hình 3-2 Ví dụ về một lát cắt s – t Giả sử (S, S ) là tập hợp các cung tới và ( S , S) là tập hợp các cung lùi thì với lát cắt của hình 3.2, ta có (S, S ) = {(2,4), (3,6)} và ( S , S) ={(5,2), (5,3)}. Độ thông qua của lát cắt s-t [S, S ] được ký hiệu là: u[S, S ] là tổng các độ thông qua của các cung tới trong lát cắt. u[S, S ] = ∑ ∈ ),(),( SSji iju Như vậy độ thông qua của một lát cắt s-t là chặn trên của giá trị luồng tối đa ta có thể gửi từ các nút trong S đến các nút trong S . Lát cắt tối thiểu là lát cắt s-t có độ thông qua nhỏ nhất. 3.2.3. Độ thông qua thặng dư của một lát cắt s-t Độ thông qua thặng dư của một lát cắt s-t [S, S ] là tổng các độ thông qua thặng dư của các cung tới trong lát cắt r[S, S ] = ∑ ∈ ),(),( SSji ijr (3.3) 3.2.4. Luồng qua một lát cắt s-t Ta có một số tính chất quan trọng sau: 10 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Tính chất 3.1. Giá trị của một luồng bất kỳ nhỏ hơn hay bằng khả năng thông qua của mọi lát cắt trong mạng. [ ]SSuuv SSji ij , ),(),( =≤ ∑ ∈ (3.4) Như vậy nếu ta phát hiện ra một luồng x mà giá trị của nó bằng khả năng thông qua của một lát cắt [S, S ] nào đó thì x chính là luồng cực đại và lát cắt [S, S ] chính là lát cắt tối thiểu. Tính chất 3.2 Với mọi luồng có giá trị x trong mạng, lượng luồng có thể gửi thêm từ s đền t luôn nhỏ hơn độ thông qua thặng dư của một lát cắt s-t bất kỳ. 3.3. Thuật toán đường tăng trưởng Đây chính là thuật toán cơ bản nhất để giải bài toán luồng cực đại. Ta gọi một đường đi từ nút nguồn s đến nút đích t là một đường tăng trưởng. Gọi độ thông qua thặng dư của một đường tăng trưởng là độ thông qua thặng dư nhỏ nhất của các cung trong con đường này. 1 2 4 3 1 1 5 1 3 2 Hình 3-3 Ví dụ về một mạng tăng trưởng Ví dụ trong mạng tăng trưởng trên chứa duy nhất một đường tăng trưởng: 1-3-2-4 và độ thông qua thặng dư của nó là min{1,2,1} = 1. Như vậy độ thông qua thặng dư của một đường tăng trưởng luôn luôn dương Vì vậy, nếu mạng thặng dư chứa một đường tăng trưởng thì ta có thể tăng giá trị luồng gửi từ s đến t trong mạng. Thuật toán đường tăng trưởng dựa trên cơ sở nhận xét vừa nêu. Thuật toán hoạt động theo quy trình lặp đi lặp lại việc tìm một đường tăng trưởng và tăng giá trị luồng gửi từ s đến t dọc theo đường này. 11 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Thuật toán đường tăng trưởng begin x:= 0 ; while (G(x) chứa một đường đi có hướng từ s đến t ) do begin Xác định đường tăng trưởng P từ s đến t ; δ := min {rij: (i,j) ∈ P} ; Tăng giá trị luồng thêm δ dọc theo P và cập nhật lại G(x) ; end; end; 3.4. Thuật toán gán nhãn và định lý lát cắt tối thiểu Trong mục này, chúng ta sẽ khảo sát thuật toán đường tăng trưởng một cách chi tiết hơn. Trong mục trước, khi khảo sát thuật toán này, chúng ta đã bỏ qua một số chi tiết quan trọng, chẳng hạn như: làm sao để tìm ra 1 đường tăng trưởng hay khẳng định luồng tăng trưởng không tồn tại trong mạng? Liệu thuật toán có dừng sau 1 số lần lặp hữu hạn hay không và dừng ở đâu, liệu thuật toán có thật sự tìm ra được luồng cực đại như mong muốn hay không? Chúng ta sẽ xem xét các vấn đề trên với 1 phiên bản cài đặt của thuật toán tăng trưởng được biết dưới tên gọi: thuật toán gán nhãn. Thuật toán gán nhãn sử dụng một kỹ thuật tìm kiếm (theo chiều rộng hay chiều sâu) để tìm một đường đi từ nút nguồn s đến nút đích t trong mạng G(x). Thuật toán sẽ lần đến tất cả các nút có thể đến từ nút nguồn theo một đường đi có hướng. Tại mỗi bước, thuật toán phân hoạch tập các nút của mạng thành hai nhóm: nhóm các nút được gán nhãn và nhóm các nút không được gán nhãn. Các nút được gán nhãn là các nút mà tại thời điểm đang xét, thuật toán phát hiện ra ít nhất một đường đi nối từ nút nguồn đến nút này. Những nút còn lại là những nút không được gán nhãn. Thuật toán lặp đi lặp lại quá trình chọn một nút có nhãn và quét theo danh sách các nút kề với nó để gán nhãn cho các nút chưa được gán nhãn. Quá trình được tiếp tục cho đến khi nút t được gán nhãn. Khi đó, ta tìm được một đường đi từ s đến t. Đây chính là một đường tăng trưởng. Gửi một lượng luồng tối 12 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI đa có thể có dọc theo con đường này ta sẽ tăng được giá trị x trong mạng ban đầu. Với mạng G(x) mới, ta tiếp tục quá trình gán nhãn và tăng luồng cho đến khi không thể gán nhãn cho nút t. Thuật toán dừng tại đây. Dưới đây là thuật toán gán nhãn: Thuật toán gán nhãn begin repeat Đặt mọi nút ở trạng thái không gán nhãn; Với mọi nút j∈N, đặt prev(j) = 0; Gán nhãn cho nút s và đặt LIST = {s}; while (LIST {} và t chưa có nhãn) do ≠ begin Lấy 1 nút từ LIST ; For(mỗi cung (i,j) trong mạng thặng dư )do if(rij > 0 và nút j chưa có nhãn)then begin Đặt prev(j) = i ; Gán nhãn cho j ; Thêm j vào LIST ; end; end; if (t được gán nhãn)then Tăng luồng ; until (t không có nhãn); end; Hàm Tăng luồng begin dùng giá trị nhãn prev() để tìm đường tăng trưởng P từ s đến t ; δ := min {rij: (i,j) ∈ P} ; Tăng δ đơn vị luồng dọc theo P và cập nhật độ thông qua thặng dư trong mạng thặng dư ; end; 13 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Định lý 3.3: định lý Ford – Fullkerson về lát cắt nhỏ nhất Giá trị cực đạicủa luồng gửi từ nút nguồn s đến nút đích t trên mạng bằng khả năng thông qua của lát cắt nhỏ nhất. Định lý 3.4: định lý về đường tăng trưởng Một luồng x* là luồng cực đại khi và chỉ khi mạng thặng dư G(x*) không chứa đường tăng trưởng. Định lý 3.5: định lý về tính nguyên Nếu khả năng thông qua của tất cả các cung trên mạng đều là số nguyên thì luồng cực đại có giá trị nguyên. 3.4.1. Độ phức tạp của thuật toán gán nhãn Ta sẽ khảo sát độ phức tạp của thuật toán trong trường hợp xấu nhất. Nhắc lại, sau mỗi lần lặp, ngoại trừ lần sau cùng, thuật toán thực hiện một lần tăng luồng. Mỗi lần tăng luồng tốn chi phí 0(m). Vấn đề còn lại là xác định tối đa có bao nhiêu lần tăng luồng. Nếu tất cả các cung đều có độ thông qua nguyên ≤U, độ thông qua của lát cắt (s,N-{s} ) không vượt quá nU. Như vậy, giá trị luồng cực đại không quá nU. Từ đây suy ra độ phức tạp của thuật toán là 0(nmU). 3.4.2. Hạn chế của thuật toán gán nhãn Thuật toán gán nhãn có thể là thuật toán đơn giản nhất dùng để giải bài toán luồng cực đại trên mạng. Trong thực nghiệm, thuật toán họat động đủ tốt. Tuy nhiên trường hợp xấu nhất của thuật toán sẽ không thỏa mãn yêu cầu về tốc độ khi U quá lớn. Ví dụ, nếu U=2n, chi phí thuật toán sẽ là hàm mũ của số nút trên mạng. Hơn nữa, thuật toán sẽ thực hiện rất nhiều vòng lặp. Hạn chế thứ hai của thuật toán là nếu độ thông qua của các cung là số vô tỷ, thuật toán có thể không dừng. Vì vậy, để đảm bảo tính hiệu quả của thuật toán, ta cần chọn đường tăng trưởng một cách cẩn thận. Hạn chế thứ ba là sự lãng phí. Trong mỗi bước lặp, ta thực hiện quá trình gán nhãn các nút lại từ đầu, trong khi trong nhiều trường hợp, thông tin về nhãn 14 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI của bước trước vẫn còn giá trị ở lần lặp sau. Việc giữ lại các thông tin này sẽ làm giảm đáng kể chi phí thực hiện thuật toán. 3.5. Luồng có chặn dưới Trong phần này chúng ta sẽ khảo sát bài toán luồng cực đại trên mạng với các cung có khả năng thông qua tối thiểu lớn hơn không. Bài toán có thể phát biểu một cách hình thức như sau: Cực đại hóa v thỏa ràng buộc: ⎪⎭ ⎪⎫ ⎪⎩ ⎪⎨⎧ v for i=s 0 for all i ∈ -v for i - t N -{s and t}=− ∑∑ ∈∈ }),(:{}),(:{ Aijj ji Ajij ij xx 0≤ xij≤ uij (i,j)∀ ∈ A Trong mục trước, ta đã khảo sát trường hợp đặc biệt của bài toán này khi tất cả lij = 0. Trong khi bài toán luồng trên mạng có chặn dưới bằng không luôn có lời giải thì bài toán luồng trên mạng lớn hơn không có thể không có lời giải thích hợp. Ví dụ: Hình 3-4: Bài toán luồng cực đại không có luồng tương thích Bài toán trên không có lời giải vì cung (1,2) phải mang tối thiểu đơn vị luồng trong khi cung (2,3) chỉ mang được tối đa 4 đơn vị luồng. Như vậy, ta không thể thỏa mãn cân bằng vật chất tại nút 2. Như vậy, mọi bài toán tìm luồng cực đại có chặn dưới phải giải quyết hai vấn đề: ™ Xác định xem bài toán có tồn tại luồng khả thi không. ™ Nếu có thì thiết lập luồng cực đại. 15 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Chính vì vậy không có gì ngạc nhiên khi hầu hết các thuật toán bao gồm hai giai đoạn. Giai đoạn thứ nhất kiểm tra sự tồn tại của luồng khả thi và trong giai đoạn hai, nếu tồn tại sẽ biến đổi luồng khả thi thành luồng cực đại. Phần tiếp theo sẽ cho chúng ta thấy rằng mỗi giai đoạn của thuật toán sẽ tương đương với một lần giải bài toán luồng cực đại không có chặn dưới. Nghĩa là để giải bài toán luồng trên mạng có chặn dưới, ta cần giải hai bài toán luồng trên mạng không có chặn dưới. Để thuận tiện, chúng ta sẽ khảo sát giai đoạn hai trước. 3.5.1. Xác định luồng cực đại Giả sử ta có một luồng khả thi x trên mạng.Ta có thể hiệu chỉnh một thuật toán tìm luồng cực đại trên mạng không có chặn dưới bất kỳ để tìm luồng cực đại trên mạng của bài toán ta đang xét. Ta chỉ cần thực hiện các hiệu chỉnh sau: định nghĩa độ thông qua thặng dư của cung (i,j) là rij = (uij - xij) + (xji - lji) hạng thức đầu tiên trong biểu thức thể hiện khả năng thông qua tối đa của luồng chạy từ i đến j thông qua cung (i,j) và hạng thức thứ hai thể hiện khả năng tăng tối đa của luồng chạy từ i đến j thông qua việc giảm luồng trên cung (j,i). Lưu ý x là luồng khả thi nên rij 0. Do thuật toán tìm luồng cực đại trình bày trong phần trước chỉ làm việc trên mạng thặng dư nên ta có thể dùng nó để thiết lập luồng cực đại trên mạng. Thuật toán này dừng khi ta nhận được giá trị luồng thặng dư tối ưu. Từ giá trị luồng thặng dư này,ta có thể tính ra luồng cực đại. ≥ Định lý 3.6: Định lý lát cắt nhỏ nhất mở rộng Nếu khả năng thông qua của một lát cắt s-t [S,S ] trên mạng có cả chặn trện và chặn dưới định nghĩa như sau: ∑∑ ∈∈ −= ),(),(),(),( SSji ij SSji ij xxv thì luồng cực đại gửi từ s đến t sẽ có giá trị bằng khả năng thông qua cuả lát cắt nhỏ nhất. 3.5.2. Xây dựng luồng khả thi Bây giờ việc còn lại là xác định một luồng khả thi trên mạng. Trước tiên, chúng ta sẽ chuyển đổi bài toán luồng cực đại sang bài toán lưu thông bằng cách thêm vào mạng cung (t,s) với khả năng thông qua vô hạn ∞ . Cung này sẽ chuyển tải toàn bộ luồng gửi từ s đến t quay ngược trở lại s. Như vậy trong bài toán lưu 16 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI thông, luồng đi ra từ một nút bất kỳ (kể cả nút s và t) bằng đúng luồng vào nó. Dễ dàng thấy rằng, bài toán luồng cực đại có luồng khả thi khi và chỉ khi bài toán lưu thông tương ứng có luồng khả thi. Bây giờ, ta sẽ tìm điều kiện cần và đủ để bài toán lưu thông trên mạng có chặn trên và chặn dưới có luồng khả thi. Bài toán xác định luồng khả thi của bài toán lưu thông là bài toán tìm một luồng x thỏa mãn các ràng buộc sau: ∑ ∑ ∈ ∈ =− }),(:{ }),(:{ 0 Ajij Aijj jiij xx Ni∈∀ (3.10a) lij ≤xij ≤uij Aji ∈∀ ),( (3.10b) Bằng cách thay xij=x’ij+lij ta nhận được bài toán tương đương sau: ∑ ∑ ∈ ∈ =− }),(:{ }),(:{ )(' Ajij Aijj jiij ibxx Ni∈∀ (3.11a) lij ≤x’ij ≤uij-lij Aji ∈∀ ),( (3.11b) Với giá trị cung cầu b(i) tại mỗi nút được xác định bởi công thức: b(i) = ∑ ∑ ∈ ∈ =− }),(:{ }),(:{ 0 Ajij Aijj jiij ll Ni∈∀ (3.12) Nhận xét rằng =0 do mỗi l∑ ∈Ai ib )( ij xuất hiện hai lần trong biểu thức này, một lần với dấu cộng, một lần với dấu trừ. Như vậy, bài toán lưu thông tương đương với việc tìm luồng x’ thỏa mãn ràng buộc (3.11). Lưu ý rằng, bài toán này chính là bài toán luồng khả thi chúng ta đã khảo sát ở phần trước. Như đã biết, để giải bài toán luồng khả thi ta cần giải bài toán luồng cực đại trên mạng không có chặn dưới. Qua đó hoặc ta xác định được một lời giải thỏa (3.11) hoặc khẳng định được rằng bài toán không có lời giải phù hợp. Nếu x’ij là luồng khả thi của (3.11) thì xij là luồng khả thi của (3.10). 3.5.3. Mô tả đặc điểm của luồng khả thi trên mạng lưu thông Ta sẽ khảo sát sự tồn tại luồng khả thi của bài toán lưu thông. Gọi S là một tập hợp nút bất kỳ trên mạng. Ta có: ∑ ∑ ∈ ∈ =− }),(:{ }),(:{ 0 Ajij Aijj jiij xx (3.13) 17 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Do lij ≤xij ≤uij nên từ (3.13) suy ra: ∑ ∑ ∈ ∈ ≤ }),(:{ }),(:{Ajij Aijj jiij ul (3.14) Biểu thức (3.14) chính là điều kiện cần để tồn tại luồng khả thi. Nó có nghĩa là lượng luồng tối đa có thể gửi ra từ tập S phải lớn hơn lượng luồng tối thiểu có thể nhận bởi tập S. Ta sẽ chứng minh (3.14) là điều kiện đủ. Bắt đầu từ một luồng x thỏa các ràng buộc của bài toán ngoại trừ một số vi phạm về chặn dưới. Ta sẽ từng bước biến đổi x thành luồng khả thi hoặc phát hiện ra rằng một nút nào đó trong S vi phạm (3.14). Ứng với luồng x, ta gọi một cung (i,j) là không tương thích nếu xij <lij và tương thích nếu ngược lại. Chọn một cung (p,q) không tương thích và biến nó thành tương thích bằng cách tăng luồng trên nó. Do điều kiện cân bằng vật chất tại các nút, để tăng luồng trên cung (p,q), ta phải tăng luồng dọc theo một hay nhiều chu trình chứa (p,q). Ta định nghĩa mạng thặng dư như trước đây, ngoại trừ khả năng thông qua thặng dư rij được đặt bằng uij - xij. Mọi chu trình tăng trưởng chứa cung(p,q) như một cung tới phải chứa một đường đi có hướng trong G(x) cộng với cung (p,q). Ta có thể dùng thuật toán gán nhãn để tìm một đường đi từ p đến q. Ta áp dụng thủ tục này trên mỗi cung không tương thích một lần. Sau mỗi bước, tính không tương thích của các cung sẽ giảm dần. Lặp lại quá trình này, hoặc ta sẽ nhận được một luồng khả thi, hoặc thuật toán gán nhãn không tìm ra đường đi từ p đến q đối với một cung không tương thích (p,q) nào đó.Trong trường hợp này, bài toán của chúng ta sẽ không tìm ra được lời giải. Thật vậy, gọi S là tập nút đã được gán nhãn trong lần áp dụng cuối cùng của thuật toán gán nhãn. Rõ ràng, q∈S và p∈ S = N-S. Do thuật toán gán nhãn không thể gán nhãn cho các nút thuộc S nên mọi cung (i,j)hướng từ S đến S có khả năng thông qua bằng 0. Do đó xij = uij (i,j)∈(S,∀ S ) và xij u≤ ij (i,j)∀ ∈(S,S ). Ta cũng có (p,q)∈(S,S ) và xpq ≤ upq. Thay các giá trị này vào (3.13) ta có: ∑ ∑ ∈ ∈ > }),(:{ }),(:{Ajij Aijj jiij ul 18 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Kết quả này mâu thuẫn với điều kiện (3.14) Như vậy (3.14) là điều kiện đủ cho sự tồn tại của luồng khả thi. Từ đây, ta có định lý: Định lý 3.7: điều kiện tồn tại luồng khả thi trên mạng lưu thông Trên mạng lưu thông có chặn dưới dương tồn tại luồng khả thi khi và chỉ khi tập đỉnh S thỏa mãn điều kiện: ∑ ∑ ∈ ∈ ≤ }),(:{ }),(:{Ajij Aijj jiij ul Định lý 3.8 Bài toán luồng khả thi có lời giải khi và chỉ khi với mọi tập con các nút S, b(S) – u[ S,S ] 0 trong đó b(S) = ≤ ∑ ∈Si ib )( . 3.6. Cải tiến thuật toán đường tăng trưởng Trong phần này, chúng ta sẽ xem xét một số phương pháp nhằm cải thiện tốc độ thực thi của thuật toán đường tăng trưởng. Những thuật toán đã cải tiến này có độ phức tạp đa thức. Chúng ta có thể giảm số lần tăng luồng (augmentation) hoặc khử chúng bằng cách nào? Trong phần này chúng ta sẽ xét 3 phương pháp cơ bản sau: 1) Tăng một lượng luồng “lớn”. 2) Sử dụng các chiến lược kết hợp để giới hạn các loại đường đi tăng trưởng (augmenting path) mà chúng ta có thể sử dụng ở mỗi bước. 3) Nới lỏng các ràng buộc cân bằng khối lượng ở các bước trung gian của thuật toán, và vì thế sẽ không đòi hỏi rằng mỗi lần thay đổi luồng phải là một lần tăng luồng bắt đầu ở đỉnh nguồn và kết thúc ở đỉnh đích. Bây giờ chúng ta hãy lần lượt xem xét các phương pháp này. Chúng ta đã thấy ở phần trên, thuật toán đường đi tăng trưởng tổng quát có thể chậm vì chúng thực hiện một số lớn các lần tăng luồng, mỗi lần với một lượng luồng nhỏ. Quan sát này cho ta một chiến lược tự nhiên để cải tiến thuật toán đường đi tăng trưởng: tăng luồng dọc theo một đường đi có độ thông qua thặng dư lớn thì số lần tăng 19 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI luồng sẽ giảm bớt. Chúng ta sẽ xây dựng một thuật toán dựa trên chiến lược này, đó là thuật toán tỉ lệ với độ thông qua, sẽ được khảo sát ở phần sau. Một chiến lược khác có thể thực thi và cải tiến thuật toán đường đi tăng trưởng là phát triển các phương pháp độc lập với dữ liệu độ thông qua của cung. Một trong những hướng tiếp cận này là bằng cách nào đó giới hạn các lựa chọn đường đi tăng trưởng. Chúng ta có thể tăng luồng theo một “đường đi ngắn nhất” từ nguồn đến đích, với định nghĩa đường đi ngắn nhất là một đường đi có hướng trong đồ thị thặng dư có ít cung nhất. Chiến lược thứ 3 là tìm “đường đi ngắn nhất” như trong thuật toán đường đi tăng trưởng ngắn nhất, nhưng không gửi luồng theo các đường đi từ nguồn tới đích. Thay cho điều đó, chúng gửi các luồng trên các cung riêng lẻ. Chúng ta sẽ minh họa chiến lược này bằng thuật toán đẩy luồng được trình bày ở phần sau. Khái niệm về các nhãn khoảng cách là một phần quan trọng để thực thi các thuật toán đường đi tăng trưởng ngắn nhất và đẩy luồng. Vì vậy trước khi mô tả các thuật toán cải tiến, chúng ta bắt đầu với định nghĩa về nhãn khoảng cách. 3.6.1. Các nhãn khoảng cách Một hàm khoảng cách d: N Z→ + {0} đối với độ thông qua thặng dư r∪ ij là một hàm từ tập các đỉnh vào tập các số nguyên không âm. Chúng ta nói một hàm khoảng cách là hợp lệ (valid) đối với một luồng x nếu nó thỏa mãn hai điều kiện sau: d(t) = 0; (3.15) d(i) d(j) + 1 với mọi cung (i, j) trong đồ thị thặng dư G(x). (3.16) ≤ Chúng ta nói d(i) là nhãn khoảng cách của đỉnh i và điều kiện (3.15) và (3.16) là các điều kiện hợp lệ. Các tính chất sau cho thấy tại sao các nhãn khoảng cách có thể được sử dụng trong việc thiết kế các thuật toán luồng trên đồ thị. 20 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Tính chất 3.9 Nếu các nhãn khoảng cách là hợp lệ thì nhãn khoảng cách d(i) là chặn dưới của độ dài đường đi (có hướng) ngắn nhất từ đỉnh i đến đỉnh t trong đồ thị thặng dư. Tính chất 3.10 Nếu d(s) ≥ n thì đồ thị thặng dư không chứa đường đi có hướng từ đỉnh nguồn đến đỉnh đích. Chúng ta nói rằng các nhãn khoảng cách là chính xác nếu với mỗi đỉnh i, d(i) bằng độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh t trong đồ thị thặng dư. Chúng ta có thể xác định các nhãn khoảng cách chính xác cho tất cả các đỉnh trong thời gian O(m) bằng thuật toán tìm kiếm theo chiều rộng lùi trên đồ thị bắt đầu từ đỉnh đích. 3.6.2. Thuật toán tỉ lệ với độ thông qua Thuật toán này dựa vào ý tưởng tăng một lượng luồng lớn nhằm giảm số lần tăng luồng. Tuy nhiên ở đây, chúng ta chỉ tăng luồng theo một đường đi có độ thông qua thặng dư đủ lớn thay vì một đường đi có độ thông qua tăng trưởng lớn nhất bởi vì chúng ta có thể dễ dàng có được đường đi này khá dễ dàng – trong thời gian O(m). Để định nghĩa thuật toán tỉ lệ với độ thông qua, ta giới thiệu một tham số ∆, và với một luồng cho trước x, đồ thị thặng dư ∆ được định nghĩa là một đồ thị chứa các cung có độ thông qua thặng dư ít nhất là ∆. Gọi G(x, ∆) là đồ thị thặng dư ∆. Chú ý rằng G(x,1) = G(x) và G(x, ∆) là đồ thị con của G(x). Hình 3.7 minh họa cho định nghĩa này. Hình 3.7(a) cho thấy đồ thị thặng dư G(x) và hình 3.7(b) cho thấy đồ thị thặng dư ∆ G(x, ∆) với ∆ = 8. 21 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI i j rij 1 2 4 3 5 10 12 4 8 13 15 6 1 2 4 3 5 10 8 13 15 7 12 (a) (b) (a)Đồ thị thặng dư G(x); (b) Đồ thị thặng dư G(x, ) với = 8∆ ∆ Hình 3-5 Minh họa đồ thị thặng dư Thuật toán Đo độ thông qua begin x := 0; ∆ := 2[log U] ; while ∆ ≥ 1 do begin while G(x, ∆) chứa một đường đi từ đỉnh s đến đỉnh t do begin xác định một đường đi P trong G(x, ∆); δ := min{rij : (i, j) ∈ P}; tăng δ đơn vị luồng trên P và cập nhật G(x, ∆); end; ∆ := ∆/2; end; end; Thuật toán đo độ thông qua giải bài toán luồng cực đại trong O(m log U) lần tăng luồng và chạy trong thời gian O(m2 log U). 22 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI 3.6.3. Thuật toán đường đi tăng trưởng ngắn nhất Thuật toán đường đi tăng trưởng ngắn nhất luôn tăng luồng theo đường đi ngắn nhất từ nguồn đến đích trong đồ thị thặng dư. Một phương pháp tự nhiên cho bài toán này là tìm đường đi ngắn nhất trên đồ thị thặng dư bằng thuật toán tìm kiếm theo chiều rộng. Tuy nhiên, phương pháp này tốn quá nhiều thời gian. Ta có thể cải tiến nó bằng cách khai thác tính chất khoảng cách nhỏ nhất từ đỉnh i bất kỳ đến đỉnh đích t là không giảm trong tất cả các lần tăng luồng. Thuật toán đường đi tăng trưởng ngắn nhất thực thi bằng cách tăng luồng theo các đường đi có thể chấp nhận. Nó tạo ra một đường đi có thể chấp nhận bằng cách thêm từng cung tại mỗi thời điểm. Thuật toán chứa một đường đi có thể chấp nhận bộ phận (nghĩa là đường đi từ đỉnh s đến đỉnh i chỉ chứa các cung có thể chấp nhận) và thực hiện hoạt động tiến tới hoặc quay lui từ đỉnh cuối cùng trên đường đi này, ta gọi điểm này là điểm hiện hành. Nếu điểm hiện hành i có (gắn với) cung có thể chấp nhận (i, j), chúng ta thực thi một hành động tiến tới và thêm cung (i, j) vào đường đi có thể chấp nhận bộ phận; ngược lại, chúng ta sẽ thực thi một hành động quay lui và quay lại cung trước đó. Ta lặp lại các hành động này đến khi đường đi có thể chấp nhận bộ phận gặp đỉnh đích và khi đó chúng ta sẽ thực hiện quá trình tăng luồng. Chúng ta lặp lại quá trình này đến khi luồng đạt giá trị cực đại. Thuật toán đường đi tăng trưởng ngắn nhất; begin x := 0; xác định các nhãn khoảng cách chính xác d(i); i := s; while d(s) < n do begin if i có một cung có thể chấp nhận then begin advance(i); if i = t then augment và đặt i = s end 23 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI else retreat(i) end; end; Hàm Tiến tới (i) begin cho (i, j) là cung có thể chấp nhận trong A(i); pred(j) := i và i := j; end; Hàm Quay lui (i) begin d(i) := min{d(j) + 1: (i, j) ∈ A(i) và rij > 0}; if i s then i := pred(i); ≠ end; Hàm Tăng luồng begin dùng chỉ số chỉ đỉnh trước pred(i) để xác định đường đi tăng trưởng P từ nguồn đến đích. δ := min{rij : (i, j) ∈ P}; tăngδ đơn vị luồng theo đường đi P; end; Thuật toán đường đi tăng trưởng ngắn nhất chạy trong thời gian O(n2m). Sự cải tiến trong thực tế Thuật toán đường đi tăng trưởng ngắn nhất kết thúc khi d(s) n. Thực tế cho thấy thuật toán này tốn quá nhiều thời gian để gán lại nhãn cho các đỉnh và phần lớn thời gian cho việc này được thực hiện sau khi đã xác định được giá trị luồng cực đại. Điều này xảy ra vì thuật toán không biết rằng nó đã tìm ra được giá ≥ 24 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI trị luồng cực đại. Chúng ta sẽ đưa ra một kỹ thuật có khả năng phát hiện lát cắt nhỏ nhất và vì thế xác định được sự hiện diện của luồng cực đại trước khi nhãn của đỉnh s thỏa điều kiện d(s) ≥ n. Để thực thi phương pháp này, chúng ta dùng một mảng numb có n phần tử, với chỉ số từ 0 đến n – 1. Giá trị numb(k) là số lượng đỉnh có nhãn khoảng cách bằng k. Thuật toán khởi tạo mảng này bằng cách tính các nhãn khoảng cách bằng thuật toán tìm kiếm theo chiều rộng. Các giá trị dương trong mảng numb liên tiếp nhau (nghĩa là numb(0), numb(1), numb(2), …, numb(l) là các số dương đến chỉ số l và tất cả các mục còn lại sẽ là 0). Do đó khi thuật toán tăng nhãn khoảng cách của một đỉnh từ k1 đến k2, nó trừ 1 từ numb(k1) và cộng 1 vào numb(k2), và kiểm tra xem numb(k1) có bằng 0 hay không. Nếu numb(k1) = 0, thuật toán kết thúc. 3.6.4. Thuật toán đẩy luồng Thuật toán này tổng quát hơn, mạnh hơn, và linh động hơn các thuật toán đường đi tăng trưởng. Như đã thấy ở phần trên, các thuật toán đường đi tăng trưởng tăng luồng theo các đường đi, hoạt động cơ bản này có thể được tách ra thành những hoạt động cơ bản hơn là gửi luồng theo các cung riêng lẻ. Theo cách đó, gửi một luồngδ đơn vị theo một đường đi gồm k cung được tách ra thành k hoạt động cơ bản là gửiδ đơn vị luồng theo từng cung trên đường đi. Chúng ta gọi mỗi thao tác cơ bản này là một lần đẩy. Thuật toán đẩy luồng đẩy luồng theo các cung riêng lẻ thay vì trên một đường đi tăng trưởng do đó nó không thỏa các ràng buộc khối lượng ở các bước trung gian. Thực tế, các thuật toán này cho phép luồng đi vào một đỉnh vượt quá luồng đi ra đỉnh đó. Như vậy , ta có hàm x: A R thỏa ràng buộc giới hạn và: → x∑ ∈ }),(:{ Aijj ji - x∑ ∈ }),( ij 0 ≥ ∀ i ∈ N – {s,t}. :{ j Aji Với luồng cho trước x, ta định nghĩa sự vượt quá của mỗi đỉnh i ∈ N như sau: e(i) = x∑ ∈ }),(:{ Aijj ji - x∑ ∈ }),(:{ Ajij ij e(i) 0 với mọi i ∈ N – {s,t}. Hơn nữa, không có cung nào xuất phát từ đỉnh t nên e(t) 0. Vì vậy đỉnh s là đỉnh duy nhất có giá trị vượt quá của đỉnh âm. ≥ ≥ 25 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Chúng ta gọi một đỉnh có giá trị vượt quá âm là một đỉnh linh động và qui ước rằng đỉnh nguồn và đích không bao giờ là đỉnh linh động. Thao tác cơ bản của thuật toán này là chọn một đỉnh linh động và cố gắng để xóa bỏ sự vượt quá của nó bằng cách đẩy luồng đến đỉnh kề với nó. Nhưng luồng nên được gửi đến đỉnh nào? Vì chúng ta muốn gửi luồng đến đỉnh đích nên chúng ta đẩy luồng đến các đỉnh gần đích hơn. Cũng như thuật toán đường đi tăng trưởng ngắn nhất, chúng ta đo mức độ gần đích bằng các nhãn khoảng cách vì thế gửi luồng đến gần đích hơn tương đương với đẩy luồng qua các cung có thể chấp nhận. Vì vậy chúng ta chỉ gửi luồng qua các cung có thể chấp nhận. Nếu đỉnh linh động đang xét không có cung có thể chấp nhận thì chúng ta tăng nhãn khoảng cách của nó để chúng ta có thể tạo ra ít nhất một cung có thể chấp nhận. Thuật toán kết thúc khi đồ thị không chứa đỉnh linh động nào nữa. Dưới đây là các hàm và thuật toán đẩy luồng. Thủ tục Tiền thực thi; begin x := 0; tính các nhãn khoảng cách chính xác d(i); xsj := usj với mỗi cung (s, j) ∈ A(s); d(s) := n; end; Thủ tục Đẩy/Gán lại nhãn(i) begin if đồ thị chứa một cung có thể chấp nhận (i, j) then push δ := min{e(i), rij} đơn vị luồng từ đỉnh i đến đỉnh j else thay d(i) bằng min{d(j) + 1 : (i, j)∈ A(i) và rij > 0}; end; 26 KH OA C NT T – Đ H KH TN CHƯƠNG 3: LUỒNG CỰC ĐẠI Thuật toán Đẩy luồng begin Tiền thực thi; while đồ thị chứa một đỉnh linh động do begin chọn một đỉnh linh động i; Đẩy/gán lại nhãn(i); end; end; Đẩy δ đơn vị luồng từ đỉnh i đến đỉnh j sẽ giảm e(i) và rij điδ đơn vị và tăng e(j) và rji lênδ đơn vị. Chúng ta nói rằng một lần đẩyδ đơn vị luồng trên một cung (i, j) là bão hòa nếuδ = rij và ngược lại là chưa bão hòa. Một lần đẩy chưa bão hòa tại đỉnh i giảm e(i) thành 0. Chúng ta gọi quá trình tăng nhãn khoảng cách của một đỉnh là thao tác gán nhãn lại. Mục tiêu của thao tác này là để tạo ra ít nhất một cung có thể chấp nhận để thuật toán có thể thực hiện các lần đẩy tiếp theo. Thuật toán đẩy luồng chạy trong thời gian O(n2m). 3.7. Tóm tắt chương 3 Trong chương 3, chúng em tập trung vào bài toán luồng cực đại. Cách tiếp cận cơ bản mà chúng em trình bày là thuật toán gán nhãn dựa trên cơ sở là định lý về đường tăng trưởng . Do thuật toán tổng quát có một số hạn chế như: (1) thuật toán sẽ không thỏa mãn yêu cầu về tốc độ nếu độ thông qua của cung là quá lớn, (2) thuật toán sẽ không thể dừng nếu độ thông qua của các cung là số vô tỷ, (3) khi duyệt qua một vòng lặp mới thì nhãn của đỉnh sẽ bị xóa ngay cả khi những thông tin này có thể dùng được cho những lần tiếp theo. Nên chúng tôi đã đưa ra một số thuật toán cải tiến có độ phức tạp đa thức dựa trên thuật toán tổng quát ban đầu như: thuật toán tỉ lệ với độ thông qua, thuật toán đường đi tăng trưởng ngắn nhất và thuật toán đẩy luồng. Trong chương này, chúng em cũng đề cập đến một vấn đề thường gặp phải trong thực tế đó là trường hợp luồng có chặn dưới. Để giải bài toán này, chúng ta cần giải hai bài toán con là tìm luồng khả thi trong mạng, sau đó tối ưu hóa để luồng này trở thành luồng cực đại. 27 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU CHƯƠNG 4 : LUỒNG VỚI CHI PHÍ CỰC TIỂU 4.1. Giới thiệu 4.1.1. Các giả thiết Gọi G = (N, A) là một đồ thị có hướng với chi phí cij và độ thông qua uij gắn với mỗi cạnh (i, j) ∈ A. Chúng ta gắn một đỉnh i ∈ N với một số b(i) chỉ khả năng cung hoặc cầu phụ thuộc vào b(i) > 0 hay b(i) < 0. Bài toán luồng với chi phí cực tiểu có thể được phát biểu như sau: Cực tiểu hóa z(x) = c∑ ∈Aji ),( ijxij (4.1a) Thỏa mãn ∑ ∈ }),(:{ Ajij xij - x∑ ∈ }),(:{ Aijj ji = b(i) với ∀ i ∈ N (4.1b) 0 x≤ ij u≤ ij với (i, j) ∀ ∈ A (4.1c) Gọi C là chi phí lớn nhất của tất cả các cung, U là giá trị lớn nhất của bất kỳ nút cung/cầu hoặc độ thông qua xác định nào. Ta cũng giả sử chặn dưới lij đối với các luồng trên cung là 0. Chúng ta có thêm các giả thiết sau: 1) Tất cả dữ liệu (chi phí, khả năng cung/cầu, và độ thông qua) là số nguyên. 2) Đồ thị là đồ thị có hướng. 3) Khả năng cung/cầu tại các đỉnh thỏa điều kiện ∑∈Ni b(i) = 0 và bài toán luồng với chi phí cực tiểu có một giải pháp khả thi. 4) Chúng ta giả sử rằng đồ thị G chứa một đường đi có hướng không có giới hạn (nghĩa là tất cả các cung trên đường đi có độ thông qua vô hạn) giữa mọi cặp đỉnh. 5) Chi phí của tất cả các cung là không âm. 28 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU 4.1.2. Đồ thị thặng dư Đồ thị thặng dư G(x) tương ứng với luồng x được định nghĩa như sau: chúng ta thay một cung (i, j) ∈ A bằng hai cung (i, j) và (j, i). Cung (i, j) có chi phí cij và độ thông qua thặng dư rij = uij – xij, và cung (j, i) có chi phí cji = - cij và độ thông qua thặng dư rij = xij. Đồ thị thặng dư chỉ chứa các cung có độ thông qua thặng dư dương. 4.2. Các điều kiện tối ưu cho bài toán 4.2.1. Các điều kiện tối ưu về chu trình âm Định lý 4.1: Các điều kiện tối ưu về chu trình âm Một giải pháp khả thi x* là một giải pháp tối ưu của bài toán luồng với chi phí cực tiểu khi và chỉ khi thỏa mãn các điều kiện tối ưu về chu trình âm: cụ thể là đồ thị thặng dư G(x*) không chứa chu trình (có hướng) có chi phí âm. 4.2.2. Các điều kiện tối ưu về chi phí rút gọn Chúng ta có thể viết điều kiện tối ưu về đường đi ngắn nhất theo chi phí dưới dạng tương đương sau: = cdijc ij + d(i) – d(j) ≥ 0 với ∀ (i, j) ∈ A (4.3) Biểu thức này được hiểu như sau: là một “chi phí rút gọn” tối ưu đối với cung (i, j) theo nghĩa là nó tính chi phí của các cung này gắn với với các nhãn khoảng cách d(i) và d(j). Chú ý rằng với những nhãn khoảng cách tối ưu, mọi cung trong đồ thị có chi phí rút gọn không âm. Hơn nữa, vì d(j) = d(i) + c d ijc ij, nếu cung (i, j) nằm trên đường đi ngắn nhất từ đỉnh nguồn s đến các đỉnh khác thì đường đi ngắn nhất chỉ sử dụng các cung có chi phí rút gọn bằng 0. Do đó, khi chúng ta biết các khoảng cách tối ưu, bài toán sẽ dễ dàng được giải quyết: chúng ta chỉ cần tìm một đường đi từ đỉnh s đến mọi đỉnh khác mà chỉ dùng các cung có chi phí rút gọn bằng 0. Cách giải thích này gợi ra một câu hỏi tự nhiên: có một tập các điều kiện tương tự cho các bài toán luồng với chi phí cực tiểu tổng quát hơn hay không? Chúng ta gắn một số thực π (i), không giới hạn âm dương, với mỗi đỉnh i ∈ N. Chúng ta gọi π (i) là khả năng của đỉnh i. Cho một tập hợp các khả năng của 29 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU đỉnh π , chúng ta định nghĩa chi phí rút gọn của cung (i, j) là = cπijc ij - π (i) + π (j). Các cung với chi phí rút gọn này thích hợp với đồ thị thặng dư cũng như đồ thị gốc. Chúng ta định nghĩa chi phí rút gọn trong đồ thị thặng dư cũng giống như chúng ta định nghĩa chi phí, nhưng sử dụng thay vì cπijc ij. Tính chất 4.2 1) Với bất kỳ đường đi có hướng P nào từ đỉnh k đến đỉnh l thì ∑ ∈Pji ),( πijc = ∑ ∈Pji ),( cij - π (k) + π (l). 2) Với bất kỳ chu trình có hướng W nào thì ∑ ∈Wji ),( πijc = c∑ ∈Wji ),( ij. Tính chất này chỉ ra rằng khả năng của đỉnh không thay đổi đường đi ngắn nhất giữa bất kỳ cặp đỉnh k và l nào bởi vì các khả năng làm tăng độ dài của mọi đường đi một giá trị không đổi π (l) - π (k). Tính chất này cũng cho thấy nếu W là một chu trình âm với chi phí cung cij, thì nó cũng là một chu trình âm với chi phí cung là . Bây giờ chúng ta có thể thay thế các điều kiện tối ưu về chu trình âm bằng các điều kiện chi phí rút gọn cho các cung. π ijc Định lý 4.3: Các điều kiện tối ưu với chi phí rút gọn Một lời giải khả thi x* là một lời giải tối ưu của bài toán luồng với chi phí cực tiểu khi và chỉ khi tập hợp các khả năng của đỉnh π thỏa các điều kiện tối ưu về chi phí rút gọn sau: ≥ 0 với mọi cung (i, j) trong G(x*). (4.4) πijc Trong định lý trên chúng ta đã mô tả một luồng tối ưu x là một luồng thỏa điều kiện 0 với tất cả (i, j) thuộc G(x) với tập hợp các khả năng của đỉnh πijc ≥ π nào đó. Cùng cách đó, chúng ta có thể định nghĩa “các khả năng tối ưu của đỉnh” là tập hợp các khả năng π của đỉnh thỏa điều kiện 0 với tất cả (i, j) thuộc G(x) với luồng khả thi x nào đó. π ijc ≥ 30 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU 4.2.3. Các điều kiện tối ưu bổ sung Định lý 4.1 và 4.3 giúp ta phát hiện tính tối ưu của các lời giải của bài toán luồng với chi phí cực tiểu bằng cách công thức hóa các điều kiện trên các đồ thị thặng dư; bây giờ chúng ta sẽ phát biểu lại các điều kiện này trên các đồ thị gốc. Định lý 4.4 :Các điều kiện tối ưu bổ sung Một lời giải khả thi x* là một lời giải tối ưu cho bài toán luồng với chi phí cực tiểu khi và chỉ khi với một tập hợp các khả năng của đỉnh π nào đó, các chi phí rút gọn và giá trị của luồng thỏa các điều kiện tối ưu lỏng bổ sung sau đối với mọi cung (i, j) ∈ A : Nếu π > 0 thì = 0 (4.5a) ijc *ijx Nếu 0 < < u*ijx ij thì = 0 (4.5b) πijc Nếu π < 0 thì = uijc *ijx ij (4.5c) Chứng minh: Chúng ta sẽ chỉ ra rằng các điều kiện tối ưu về chi phí rút gọn tương đương với (4.5). Để có kết luận này, trước tiên chúng ta chứng minh rằng nếu các khả năng của đỉnh π và luồng x thỏa các điều kiện tối ưu về chi phí rút gọn thì chúng phải thỏa (4.5). Hãy xét 3 trường hợp cho mọi cung (i, j)∈ A. Trường hợp 1. Nếu > 0, đồ thị thặng dư không thể chứa cung (j, i) vì = - < 0, mâu thuẫn với (4.4). Vì vậy, = 0. π ijc π jic π ijc * ijx Trường hợp 2. Nếu 0 < < u*ijx ij, đồ thị thặng dư chứa cả cung (i, j) và cung (j, i). Các điều kiện tối ưu về chi phí rút gọn chỉ ra rằng 0 và 0. Nhưng vì = - nên từ các bất đẳng trên suy ra = = 0. π ijc ≥ πjic ≥ π jic π ijc π ijc π jic Trường hợp 3. Nếu < 0, đồ thị thặng dư không thể chứa cung (i, j) vì < 0, mâu thuẫn (4.4). Vì thế, = u π ijc π ijc * ijx ij. 4.3. Liên hệ các luồng tối ưu và các khả năng tối ưu của đỉnh Chúng ta có các câu hỏi sau: (1) cho một luồng tối ưu, làm cách nào để có được các khả năng (của đỉnh) tối ưu? Ngược lại, (2) cho các khả năng tối ưu, làm cách nào để có được một luồng tối ưu? Chúng ta chỉ ra cách giải quyết những bài 31 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU toán này bằng cách giải một bài toán được đi ngắn nhất hoặc một bài toán luồng cực đại. Các kết quả này chỉ ra một quan hệ đáng chú ý giữa bài toán luồng với chi phí nhỏ nhất và các bài toán luồng cực đại và đường đi ngắn nhất. Tính toán khả năng tối ưu của đỉnh Chúng ta sẽ chỉ ra rằng nếu cho trước một luồng tối ưu x*, ta có thể đạt được các khả năng tối ưu bằng cách giải một bài toán đường đi ngắn nhất (với các cung có thể âm). Gọi G(x*) là đồ thị thặng dư đối với luồng x*. Rõ ràng, G(x*) không chứa chu trình có chi phí âm nào, nếu ngược lại thì mâu thuẫn với tính tối ưu của lời giải x*. Gọi d(.) là đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị thặng dư nếu chúng ta coi cij là độ dài các cung. Khoảng cách d(.) được định nghĩa tốt bởi vì đồ thị thặng dư không chứa chu trình âm. Các điều kiện tối ưu về đường đi ngắn nhất (2.2) cho ta: d(j) ≤ d(i) + cij với mọi (i, j) trong G(x*) (4.6) Đặt π = -d. Chúng ta có thể biểu diễn (4.6) thành = cπijc ij - π (i) + π (j) 0 với mọi (i, j) trong G(x*) ≥ Định lý 4.3 cho thấy π tạo thành một tập hợp tối ưu các khả năng của đỉnh. Đạt được các luồng tối ưu Bây giờ chúng ta sẽ chỉ ra rằng nếu cho trước một tập hợp các khả năng tối ưu π , chúng ta có thể đạt được một lời giải tối ưu x* bằng cách giải một bài toán luồng cực đại. Trước tiên, chúng ta sẽ tính chi phí rút gọn cho mọi cung (i, j) A và rồi lần lượt khảo sát tất cả các cung. Chúng ta sẽ phân loại mỗi cung (i, j) theo một trong các cách sau và sử dụng các cách phân loại này để định nghĩa một bài toán luồng cực đại. π ijc ∈ Trường hợp 1: > 0 πijc Điều kiện (4.5a) cho biết phải bằng 0. Chúng ta tuân theo ràng buộc này bằng cách đặt = 0 và xóa cung (i, j) khỏi đồ thị. * ijx * ijx 32 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU Trường hợp 2: < 0 πijc Điều kiện (4.5a) cho biết = u*ijx ij. Chúng ta tuân theo ràng buộc này bằng cách đặt = u*ijx ij và xóa cung (i, j) khỏi đồ thị. Bởi vì chúng ta gửi uij đơn vị luồng trên cung (i, j), chúng ta phải giảm b(i) một lượng uij và tăng b(j) một lượng uij. Trường hợp 3: = 0 πijc Trong trường hợp này chúng ta cho phép luồng trên cung (i, j) nhận bất kỳ giá trị nào giữa 0 và uij. Gọi G’ = (N, A’) là đồ thị kết quả và b’ là khả năng cung/cầu được bổ sung của các đỉnh. Bây giờ bài toán trở thành tìm một luồng khả thi trong đồ thị G’ thỏa mãn khả năng cung/cầu được bổ sung của các đỉnh. Chúng ta có thể tìm một luồng như thế bằng cách giải bài toán luồng cực đại được định nghĩa như sau. Chúng ta giới thiệu một đỉnh nguồn s và một đỉnh đích t. Với mỗi đỉnh i có b’(i) > 0, chúng ta thêm một cung (s, i) có độ thông qua b’(i) và với mỗi đỉnh i có b’(i) < 0, chúng ta thêm một cung (i, t) có độ thông qua –b’(i). Bây giờ chúng ta giải toán một bài toán luồng cực đại từ đỉnh s đến t trong đồ thị biến đổi để đạt được một luồng cực đại x*. Lời giải cho ∀ (i, j) *ijx ∈ A là một luồng tối ưu cho bài toán luồng với chi phí cực tiểu trong G. 4.4. Thuật toán khử chu trình âm và tính chất nguyên Các điều kiện tối ưu về chu trình âm cho ta một hướng tiếp cận thuật toán đơn giản để giải bài toán luồng với chi phí cực tiểu, chúng ta gọi là thuật toán khử chu trình âm. Thuật toán này giữ một lời giải khả thi và tại mỗi vòng lặp cố gắng để cải thiện giá trị hàm mục tiêu của nó. Trước hết thuật toán thành lập một luồng khả thi x trong đồ thị bằng cách giải bài toán luồng cực đại. Rồi nó sẽ tìm các chu trình có hướng có chi phí âm trong đồ thị thặng dư và tăng luồng trên những chu trình này. Thuật toán kết thúc khi đồ thị thặng dư không chứa chu trình có hướng chi phí âm. Định lý 4.1 cho biết khi thuật toán kết thúc, nó tìm được một luồng có chi phí cực tiểu. Dưới đây là dạng tổng quát của thuật toán khử chu trình âm. 33 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU Thuật toán khử chu trình âm begin tìm một luồng khả thi x trong đồ thị; while G(x) chứa một chu trình âm do begin sử dụng một thuật toán để tìm một chu trình âm W; δ := min{rij: (i, j) ∈ W}; tăng δ đơn vị luồng trong chu trình W và cập nhật G(x); end; end; i j ( c , u )ij ij x ij i j ( c , r )ij ij 2 1 3 4 b(2 ) = 0 b(1 ) = 4 b(4 ) = -4 b(3 ) = 0 (2, 4) 3 (3, 3) 3 0 (1 , 2) (2, 2) 1 1 (1, 5) (a) 2 1 3 4 (2, 1) (-3, 3) (1 , 2) (-2, 1) (1, 4) (b) (-2, 3) (2, 1) (-1, 1) 2 1 3 4 (2, 1) (-3, 1)(-1 , 2) (-2, 1) (1, 2) (c) (-2, 3) (2, 1) (-1, 3) (3, 2) 2 1 3 4 (2, 2) (3, 3) (-1 , 2) (-2, 1) (1, 1) (d) (-2, 2) (-1, 4) (a) Đồ thị có 1 luồng khả thi x; (b) Đồ thị thặng dư G(x); (c) Đồ thị thặng dư sau khi tăng 2 đơn vị luồng theo chu trình 4-2-3-4; (d) Đồ thị thặng dư sau khi tăng 1 đơn vị luồng theo chu trình 4-2-1-3-4 Hình 4-1 Minh họa thuật toán Khử chu trình âm Chúng ta dùng ví dụ trên hình vẽ 4.1(a) để minh họa thuật toán khử chu trình âm. (Chúng ta vi phạm giả thiết 4) để dễ khảo sát đồ thị hơn). Hình vẽ 4.1(a) mô tả một luồng khả thi trong đồ thị và hình vẽ 4.1(b) là đồ thị thặng dư tương 34 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU ứng. Giả sử thuật toán chọn chu trình 4-2-3-4 có chi phí là -1 trước tiên. Khả năng thông qua thặng dư của chu trình này là 2. Thuật toán tăng 2 đơn vị luồng theo chu trình này. Hình vẽ 4.1(c) vẽ đồ thị thặng dư bổ sung. Trong vòng lặp kế tiếp, giả sử thuật toán chọn chu trình 4-2-1-3-4 có chi phí -2. Thuật toán gửi 1 đơn vị luồng theo chu trình này. Hình vẽ 4.1(d) mô tả đồ thị thặng dư cập nhật. Vì đồ thị thặng dư không chứa chu trình âm nào nữa nên thuật toán kết thúc. Có nhiều thuật toán phát hiện chu trình âm. Trong đó thuật toán hiệu chỉnh nhãn FIFO (thuật toán tìm đường đi ngắn nhất) có thể nhận dạng chu trình âm một cách hiệu quả trong thời gian O(nm). Một kết quả phụ của thuật toán khử chu trình âm là định lý quan trọng sau đây: Định lý 4.5: Tính chất nguyên Nếu tất cả các độ thông qua của cung và khả năng cung/cầu của các đỉnh là số nguyên thì bài toán luồng với chi phí nhỏ nhất luôn có một luồng với chi phí nhỏ nhất là số nguyên. Trong bài toán luồng với chi phí nhỏ nhất, mCU là chặn trên của chi phí luồng ban đầu (vì cij C và x≤ ij ≤ U với ∀ (i, j) ∈A) và –mCU là chặn dưới của chi phí luồng tối ưu (do cij -C và x≥ ij ≤ U với ∀ (i, j) ∈A). Mỗi vòng lặp của thuật toán khử chu trình âm thay đổi giá trị hàm mục tiêu một lượng (∑ c∈Wji ),( ij)δ , là một giá trị âm. Chúng ta giả sử rằng tất cả dữ liệu của bài toán là số nguyên nên thuật toán sẽ kết thúc trong O(mCU) vòng lặp và chạy trong thời gian O(nm2CU). 4.5. Thuật toán đường đi ngắn nhất liên tiếp Thuật toán khử chu trình âm duy trì tính khả thi của lời giải trong mỗi bước và cố gắng để đạt được lời giải tối ưu. Ngược lại, thuật toán đường đi ngắn nhất liên tiếp duy trì tính tối ưu của lời giải ở mỗi bước và cố gắng đạt được tính khả thi. Nó giữ một lời giải x thỏa mãn ràng buộc không âm và độ thông qua, nhưng vi phạm ràng buộc cân bằng khối lượng của các đỉnh. Tại mỗi bước, thuật toán chọn một đỉnh s có khả năng cung thừa (nghĩa là nút cung chưa gửi đến nút cầu) và một đỉnh t có khả năng cầu chưa hoàn thành và gửi luồng từ đỉnh s đến đỉnh t theo một 35 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU đường đi ngắn nhất trong đồ thị thặng dư.Thuật toán kết thúc khi lời giải hiện tại thỏa mãn tất cả các ràng buộc cân bằng khối lượng. Để mô tả thuật toán này, trước hết chúng ta giới thiệu khái niệm luồng giả. Một luồng giả là một hàm x: A → R+ chỉ thỏa mãn các ràng buộc không âm và khả năng thông qua; nó không cần thỏa mãn các ràng buộc cân bằng khối lượng. Với mọi luồng giả x, ta định nghĩa độ mất cân bằng của đỉnh i như sau: e(i) = b(i) + x∑ ∈ }),(:{ Aijj ji - ∑ ∈ }),(:{ Ajij xij với ∀ i ∈ N Nếu e(i) > 0 với đỉnh i nào đó, ta nói e(i) là mức vượt quá của đỉnh i; nếu e(i) < 0, ta gọi –e(i) là mức thiếu hụt của đỉnh. Chúng ta gọi một đỉnh i có e(i) = 0 là cân bằng. Gọi E và D là các tập hợp các đỉnh vượt quá và thiếu hụt trong đồ thị. Chú ý rằng e(i) = b(i) = 0, vì thế ∑∈Ni ∑∈Ni ∑∈Ei e(i) = -∑∈Di e(i). Do đó, nếu đồ thị chứa một đỉnh vượt quá thì nó cũng phải chứa một đỉnh thiếu hụt. Đồ thị thặng dư tương ứng với một luồng giả được định nghĩa giống như chúng ta định nghĩa đồ thị thặng dư cho một luồng. Bổ đề 4.6 Giả sử một luồng giả (hoặc một luồng) x thỏa các điều kiện tối ưu về chi phí rút gọn đối với các khả năng (của đỉnh) π nào đó. Gọi vectơ d là các khoảng cách đường đi ngắn nhất từ đỉnh s đến tất cả các đỉnh khác trong đồ thị thặng dư G(x) với là độ dài của cung (i, j), ta có các tính chất sau: πijc 1) Luồng giả x cũng thỏa các điều kiện tối ưu về chi phí rút gọn đối với các khả năng của đỉnh π ’ = π - d. 2) Các chi phí rút gọn với tất cả các cung (i, j) trên đường đi ngắn nhất từ đỉnh s đến mọi đỉnh khác. π ijc Bổ đề 4.7 Giả sử một luồng giả (hoặc một luồng) x thỏa các điều kiện tối ưu về chi phí rút gọn và chúng ta đạt được x’ từ x bằng cách gửi luồng theo một đường đi ngắn nhất từ đỉnh s đến một số đỉnh k khác, thì x’ cũng thỏa các điều kiện tối ưu về chi phí rút gọn. 36 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU Dưới đây là mô tả của thuật toán đường đi liên tiếp. Các khả năng của đỉnh đóng vai trò rất quan trọng trong thuật toán này. Bên cạnh việc sử dụng chúng để chứng minh tính đúng đắn của thuật toán, chúng ta còn dùng chúng để giữ độ dài các cung không âm giúp ta giải quyết bài toán đường đi ngắn nhất một cách hiệu quả. Thuật toán đường đi ngắn nhất liên tiếp begin x := 0 và π := 0; e(i) := b(i) với ∀ i∈N; khởi tạo tập hợp E := {i: e(i) > 0} và D := {i: e(i) < 0}; while E ≠ do ∅ begin Chọn một đỉnh k ∈ E và một đỉnh l ∈ D; Xác định các khoảng cách đường đi ngắn nhất d(j) từ đỉnh s đến tất cả các đỉnh khác trong G(x) với các chi phí rút gọn ; πijc P biểu thị đường đi ngắn nhất từ đỉnh k đến đỉnh l; Cập nhật π := π - d; δ := min[e(k), -e(l), min{rij: (i, j) ∈ P}]; Tăng δ đơn vị luồng theo đường đi P; Cập nhật x, G(x), E, D, và các chi phí rút gọn; end; end; Chúng ta minh họa thuật toán đường đi ngắn nhất liên tiếp trên cùng một ví dụ chúng ta đã sử dụng để minh họa thuật toán khử chu trình âm. Hình vẽ 4.2(a) là đồ thị thặng dư ban đầu. Khởi tạo, E = {1} và D = {4}. Do đó, trong vòng lặp đầu tiên, s = 1 và t = 4. Đường đi ngắn nhất d (đối với các chi phí rút gọn) là d = (0, 2, 2, 3) và đường đi ngắn nhất từ đỉnh 1 đến đỉnh 4 là 1-3-4. Hình vẽ 4.2(b) biểu diễn các khả năng (của đỉnh) đã được cập nhật và các chi phí rút gọn, và hình vẽ 4.2(c) là lời giải sau khi chúng ta đã tăng luồng min{e(1), -e(4), r13, r34} = min{4, 4, 2, 5} = 2 đơn vị luồng theo đường đi 1-3-4. Trong vòng lặp thứ hai, k = 1, l = 4, d = (0, 0, 1, 1) và đường đi ngắn nhất từ đỉnh 1 đến đỉnh 4 là 1-2-3-4. Hình vẽ 4.2(d) biểu 37 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU diễn các khả năng đã được cập nhật và các chi phí rút gọn, và hình vẽ 4.2(e) là lời giải sau khi chúng ta đã tăng luồng min{e(1), -e(4), r12, r23, r34} = min{2, 2, 4, 2, 3} = 2 đơn vị luồng. Cuối vòng lặp này, tất cả các độ mất cân bằng (imbalance) đều bằng 0 và thuật toán kết thúc. Bây giờ chúng ta chứng minh tính đúng đắn của thuật toán đường đi ngắn nhất liên tiếp. Để khởi tạo, chúng ta đặt x = 0, là một luồng giả khả thi. Với luồng giả x bằng 0, G(x) = G. Chú ý rằng lời giải này cùng với π = 0 thỏa các điều kiện tối ưu về chi phí rút gọn vì = cπijc ij 0 với mọi cung (i, j) trong đồ thị G(x) (nhớ lại rằng trong giả thiết 5) thì chi phí của tất cả các cung là không âm). Ta quan sát thấy khi vẫn còn đỉnh có độ mất cân bằng khác 0 thì cả E và D phải khác rỗng ( ≥ ∅ ) vì tổng các độ vượt quá bằng tổng các mức thiếu hụt. Vì vậy cho đến khi tất cả các đỉnh đều cân bằng thì thuật toán luôn có thể xác định một đỉnh vượt quá k và một đỉnh thiếu l. Giả thiết 4) chỉ ra rằng đồ thị thặng dư chứa một đường đi có hướng từ đỉnh k đến mọi đỉnh khác, bao gồm cả đỉnh l. Do đó các khoảng cách đường đi ngắn nhất d(.) được định nghĩa tốt. Mỗi vòng lặp của thuật toán giải một bài toán đường đi ngắn nhất với chiều dài cung không âm và giảm độ vượt quá của một số đỉnh (đồng thời cũng giảm mức thiếu hụt của một số đỉnh). Do đó, nếu U là chặn trên của khả năng cung lớn nhất của các đỉnh, thuật toán sẽ kết thúc sau nhiều nhất nU vòng lặp. Nếu S(n, m, C) là thời gian cần thiết để giải bài toán đường đi ngắn nhất với độ dài cung không âm thì độ phức tạp tổng cộng của thuật toán này là O(nUS(n, m, nC)). Chú ý rằng chúng ta dùng nC thay vì C trong biểu thức này vì chi phí trong đồ thị thặng dư bị chặn bởi nC. 38 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU i j ( c , u )ij ij 2 1 3 4 e(2 ) = 0 (2, 4) (3, 3) (1 , 2) (2, 2) (1, 5) (2 ) = 0 e(1 ) = 0 (1 ) = 0 e(4 ) = 0 (4 ) = 0 e(3 ) = 0 (3 ) = 0 (a) 2 1 3 4 e(2 ) = 0 (0, 4) (2, 3) (1 , 2) (0, 2) (0, 5) (2 ) = -2 e(1 ) = 4 (1 ) = 0 e(4 ) = -4 (4 ) = -3 e(3 ) = 0 (3 ) = -2 (b) 2 1 3 4 e(2 ) = 0 (0, 4) (2, 3) (1 , 2) (0, 2) (0, 3) (2 ) = -2 e(1 ) = 2 (1 ) = 0 e(4 ) = -2 (4 ) = -3 e(3 ) = 0 (3 ) = -2 (c) (0, 2) 2 1 3 4 e(2 ) = 0 (0, 4) (1, 3) (0 , 2) (0, 2) (0, 3) (2 ) = -2 e(1 ) = 2 (1 ) = 0 e(4 ) = -2 (4 ) = -4 e(3 ) = 0 (3 ) = -3 (d) (0, 2) 2 1 3 4 e(2 ) = 0 (0, 2) (1, 3) (0 , 2) (0, 2) (0, 1) (2 ) = -2 e(1 ) = 0 (1 ) = 0 e(4 ) = 0 (4 ) = -4 e(3 ) = 0 (3 ) = -3 (e) (0, 4) (0, 2) (a) Đồ thị thặng dư ban đầu với x=0 và =0; (b) Đồ thị sau khi cập nhật các khả năng ; (c) Đồ thị sau khi tăng 2 đơn vị luồng theo đừơng 1-3-4; (d) Đồ thị sau khi cập nhật khả năng ; (e) Đồ thị sau khi tăng 2 đơn vị luồng theo 1-2-3-4 πππ Hình 4-2 Minh họa thuật toán đường đi ngắn nhất liên tiếp 4.6. Thuật toán Primal-dual Thuật toán primal-dual cho bài toán luồng với chi phí cực tiểu cũng giống như thuật toán đường đi ngắn nhất liên tiếp ở khía cạnh nó cũng duy trì một luồng giả thỏa mãn các điều kiện tối ưu về chi phí rút gọn và từ từ biến đổi nó thành một luồng bằng cách tăng luồng theo các đường đi ngắn nhất. Nhưng nó khác ở chỗ thay vì tăng luồng dọc theo một đường đi ngắn nhất tại một thời điểm, nó giải bài toán luồng cực đại để tăng luồng theo tất cả các đường đi ngắn nhất. 39 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU Thuật toán primal-dual biến đổi bài toán luồng với chi phí cực tiểu thành một bài toán có một đỉnh vượt quá đơn và một đỉnh thiếu hụt đơn. Chúng ta biến đổi bài toán thành dạng này bằng cách đưa vào một đỉnh nguồn s và một đỉnh đích t. Với mỗi đỉnh i có b(i) > 0, chúng ta thêm cung (s, i) có chi phí bằng 0 và độ thông qua b(i), và với đỉnh i có b(i) < 0, chúng ta thêm cung (i, t) có chi phí bằng 0 và độ thông qua –b(i). Cuối cùng chúng ta đặt b(s) = ∑ >∈ }0)(:{ ibNi b(i), b(t) = -b(s), và b(i) = 0 với i∈N. Dễ thấy rằng một luồng có chi phí cực tiểu trong đồ thị biến đổi cho ta một luồng với chi phí cực tiểu trong đồ thị gốc. Để đơn giản hóa các ký hiệu, chúng ta biểu diễn đồ thị biến đổi là G = (N, A), giống như chúng biểu diễn của đồ thị gốc. ∀ Thuật toán primal-dual giải bài toán luồng cực đại trên một đồ thị con của đồ thị thặng dư G(x), được gọi là đồ thị có thể chấp nhận, được biểu diễn là Go(x). Chúng ta định nghĩa một đồ thị có thể chấp nhận Go(x) đối với một luồng giả x thỏa các điều kiện tối ưu về chi phí rút gọn với khả năng π ; đồ thị có thể chấp nhận chỉ chứa các cung có chi phí rút gọn bằng 0 trong G(x). Khả năng thông qua thặng dư của một cung trong Go(x) bằng với trong G(x). Ta nhận thấy rằng mọi đường đi có hướng từ đỉnh s đến đỉnh t trong Go(x) là đường đi ngắn nhất giữa hai đỉnh đó trong G(x). Dưới đây là thuật toán primal-dual trên đồ thị biến đổi. Thuật toán primal-dual begin x := 0 và π := 0; e(s) := b(s) và e(t) := b(t); while e(s) > 0 do begin Xác định các khoảng cách đường đi ngắn nhất d(.) từ đỉnh s đến tất cả các đỉnh khác trong G(x) với các chi phí rút gọn ; πijc Cập nhật π := π - d; Định nghĩa đồ thị có thể chấp nhận Go(x); Tìm luồng cực đại từ đỉnh s đến đỉnh t trong Go(x); 40 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU Cập nhật e(s), e(t) và G(x); end; end; Để minh họa thuật toán primal-dual, chúng ta xét ví dụ trên hình vẽ 4.3(a). Hình vẽ 4.3(b) thể hiện đồ thị biến đổi. Đường đi ngắn nhất từ đỉnh s đến các đỉnh 1, 2, 3, 4, t lần lượt là 0, 0, 1, 2, 1 với độ dài các cạnh là . Hình vẽ 4.3(c) biểu diễn các khả năng được thay đổi và các chi phí rút gọn. Hình vẽ 4.3(d) là đồ thị có thể chấp nhận. Khi chúng ta áp dụng thuật toán luồng cực đại với đồ thị có thể chấp nhận, ta có thể gửi 2 đơn vị luồng từ đỉnh s đến đỉnh t. Quan sát rằng đồ thị có thể chấp nhận chứa 2 đường đi từ đỉnh s đến đỉnh t và luồng đi qua cả hai đường này. Thuật toán đường đi ngắn nhất liên tiếp lặp 2 lần để gửi 2 đơn vị luồng. Vòng lặp thứ 2 của thuật toán primal-dual cũng gửi 2 đơn vị luồng từ đỉnh s đến đỉnh t, tại thời điểm đó nó chuyển luồng giả thành luồng và kết thúc. π ijc Thuật toán primal-dual đảm bảo rằng độ vượt quá của đỉnh s giảm sau mỗi vòng lặp, và cũng chắc chắn rằng khả năng của đỉnh đích giảm khi chuyển từ vòng lặp này sang vòng lặp khác. Nhận xét thứ hai có được từ việc khi chúng ta thiết lập một luồng cực đại trong Go(x), đồ thị thặng dư G(x) không chứa đường đi có hướng nào từ đỉnh s đến đỉnh t chỉ gồm các cung có chi phí rút gọn bằng 0. Do đó trong vòng lặp kế tiếp khi chúng ta giải bài toán đường đi ngắn nhất d(t) ≥ 1. Các quan sát này cho chúng ta một giới hạn min{nU, nC} đối với số vòng lặp vì ban đầu e(s) nU, và không có giá trị khả năng của đỉnh nào có thể hạ thấp hơn –nC. Giới hạn về số vòng lặp này tốt hơn của thuật toán đường đi ngắn nhất liên tiếp, nhưng thuật toán phải chịu một chi phí cho việc giải bài toán luồng cực đại ở mỗi vòng lặp. Nếu S(n, m, C) và M(n, m, U) là thời gian giải bài toán đường đi ngắn nhất và luồng cực đại thì thuật toán primal-dual có độ phức tạp tổng cộng là O(min{nU, nC} {S(n, m, nC) + M(n, m, U)}). ≤ 41 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU i j ( c , u )ij ij b(i) b(j) 1 3 2 4 (1 , 1) (2 , 2) (2, 1) (1, 1) 2 -2 2 -2 1 3 2 4 (1 , 1) (2 , 2) (2, 1) (1, 1) 0 0 0 0 s t (0, 2) (0, 2) (0, 2) (0, 2) (a) (b) 4 -4 i j (c , u )ij ij 1 3 2 4 (0 , 1) (0 , 1) (0, 1)s t (0, 2) (1, 2) (c) e(s ) = 4 e(t ) = -4 (0, 2) (0, 1) (0, 2) (1 ) = 0 (3 ) = -1 (4 ) = -2(2 ) = 0 (s ) = 0 (t ) = 1 i j rij 1 3 2 4 1 0 0 1 s t 2 2 2 (d) e(s ) = 4 e(t ) = -4 (a) Đồ thị mẫu; (b) Đồ thị biến đổi; (c) Đồ thị thặng dư sau khi cập nhật các khả năng của đỉnh; (d) Đồ thị có thể chấp nhận Hình 4-3 Minh họa thuật toán Primal - dual 4.7. Các thuật toán cải tiến Ở phần trên, chúng ta đã xét một số thuật toán giúp giải bài toán luồng với chi phí cực tiểu. Mặc dù các thuật toán này đảm bảo sự hội tụ nếu như dữ liệu trong bài là số nguyên, nhưng việc tính toán không được giới hạn bởi một hàm đa thức. Và như vậy, thuật toán không đảm bảo sẽ giải tốt tất cả các bài toán được đặt ra. Dưới đây là một số một số cải tiến quan trọng của các thuật toán trên để bài toán có thể giải trong thời gian đa thức. 42 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU 4.7.1. Cải tiến thuật toán đường đi ngắn nhất liên tiếp Bây giờ chúng ta đề xuất một số cách cải tiến trên thực tế đối với thuật toán đường đi ngắn nhất liên tiếp. Như mô tả, thuật toán này chọn một đỉnh vượt quá k, sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh k đến tất cả các đỉnh khác, và tăng luồng theo một đường đi từ đỉnh k đến một đỉnh thiếu l nào đó. Thật sự, không cần thiết phải xác định đường đi ngắn nhất từ đỉnh k đến tất cả các đỉnh khác; một đường đi ngắn nhất từ đỉnh k đến một đỉnh thiếu l là đủ. Do đó, chúng ta có thể kết thúc thuật toán Dijkstra ngay khi nó gán nhãn cố định cho đỉnh thiếu l đầu tiên. Chúng ta có thể thay đổi các khả năng của đỉnh theo cách sau: =)(iπ )()( idi −π )()( ldi −π hay một cách khác =)(iπ )()()( ldidi +−π )(iπ Bằng các cách này, chúng ta có thể giữ các chi phí rút gọn của tất cả các cung không âm và chi phí rút gọn của các cung trên đường đi ngắn nhất từ đỉnh k đến đỉnh l bằng 0. 4.7.2. Một số cách cải tiến khác Hai phương pháp nhằm tối ưu hóa thời gian chạy của thuật toán: phương pháp thứ nhất tác động lên yếu tố luồng trong đồ thị (tăng luồng), phương pháp thứ hai tác động lên yếu tố chi phí (giảm chi phí), hai phương pháp này sẽ được minh họa bằng các thuật toán tỉ lệ theo thông lượng và tỉ lệ theo chi phí sau: 4.7.2.1. Thuật toán tỉ lệ theo thông lượng Thuật toán tỉ lệ theo thông lượng áp dụng cho bài toán luồng có chi phí cực tiểu bảo đảm rằng mỗi lần làm tăng trưởng đường đi ngắn nhất sẽ mang theo một lượng lớn luồng dọc theo đường đi này. 43 KH OA C NT T – Đ H KH TN CHƯƠNG 4: LUỒNG CÓ CHI PHÍ CỰC TIỂU Thuật toán tỉ lệ theo thông lượng áp dụng vào bài toán luồng có chi phí cực tiểu tổng quát bằng cách sử dụng một luồng giả x và giá trị e(i), với e(i) là giá trị mất cân bằng tại nút i được định nghĩa như sau: ∑∑ ∈∈ −+= }),(:{}),(:{ )()( Ajij ij Aijj ji xxibie Ni∈∀ Thuật toán duy trì một luồng giả thỏa mãn điều kiện giảm chi phí tối ưu và từng bước biến đổi luồng giả này thành một luồng bằng cách xác định đường đi ngắn nhất từ các nút thừa đến các nút thiếu và tăng luồng dọc theo các đường này. Đặt một pha tỉ lệ có giá trị cụ thể ∆ là pha tỉ lệ ∆ . Ban đầu 2, = 2∆ |log U|. Thuật toán bảo đảm rằng trong mỗi pha tỉ lệ ∆ , mỗi lần tăng trưởng sẽ mang chính xác đơn vị luồng. Khi không còn nút nào vượt quá giá trị ∆ ∆ tối thiểu hay không còn nút nào thấp hơn giá trị ∆ tối thiểu thì thuật toán sẽ giảm giá trị đi hai lần và tiếp tục tiến trình. Cuối cùng khi ∆ ∆= 1 thì pha này kết thúc và ta nhận được một luồng. Luồng này chính là luồng tối ưu vì nó thỏa mãn điều kiện giảm chi phí tối ưu. Với giá trị ∆ , ta định nghĩa hai tập hợp S(∆ ) và T(∆ ) như sau : S(∆ ) = {i : e(i) ∆≥ } T(∆ ) = {i : e(i) ∆−≤ } Trong một pha tỉ lệ, mỗi lần tăng trưởng phải bắt đầu từ một nút trong S(∆ ) và kết thúc tại một nút trong T(∆ ). Ngoài ra, sự tăng luồng phải diễn ra trên một đường đi có các cạnh có độ thông qua thặng dư tối thiểu là ∆ . Do đó, ta có một định nghĩa khác: Mạng thặng dư G(x,∆ ∆ ) là một mạng con của G(x), gồm những cạnh có độ thông qua thặng dư tối thiểu là ∆ . Trong một pha tỉ lệ, thuật toán tăng một luồng từ một nút trong S(∆ ) đến một nút trong mạng G(x,∆ ). Thuật toán đáp ứng tính chất mỗi cạnh của G(x, ) thỏa điều kiện giảm chi phí tối ưu. Tuy nhiên các cạnh của G(x) mà không thuộc G(x, ∆ ∆ ) có thể vi phạm điều kiện này. Cần chú ý rằng thuật toán này chỉ tăng chính