Nội dung

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ừ đỉnh nguồ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ật toán hoán chuyển nguồn đích trong [16] như sau: Tại mỗi bước lặp, để xác định hướ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).2008 1. 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 để sinh nhã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 để sinh nhã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 (sinh nhãn lùi). 3. Sinh nhãn tiến 3.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ăng luồ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ùi 4.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).2008 4.2. Gán nhãn lùi cho đỉnh chưa có nhãn lùi và kề đỉnh sinh nhãn lùi v  Trường hợp B = : Quay lại bước 2.  Trường hợp B  : Chọn t  B nhỏ nhất (theo thứ tự). Loại t khỏi B, B:=B \ { t }. Gán nhãn lùi cho t như sau: Nếu (t, v)E và ft,v < ct,v, đặt nhãn lùi đỉnh t là (, v, min{, ct,v  ft,v}). Nếu (v, t)E và fv,t > 0, đặt nhãn lùi đỉnh t là (, v, min{, fv,t}). Nếu t không được gán nhãn lùi, thì quay lại bước 4.2. Nếu t được gán nhãn lùi và t có nhãn tiến, thì sang bước hiệu chỉnh tăng luồng 5. Nếu t được gán nhãn lùi và t không có nhãn tiến, thì bổ sung t vào T, T:= T  { t }, và quay lại bước 4.2. 5. Hiệu chỉnh tăng luồng Ký hiệu t là đỉnh được gán nhãn tiến ở bước 3.2 hoặc nhãn lùi ở bước 4.2 để thuật toán dẫn đến bước 5. Giả sử t có nhãn tiến (, p, ) và nhãn lùi (, q, ). Đặt  = min{, }. Ta hiệu chỉnh luồng f như sau: 5.1. Hiệu chỉnh ngược từ t về a theo nhãn tiến 5.1.1. Khởi tạo j := t, i := p 5.1.2. Hiệu chỉnh Nếu cung (i, j)  G, thì hiệu chỉnh fij = fij + . Nếu cung (j, i)  G, thì hiệu chỉnh fji = fji  . 5.1.3. Tịnh tiến Nếu i = a, thì sang bước 5.2. Nếu i  a, thì đặt j := i và i := h, với h là thành phần thứ hai của nhãn tiển đỉnh j. Sau đó quay lại bước 5.1.2. 5.2. Hiệu chỉnh từ t đến z theo nhãn lùi 5.2.1. Khởi tạo i := t, j := q 5.2.2. Hiệu chỉnh Nếu cung (i, j)  G, thì hiệu chỉnh fij = fij + . Nếu cung (j, i)  G, thì hiệu chỉnh fji = fji  . 5.2.3. Tịnh tiến Nếu i = z, thì sang bước 5.3. 101 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).2008 Nếu i  z, thì đặt i := j và j := k, với k là thành phần thứ hai của nhãn lùi đỉnh i. Sau đó quay lại bước 5.2.2. 5.3. Xoá tất cả nhãn của các đỉnh trên mạng, trừ đỉnh nguồn a và đỉnh đích z, và quay lại bước 2.  Định lý 1. Nếu các giá trị thông qua cij là số nguyên, thì sau hữu hạn bước quá trình giải kết thúc. Chứng minh (tương tự như thuật toán Ford-Fulkerson).  Hệ quả. Nếu giá trị thông qua cij là số hữu tỉ với mọi (i,j)  E, thì sau hữu hạn bước quá trình giải kết thúc. Chứng minh (tương tự như thuật toán Ford-Fulkerson).  Định lý 2 Cho mạng G=(V,E,c) với nguồn a và đích z, f = {fij  (i,j)G} là luồng nhận được khi kết thúc thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại. Khi đó, f là luồng cực đại. Chứng minh Ta xét hai trường hợp kết thúc thuật toán. (i) Thuật toán kết thúc ở bước 3.1: Ký hiệu S là tập các đỉnh mang nhãn tiến. Khi đó lát cắt (S, V \ S) là lát cắt cực tiểu (xem chứng minh thuật toán FordFulkerson), kéo theo f là luồng cực đại. (ii) Thuật toán kết thúc ở bước 4.1: Ký hiệu T là tập các đỉnh mang nhãn lùi. Khi đó lát cắt (V \ T, T) là lát cắt cực tiểu (tương tự chứng minh thuật toán FordFulkerson), kéo theo f là luồng cực đại. + Ví dụ 1. Xét mạng G a 1 z 2 n trong đó số đỉnh là (2.n +1)2+1 và các cung cho như hình vẽ với trọng số đều là 1. 102 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).2008 Áp dụng thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại của G ta thấy: Ở bước 2,  T  luôn bằng 1 và nhỏ hơn  S , vì vậy từ vòng lặp thứ 2, chỉ có bước 4 (sinh nhãn lùi) được thực hiện. Do đó kết quả tính toán giống như thuật toán đích hướng nguồn [17]. Cuối cùng ta nhận được luồng cực đại là luồng trên đường đi (a12 ... nz) với giá trị luồng bằng 1. Ta chỉ phải duyệt qua 3n đỉnh để xét gán nhãn lùi. Như vậy khối lượng tính toán chỉ bằng khoảng 1/n khối lượng tính toán theo thuật toán Ford-Fulkerson (phải duyệt qua (2.n+1)2 đỉnh). + Ví dụ 2. Cho k nguyên dương. Xét mạng G = (V,E,c) cho trên mặt phẳng toạ độ (xem hình sau). (i) Tập các đỉnh V là V = { (i, j)  N  N  2k  i  2k, 3k  j  3k }. Số đỉnh của đồ thị là (4k + 1).(6k + 1). (ii) Tập các cung bao gồm các cung ngang và cung dọc nối các đỉnh mạng (a) Cung dọc [(i,j), (i,j+1)], 2k  i  2k, 3k  j  3k1 (i, j  1) ,  2k  i  2k và (3k  j  k1 hoặc k  j  3k1)  (i, j ) (i, j  1)  ,  2k  i  2k và k  j  k1 (i, j ) (b) Cung ngang [(i,j), (i+1,j)], 2k  i  2k1, 3k  j  3k (i,j)(i+1,j)  (0  i  2k1, 0  j  3k) hoặc (2k  i  1, 3k  j  1) (i,j)(i+1,j)  0  i  2k1, 3k  j  1 hoặc 2k  i  1, 0  j  3k (iii) Khả năng thông qua của tất cả các cung là 1. Áp dụng thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại của G ta thấy: lực lượng của S và T tương đương nhau, vì vậy số lần gán nhãn tiến và nhãn lùi xấp xỉ như nhau. Ở mỗi vòng lặp tìm đường đi tăng luồng, số đỉnh xét xấp xỉ (2k)2 = 4.k2, và nhãn tiến và nhãn lùi sẽ gặp nhau ở các đỉnh (i,j) có tọa độ i, 1  i  1. 103 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).2008 3 k ak 2k 1 1 0 1 1 - z k 2 k Ta cũng dễ dàng thấy rằng sau 3 -3k vòng lặp sẽ được luồng cực đại với giá trị luồng là 3. Nếu áp dụng thuật toán FordFulkerson hay thuật toán đích hướng nguồn, thì số đỉnh xét ở mỗi vòng lặp tìm đường đi tăng luồng là (4k)2/2 = 8.k2. Như vậy độ phức tạp tính toán của thuật toán đề xuất giảm được một nửa so với thuật toán truyền thống. Kết luận Công trình đề xuất thuật toán hoán chuyển nguồn đích có trọng số tìm luồng cực đại trên mạng. Đây là thuật toán tổng quát, có thể áp dụng một cách hiệu quả cho tất cả các loại mạng. Khối lượng tính toán có thể giảm tới 2 lần so với thuật toán FordFulkerson truyền thống hoặc thuật toán đích hướng nguồn [18]. TÀI LIỆU THAM KHẢO [1] Richard Johnsonbauch: Discrete Mathematics. Macmillan Publishing Company. New York 1992. [2] Nguyễn Tô Thành, Nguyễn Đức Nghĩa: Giáo trình Toán rời rạc. Trường Đại học bách khoa Hà nội. Hà nội 1994. [3] Nguyễn Xuân Quỳnh: Cơ sở Toán rời rạc và ứng dụng. NXB Giáo dục. Hà nội 1995. [4] Oystein Ore: Theory of Graphs. American Mathematical Society. 1967. [5] Christofides Nicos : Graph Theory. Academic Press. New York London San Francisco, 1975. [6] R.G. Busacker & T.L. Saaty: Finite Graph and Networks. Mc Graw-Hill Book Company. New York - St. Louis - San Francisco - Toronto - London Sydney, 1974. 104 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 3(26).2008 [7] Kenneth H. Rosen: Discrete Mathematics and Its Applications. McGraw Hill Book Company. New York 1994. [8] Nguyễn Cam, Chu Đức Khánh: Lý thuyết đồ thị. NXB TP.HCM, 1999. [9] V.K. Balakrishnan: Theory and Problems of Graph Theory. McGRAW-HILL. 1997. [10] Trần Quốc Chiến, Giáo trình lý thuyết đồ thị, Đại học Đà Nẵng 2002. [11] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Introduction To Algorithms, the MIT Press 1999. [12] A.V.Goldberg, R.E.Tarjan, Expected performance of Dijkstra’s shortest path algorithm, Technical Report 96-070, NEC Research Institute Inc, 1996. [13] Trần Quốc Chiến – Nguyễn Thanh Tuấn, Giải thuật tìm đường đi ngắn nhất giữa hai tập đỉnh, Tạp chí Khoa học Công nghệ, Đại học Đà Nẵng, 3(7)/ 2004. [14] Trần Quốc Chiến – Nguyễn Thanh Tuấn, Đường kính hai tập đỉnh đồ thị  Khái niệm, Giải thuật và Chương trình, Hội nghị khoa học lần thứ 3 – Đại học Đà Nẵng 11/2004. [15] Trần Quốc Chiến, Thuật toán hoán chuyển nguồn đích tìm luồng cực đại (1), Tạp chí khoa học công nghệ - Đại học Đà Nẵng (submitted). [16] Trần Quốc Chiến, Thuật toán hoán chuyển nguồn đích tìm luồng cực đại (2), Tạp chí khoa học công nghệ - Đại học Đà Nẵng (submitted). [17] Trần Quốc Chiến  Nguyễn Thanh Tuấn, Một số giải thuật tìm đường đi ngắn nhất giữa hai tập đỉnh. Kỷ yếu Hội thảo quốc gia: Một số vấn đề chọn lọc của CNTT, Đà Nẵng 18-20 tháng 8 năm 2004, trang 53-59. NXB Khoa học và Kỹ thuật, Hà-Nội 2005. [18] Trần Quốc Chiến, Thuật toán đích hướng nguồn tìm luồng cực đại, (submitted). 105