Báo cáo nghiên cứu khoa học: THUẬT TOÁN HOÁN CHUYỂN NGUỒN ĐÍCH CÓ TRỌNG SỐ TÌM LUỒNG CỰC ĐẠI

Tham khảo luận văn - đề án báo cáo nghiên cứu khoa học: " thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại", luận văn - báo cáo phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: " THUẬT TOÁN HOÁN CHUYỂN NGUỒN ĐÍCH CÓ TRỌNG SỐ TÌM LUỒNG CỰC ĐẠI" TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).2008 THUẬT TOÁN HOÁN CHUYỂN NGUỒN ĐÍCH CÓ TRỌNG SỐ TÌM LUỒNG CỰC ĐẠI WEIGHTED SOURCE-SINK ALTERNATIVE ALGORITHM TO FIND MAXIMAL FLOW TRẦN QUỐC CHIẾN Trường Đại học Sư phạm, Đại học Đà Nẵng TÓM TẮT Công trình tiếp tục nghiên cứu thuật toán hoán chuyển nguồn đí ch giải bài toán tìm luồng cực đại trên mạng. Kết quả chính của báo cáo là đề xuất Thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại. Ý tưởng thuật toán là tìm đường đi tăng luồng đồng thời từ đỉnh nguồn và đỉnh đích với trọng số là lực lượng các đỉnh gán nhãn tiến và nhãn lùi. Kết quả tính toán qua các ví dụ cho thấy thuật toán hoán chuyển nguồn đích có trọng số là thuật toán tổng quát có thể áp dụng hiệu quả cho mạng bất kỳ. ABSTRACT This paper deals with the maximal flow problem. The basic results are systematically presented and proved. The known Ford-Fulkerson is thoroughly introduced and illustrated. The main result of this work is the weighted source -sink alternative algorithm. The idea of the algorithm is to find augmented paths simultaneously from the source and the sink vertex with the weights as the cardinalities of the forward labeled vertices and the backward labeled vertices (the Ford-Fulkerson algorithm finds augmented paths only from the source vertex). Calculus examples show that the proposed algorithm considerably decreases the computational complexity in comparison with the Ford -Fulkerson algorithm. Key word: graph, network, flow Ý tưởng của phương pháp này là gán nhãn các đỉnh đồng thời từ đỉnhnguồn và đỉnh đích, xem [16]. Sự khác biệt cơ bản của thuật toán nà y so với thuậttoán hoán chuyển nguồn đích trong [16] như sau: Tại mỗi bước lặp, để xác địnhhướng gán nhãn, ta xác định lực lượng của tập đỉnh đã có nhãn tiến, nhưng chưađược dùng để sinh nhãn tiến, kí hiệu S, và lực lượng của tập đỉnh đã có nhãn lùi,nhưng chưa được dùng để sinh nhãn lùi, kí hiệu T. S  và T  có thể coi là trọng sốcủa hướng gán nhãn. Nếu S   T , thì sinh nhãn tiến, ngược lại sinh nhãn lùi. Thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại + Đầu vào. Mạng G = (V, E) với nguồn a, đích z, khả năng thông qua C =(cij), (i,j)G. Các đỉnh trong G được sắp xếp theo thứ tự nào đó. + Đầu ra. Luồng cực đại F = (fij), (i,j)G + Các bước: 99 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).20081. Khởi tạo Luồng xuất phát: fij := 0 (i,j)G Đặt nhãn tiến () cho đỉnh nguồn và nhãn lùi () cho đỉnh đích a(, , ) & z(, , ) Tạo lập tập S gồm các đỉnh đã có nhãn tiến nhưng chưa được dùng để sinhnhãn tiến: S:={a} Tạo lập tập T gồm các đỉnh đã có nhãn lùi nhưng chưa được dùng để sinhnhãn lùi: T:={z}2. Chọn chiều sinh nhãn Nếu S   T , thì sang bước 3 (sinh nhãn tiến), ngược lại sang bước 4 (sinhnhãn lùi).3. Sinh nhãn tiến3.1. Chọn đỉnh sinh nhãn tiến  Trường hợp S  : Chọn đỉnh u  S nhỏ nhất (theo thứ tự). Loại u khỏi S, S := S { u }. Ký hiệu nhãn tiến của u là (, p, ) và A là tập các đỉnh chưa có nhãn tiến và kề đỉnh sinh nhãn tiến u. Sang bước 3.2.  Trường hợp S = , thì kết thúc, luồng F là cực đại.3.2. Gán nhãn tiến cho đỉnh chưa có nhãn tiến và kề đỉnh sinh nhãn tiến u  Trường hợp A = : Quay lại bước 2.  Trường hợp A  : Chọn t  A nhỏ nhất (theo thứ tự). Loại t khỏi A, A:= A { t }. Gán nhãn tiến cho t như sau: Nếu (u,t)  E và fu,t < cu,t, đặt nhãn tiến đỉnh t là (, u, min{, cu,t  fu,t}). Nếu (t, u)  E và ft,u > 0, đặt nhãn tiến đỉnh t là (, u, min{, ft,u}). Nếu t không được gán nhãn tiến, thì quay lại bước 3.2. Nếu t được gán nhãn tiến và t có nhãn lùi, thì sang bước hiệu chỉnh tăngluồng 5. Nếu t được gán nhãn tiến và t không có nhãn lùi, thì bổ sung t vào S, S:=S  { t }, và quay lại bước 3.2.4. Sinh nhãn lùi4.1. Chọn đỉnh sinh nhãn lùi  Trường hợp T  : Chọn đỉnh v  T nhỏ nhất (theo thứ tự). Loại v khỏi T, T := T { v }. Ký hiệu nhãn lùi của v là (, q, ) và B là tập các đỉnh chưa có nhãn lùi và kề đỉnh sinh nhãn lùi v. Sang bước 4.2.  Trường hợp T = , thì kết thúc, luồng F là cực đại. 100 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).20084.2. Gán nhãn ...