Nội dung

Chương 6 Bài toán luồng cực đại Maximum Flow Problem  v 4/6 1/1 3/3 s 3/5 3/3 w 1/1 u 2/2 t 4/7 1/9 3/5 z BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • Nguyễn Đức Nghĩa Bài toán luồng cực đại Maximum Flow Problem  v 4/6 1/1 3/3 s 3/5 3/3 w 1/1 u 2/2 t 4/7 1/9 3/5 z BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • Nguyễn Đức Nghĩa NỘI DUNG  Bài toán luồng cực đại trong mạng.  Lát cắt, Đường tăng luồng.  Định lý về luồng cực đại và lát cắt hẹp nhất.  Thuật toán Ford-Fulkerson  Thuật toán Edmond-Karp.  Các ứng dụng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 3 L. R. Ford; D. R. Fulkerson (1962). Flows in Networks. Princeton, NJ: Princeton University Press. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 4 Lester Randolph Ford, Jr (1927 ~) Lester Randolph Ford, Jr. (born September 23, 1927), son of Lester R. Ford, Sr., is an American mathematician specializing in network flow programming. His 1956 paper with D. R. Fulkerson on the maximum flow problem established the maxflow-mincut theorem. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 5 Delbert Ray Fulkerson (August 14, 1924 - January 10, 1976) Delbert Ray Fulkerson was a mathematician who codeveloped the Ford-Fulkerson algorithm, one of the most used algorithms to compute maximal flows in networks. Ph.D, Univ. of Wisconsin-Madison, 1951. In 1956, he published his famous paper on the FordFulkerson algorithm together with Lester Randolph Ford. In 1979, the renowned Fulkerson Prize was established which is now awarded every three years for outstanding papers in discrete mathematics jointly by the Mathematical Programming Society and the American Mathematical Society. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 6 Network Flows Ravindra K. Ahuja, Thomas Magnanti and James Orlin. Network Flows. Prentice Hall, 1993. 11 21 2 s 1 32 t 31 11 Toán rời rạc – Fall 2005 42 864 pages! NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 2008/5/2 Mạng và luồng trong mạng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 8 MẠNG (Network) Mạng là đồ thị có hướng G = (V,E) : Có duy nhất một đỉnh s không có cung đi vào gọi là đỉnh phát (nguồn) và duy nhất một đỉnh t không có cung đi ra gọi là đỉnh thu (đích). Mỗi cung e của G được gắn với một số không âm c(e) được gọi là khả năng thông qua của e.   Ví dụ: v 6 1 w 1 5 u t 7 3 s Toán rời rạc – Fall 2005 3 2 9 5 z NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 9 LUỒNG TRONG MẠNG Định nghĩa. Luồng f trong mạng G=(V,E) là phép gán số f(e) cho mỗi cạnh e ( f(e) được gọi là luồng trên cạnh e) thoả mãn các điều kiện: 1) Hạn chế về khả năng thông qua (Capacity Rule): Với mỗi cung e, 0  f (e)  c(e) 2) Điều kiện cân bằng luồng (Conservation Rule): Với mỗi v  s, t  f (e )  eE  ( v )  f (e) eE  ( v ) trong đó E(v) và E(v) tương ứng là tập các cung đi vào và đi ra khỏi đỉnh v. Định nghĩa. Giá trị của luồng f là val ( f )  (*)  eE  ( s ) f (e)   f ( e) eE  ( t ) (Đẳng thức (*) thu được bằng cách cộng tất cả các điều kiện cân bằng luồng.) Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 10 LUỒNG TRONG MẠNG – Ví dụ Ví dụ: v 2/6 1/1 3/3 s w 1/1 3/5 u  1/3 2/2 t 3/7 2/9 4/5 z Trong 2 số viết bên mỗi cạnh: giá trị luồng trên cạnh là số màu đỏ, số còn lại là khả năng thông qua.  Các điều kiện 1) và 2) được thoả mãn => f là luồng trên mạng.  Giá trị luồng là: 8 = f(s,v) + f(s,u) + f(s,w) = f(v,t) + f(w,t) + f(z,t) Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 11 Bài toán luồng cực đại Luồng trong mạng G được gọi là luồng cực đại nếu trong số tất cả các luồng trong mạng G nó là luồng có giá trị lớn nhất 2/6 1/3 1/1 3/3 s Bài toán tìm luồng cực đại trong mạng G được gọi là bài toán luồng cực đại v w 1/1 3/5 t 3/7 2/9 4/5 z 2/2 Luồng với giá trị 8 = 2 + 3 + 3 = 1 + 3 + 4 u v 4/6 1/1 3/3 s 3/3 1/1 3/5 w t 3/7 2/9 4/5 z 2/2 Luồng cực đại có giá trị 10 = 4 + 3 + 3 = 3 + 3 + 4 u Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 12 Mạng Mạng: G = (V, E, s, t, c) .  (V, E) = đồ thị có hướng, không có cung lặp.  Có hai đỉnh đặc biệt: s = phát/nguồn (source), t = thu/đích (sink).  c(e) = khả năng thông qua (capacity) của cung e. 10 s Capacity Toán rời rạc – Fall 2005 5 15 2 9 5 4 15 15 10 3 8 6 10 4 6 15 10 4 30 7 t NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 13 Luồng Luồng từ s đến t là hàm f: E  R thoả mãn:  Với mỗi e  E:  Với mỗi v  V – {s, t}:  f (e )  e vµo v  f (e) : - eE (v ) s kntq Capacity Luồng Toán rời rạc – Fall 2005 Flow f ( w, v)  0 5 15 0  f (e)  f (e) : (cân bằng luồng) e ra khái v eE ( v ) 2 0 9 4 4 0 15 3 4 8 40 0 6 4 30 0 f (v, w)  w : ( v ,w)  E  w : ( w, v )  E 4 10 (hạn chế kntq) 0  f(e)  c(e) 5 15 0 0 10 6 4 10 15 0 0 10 7 t NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 14 Luồng Bài toán luồng cực đại: Tìm luồng có tổng luồng trên các cạnh đi ra khỏi đỉnh phát là lớn nhất: val ( f )   f ( e)  eE  ( s ) 4 10 s kntq Luồng Toán rời rạc – Fall 2005 0 5 15 0  f (e ) eE  (t ) 2 0 9 4 4 0 15 3 4 8 40 0 6 5 15 0 0 10 6 4 10 15 0 0 10 t Giá trị = 4 4 30 0 7 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 15 Luồng Luồng có giá trị 24 trong mạng: 10 10 s kntq Luồng Toán rời rạc – Fall 2005 3 5 15 11 2 6 9 4 4 0 15 3 8 8 40 1 6 5 15 0 6 10 6 8 10 15 0 10 10 t Giá trị = 24 4 30 11 7 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 16 Luồng Luồng có giá trị 28 trong mạng: 10 10 s kntq Luồng Toán rời rạc – Fall 2005 4 5 15 14 2 9 9 4 0 1 15 3 8 8 40 4 6 5 15 0 9 10 6 9 10 15 0 10 10 t Giá trị = 28 4 30 14 7 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 17 Luồng trong mạng Mạng Đỉnh truyền thông trạm giao dịch, máy tính, vệ tinh mạng điện Cung Luồng cáp nối, cáp quang, voice, video, packets cổng, registers, processors dây dẫn dòng điện joints rods, beams, springs heat, energy thuỷ lợi hồ chứa, trạm bơm, nguồn nước đường ống dòng nước, chất lỏng tài chính nhà băng giao dịch tiền sân bay, ga tàu, giao lộ đường cao tốc, ray, đường bay hàng hoá, phương tiện, hành khách sites bonds energy cơ khí giao thông hoá học Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 18 Luồng trong mạng Mạng Đỉnh Cung Luồng telephone exchanges, cables, fiber optics, computers, satellites microwave relays voice, video, packets gates, registers, processors wires current joints rods, beams, springs heat, energy hydraulic reservoirs, pumping stations, lakes pipelines fluid, oil financial stocks, currency transactions money airports, rail yards, street intersections highways, railbeds, airway routes freight, vehicles, passengers sites bonds energy communication circuits mechanical transportation chemical Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 19 Các ứng dụng/qui dẫn  Network connectivity.       Network reliability. Bipartite matching.  Security of statistical data. Data mining.  Open-pit mining. Distributed computing.  Egalitarian stable matching.  Distributed computing.  Many many more . . . Airline scheduling. Image processing.  Project selection.  Baseball elimination. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 20 Lát cắt – Đường tăng luồng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 21 Lát cắt (Cuts) Lát cắt là cách phân hoạch tập đỉnh (S, T) sao cho s  S, t  T.  Khả năng thông qua cap(S,T) của lát cắt (S, T) là số: cap( S , T )   c(e), eS  T trong ® ã S  T :{(v, w)  E : v  S , w  T } Lát cắt nhỏ nhất (hẹp nhất) là lát cắt với kntq nhỏ nhất. 10 s 5 15 Toán rời rạc – Fall 2005 2 9 5 4 15 15 10 3 8 6 10 4 6 15 10 4 30 7 t kntq = 30 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 22 Lát cắt Lát cắt (S1, T1), S1={s,2,3,4}, T={5,6,7,t) có khả năng thông qua 62: 10 s 5 15 Toán rời rạc – Fall 2005 2 9 5 4 15 15 10 3 8 6 10 4 6 15 10 4 30 7 t cap(S1,T1)= 62 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 23 Lát cắt Lát cắt (S2, T2), S2={s,3,4,7}, T2={2,5,6,t) có khả năng thông qua 28: 10 s 5 15 Toán rời rạc – Fall 2005 2 9 5 4 15 15 10 3 8 6 10 4 6 15 10 4 30 7 t cap(S2,T2) = 28 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 24 Luồng và lát cắt Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng:  f (e)  eS  T  f (e)  eT  S  f (e)  val ( f ) eE  (s ) trong đó S  T = {(v,w)E: vS, wT} và T S = {(v,w)E: vT, w S} Giá trị = 24 s 10 10 4 5 15 10 Toán rời rạc – Fall 2005 2 6 9 4 4 0 15 3 8 8 40 0 6 4 30 10 5 15 0 6 10 6 8 10 15 0 10 10 7 t NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 25 Luồng và lát cắt Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: Giá trị = 24 s 10 10 4 5 15 10 2 6 9 4 4 0 15 3 8 8 40 0 6 4 Toán rời rạc – Fall 2005 30 10 5 15 0 6 10 6 8 10 15 0 10 10 t 7 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 26 Luồng và lát cắt Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: Giá trị = 24 s 10 10 4 5 15 10 2 6 9 4 4 0 15 15 0 6 10 3 8 8 6 8 10 40 0 6 15 0 10 10 4 Toán rời rạc – Fall 2005 5 30 10 t 7 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 27 Luồng và lát cắt Chứng minh bổ đề: Giả sử f là luồng còn (S, T) là lá cắt. Khi đó  f (e)  eS  T  f (e )  eT  S  f (e)  val ( f ) eE  (s ) CM. Cộng tất cả các ràng buộc cân bằng luồng theo mọi vS, đơn giản biểu thức ta thu được: 0  (  f ( e)  vS eE  ( v )    eE ( s )  w f (e)) eE  ( v ) v u  f (e )    f (e )   eS  T  eT  S t  f (e )   s tổng theo các cung xanh tổng theo các cung tím S T từ đó suy ra đẳng thức cần chứng minh Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 28 Luồng và lát cắt Bổ đề 2. Giả sử f là luồng, còn (S, T) là lát cắt. Khi đó, val(f) cap(S, T). CM. val ( f )     f (e)  eS  T   f ( e) eT  S S f ( e) eS  T  4 8 T t c (e) eS  T  cap(S , T ) Toán rời rạc – Fall 2005 s 7 6 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 29 Luồng cực đại và lát cắt nhỏ nhất Max Flow and Min Cut Hệ quả. Giả sử f là luồng, còn (S, T) là lát cắt. Nếu val(f) = cap(S, T), thì f là luồng cực đại còn (S, T) là lát cắt hẹp nhất. CM. Xét f’ là luồng bất kỳ và (S’,T’) là lát cắt bất kỳ. Theo bổ đề ta có val(f’)  cap(S,T) = val(f)  cap(S’,T’). 10 10 s 4 5 15 14 2 9 9 4 0 1 15 15 0 9 10 3 8 8 6 9 10 40 4 6 15 0 10 10 4 kntq của lát cắt = 28 Toán rời rạc – Fall 2005 5 30 14 t 7 Giá trị luồng = 28 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 30 Định lý về luồng cực đại và lát cắt nhỏ nhất Max-Flow Min-Cut Theorem Đinh lý (Ford-Fulkerson, 1956): Trong mạng bất kỳ, giá trị của luồng cực đại luôn bằng khả năng thông qua của lát cắt nhỏ nhất.  Proof (muộn hơn). 10 10 s 4 5 15 15 2 9 9 4 0 1 15 3 8 8 40 4 6 4 Cut capacity = 28 Toán rời rạc – Fall 2005 30 15 5 15 0 9 10 6 9 10 15 0 10 10 t 7 Flow value = 28 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 31 Ý tưởng thuật toán Thuật toán tham lam:  Bắt đầu từ luồng 0 (Luồng có giá trị = 0).  Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e).  Tăng luồng dọc theo đường đi P.  Lặp lại cho đến khi gặp bế tắc. 4 0 4 s 0 10 0 4 2 5 0 4 0 4 0 13 3 0 10 t Luồng có giá trị = 0 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 32 Ý tưởng thuật toán Thuật toán tham lam:  Bắt đầu từ luồng 0 (Luồng có giá trị = 0).  Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e).  Tăng luồng dọc theo đường đi P.  Lặp lại cho đến khi gặp bế tắc. 4 0 4 s X 0 10 10 0 4 2 5 0 4 0 4 X 0 10 13 3 X 0 10 10 t Giá trị luồng = 10 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 33 Ý tưởng thuật toán Thuật toán tham lam:  Bắt đầu từ luồng 0 (Luồng có giá trị = 0).  Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e).  Tăng luồng dọc theo đường đi P.  Lặp lại cho đến khi gặp bế tắc. 4 0 4 s 10 10 0 4 2 5 0 4 0 4 10 13 3 10 10 t Thuật toán tham lam cho luồng với giá trị 10. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 34 Ý tưởng thuật toán Thuật toán tham lam không cho lời giải tối ưu. 4 0 4 s 10 10 0 4 2 4 4 4 s Toán rời rạc – Fall 2005 10 10 0 4 10 13 3 5 4 4 4 4 2 5 0 4 TT tham lam: Giá trị luồng = 10 10 10 t Tối ưu: Giá trị luồng = 14 4 4 6 13 3 10 10 t NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 35 Đồ thị tăng luồng – Đường tăng luồng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 36 Đồ thị tăng luồng – Tập cung Mạng đã cho G = (V, E).  Luồng f(e), e  E.  Cung e = (v, w)  E. kntq v w 17 6 Luồng Đồ thị tăng luồng: Gf = (V, Ef ).  “thu lại" luồng đã gửi.  Ef = {e: f(e) < c(e) }  {eR : f(e) > 0 }.  Khả năng thông qua c(e)  f (e) nÕu e  E c f (e)  R f ( e ) nÕ u e E  Kntq v w 11 6 Kntq e = (u,v)  eR = (v,u) Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 37 Đồ thị tăng luồng - Ví dụ Đồ thị tăng luồng: Gf = (V, Ef ). c(e)  f (e) nÕu e  E c f (e)  nÕu e R  E  f (e)  Ef = {e : f(e) < c(e)}  {eR : f(e) > 0}.  cf(e) cho biết lượng lớn nhất có thể tăng luồng trên cung e.  cf(eR) cho biết lượng lớn nhất có thể giảm luồng trên cung e. 4 0 4 G s 10 10 5 0 4 0 4 2 0 4 10 13 4 t 5 4 4 Gf 3 10 10 4 4 s Toán rời rạc – Fall 2005 10 2 10 3 3 10 t NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 38 Đường tăng luồng Đường tăng luồng = đường đi từ s đến t trên đồ thị tăng luồng G f. Khả năng thông qua của đường đi P là cf (P) = min {cf (e): e  P }. 4 4 0 X 4 G s 10 10 5 4 X 0 4 4 X 0 4 2 0 4 X 4 10 X 6 13 4 5 t cf (P) = 4 4 4 Gf 3 10 10 4 4 s Toán rời rạc – Fall 2005 10 2 10 3 3 10 t NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 39 Đường tăng luồng Đường tăng luồng = đường đi từ s đến t trên đồ thị tăng luồng.  Luồng là cực đại  không tìm được đường tăng luồng??? 4 4 4 G s 10 10 5 4 4 4 4 2 4 4 6 13 4 5 t Giá trị luồng = 14 4 4 Gf 3 10 10 4 4 s 10 2 6 3 10 t 7 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 40 Định lý về luồng cực đại và lát cắt nhỏ nhất Định lý đường tăng luồng (Ford-Fulkerson, 1956): Luồng là cực đại khi và chỉ khi không tìm được đường tăng luồng. Định lý về luồng cực đại và lát cắt nhỏ nhất (Ford-Fulkerson, 1956): Giá trị của luồng cực đại bằng khả năng thông qua của lát cắt nhỏ nhất. Ta sẽ chứng minh định lý tổng hợp sau: Định lý. Giả sử f là luồng trong mạng. Ba mệnh đề sau là tương đương (i) Tìm được lát cắt (S, T) sao cho val(f) = cap(S, T). (ii) f là luồng cực đại. (iii) Không tìm được đường tăng luồng f. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 41 Chứng minh định lý Chứng minh. (i)  (ii)  Suy từ hệ quả của Bổ đề 2. (ii)  (iii)   Chứng minh bằng lập luận phản đề (contrapositive): Nếu tìm được đường tăng thì f không là luồng cực đại. Thực vậy, nếu tìm được đường tăng P, thì tăng luồng dọc theo P ta thu được luồng f’ với giá trị lớn hơn. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 42 Chứng minh định lý (iii)  (i)  Giả thiết: f là luồng và Gf không chứa đường đi từ s đến t.  Gọi S là tập các đỉnh đạt tới được từ s trong Gf.   Theo định nghĩa s  S, và theo giả thiết t  S Ta có S f(e) = 0, e  TS, f(e) = c(e), e  ST  T t Từ đó suy ra val ( f )    f (e )  eS  T   f (e) s eT  S c (e ) Mạng đã cho G eS  T  cap(S , T ) Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 43 Thuật toán Ford – Fulkerson Tăng luồng f dọc theo đường tăng P Augment(f,P) b  cf(P) FOR e  P DO IF (e  E) THEN // cạnh thuận f(e)  f(e) + b ELSE // cạnh nghịch f(eR)  f(e) – b RETURN f Thuật toán Ford-Fulkerson Ví dụ Ford_Fulkerson(G,c,s,t); FOR e  E DO // Khởi tạo luồng 0 f(e)  0 Gf  đồ thị tăng luồng f Toán rời rạc – Fall 2005 WHILE (tìm được đường tăng luồng P) DO f  augment(f, P) Sửa lại Gf NGUYỄN ĐỨC NGHĨA RETURN f Bộ môn KHMT 44 Thời gian tính Giả thiết: tất cả các khả năng thông qua là các số nguyên trong khoảng từ 0 đến C. Bất biến: mỗi giá trị luồng f(e) và mỗi khả năng thông qua c f (e) luôn luôn là số nguyên trong quá trình thực hiện thuật toán. Định lý: Thụât toán dừng sau không quá val( f *)  nC lần lặp. CM. Sau mỗi lần tăng luồng, giá trị của luồng tăng thêm ít nhất 1. Hệ quả. Thời gian tính của thuật toán F-F là O(m.n.C) Hệ quả: Nếu C = 1, thì thuật toán đòi hỏi thời gian O(mn). Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 45 Thời gian tính Giả thiết: tất cả các khả năng thông qua là các số nguyên trong khoảng từ 0 đến C. Bất biến: mỗi giá trị luồng f(e) và mỗi khả năng thông qua c f (e) luôn luôn là số nguyên trong quá trình thực hiện thuật toán. Định lý: Thụât toán dừng sau không quá val( f *)  nC lần lặp. CM. Sau mỗi lần tăng luồng, giá trị của luồng tăng thêm ít nhất 1. Hệ quả: Nếu C = 1, thì thuật toán đòi hỏi thời gian O(mn). Định lý về tính nguyên: Nếu kntq là các số nguyên, thì luôn tồn tại luồng cực đại với giá trị luồng trên các cung là các số nguyên. Chú ý: Thuật toán có thể không dừng nếu kntq là không nguyên. Hơn thế nữa thuật toán còn không hội tụ đến lời giải tối ưu. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 46 Thuật toán Ford-Fulkerson: Thời gian hàm mũ    Question: Thuật toán Ford-Fulekerson có phải là thuật toán đa thức? (thuật toán với thời gian tính bị chặn bởi đa thức bậc cố định của độ dài dữ liệu vào) Answer: Không phải. Nếu kntq lớn nhất là C thì thuật toán có thể phải thực hiện cỡ C bước lặp. Ví dụ: Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 47 Thuật toán F-F không là thuật toán đa thức 4 0 109 10 s Toán rời rạc – Fall 2005 0 109 t 109 109 0 0 2 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 48 Thuật toán F-F không là thuật toán đa thức 1 0 X 109 4 0 109 1 1X 0 s 109 0 Toán rời rạc – Fall 2005 t 109 2 X 0 1 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 49 Thuật toán F-F không là thuật toán đa thức 4 1 109 11 s Toán rời rạc – Fall 2005 0 109 t 109 109 0 1 2 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 50 Thuật toán F-F không là thuật toán đa thức 4 1 109 0 1 X 109 0 1X 1 s 109 1 X 0 Toán rời rạc – Fall 2005 t 109 2 1 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 51 Thuật toán F-F không là thuật toán đa thức 4 1 109 1 109 10 s t 109 109 1 1 2 2109 lần lặp. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 52 Ví dụ Zwick xây dựng ví dụ sau đây cho thấy thuật toán F-F có thể không dừng, nếu như khả năng thông qua là số vô tỷ s X X X 1 1 X X  X t Có 6 cung với khả năng thông qua X, 2 cung khả năng thông qua 1 và một cung khả năng thông qua  = (sqrt(5)-1)/20.618034... Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 53  Để chỉ ra thuật toán không dừng, ta có thể theo dõi khả năng thông qua của 3 cung nằm ngang của đồ thị tăng luồng trong quá trình thực hiện thuật toán. (Khả năng thông qua của 6 cung còn lại ít nhất là X-3). s X X X 1 1 X X  X t Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 54 Thực hiện thuật toán FF  Thuật toán FF bắt đầu bởi việc sử dụng đường tăng luồng trung tâm trong hình vẽ trên. Giá trị luồng tăng thêm được 1. Val(f)=1. s X X X 1 1  X X X t s  Trên đồ thị tăng luồng: Các cung nằm ngang theo thứ tự từ trái sang có khả năng rút gọn là 1, 0,  Toán rời rạc – Fall 2005 1 0  t NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 55 Thực hiện thuật toán FF s s t t B C s s X 1 1 X t X X X  X t A Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 56 Thực hiện thuật toán FF  Giả sử ở đầu lần lặp k các cung đó có khả năng thông qua là k-1, 0, k. Khi đó 1) Tăng luồng dọc theo B thêm k, kntq của chúng trở thành k+1, k, 0 2) Tăng luồng dọc theo C thêm k, kntq của chúng trở thành k+1, 0, k, 3) Tăng luồng dọc theo B thêm k+1, kntq của chúng trở thành 0, k+1, k+2, 4) Tăng luồng dọc theo A thêm k+1, kntq của chúng trở thành k+1, 0, k+2,  Sau 4 lần tăng, giá trị của luồng tăng thêm là 2(k+k+1)=2k+2  Sau 4n+1 lần tăng luồng, khả năng thông qua sẽ là 2n-2, 0, 2n-1, Khi số lần tăng luồng ra vô cùng, giá trị của luồng sẽ là  Mặc dù dễ thấy là giá trị của luồng cực đại trong mạng này là 2X+1. 2 1  2  1  4  5  7. 1  i 1  Toán rời rạc – Fall 2005 i NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 57 Chọn đường tăng luồng như thế nào? Cần hết sức cẩn thận khi lựa chọn đường tăng, bởi vì  Một số cách chọn dẫn đến thuật toán hàm mũ.  Cách chọn khôn khéo dẫn đến thuật toán đa thức.  Nếu kntq là các số vô tỷ, thuật toán có thể không dừng Mục đích: chọn đường tăng sao cho:  Có thể tìm đường tăng một cách hiệu quả.  Thuật toán đòi hỏi thực hiện càng ít bước lặp càng tốt. Chọn đường tăng với (Edmonds-Karp 1972, Dinitz 1970)  khả năng thông qua lớn nhất. (đường béo - fat path)  khả năng thông qua đủ lớn. (thang độ hoá kntq – capacity scaling)  số cạnh trên đường đi là ít nhất. (đường ngắn nhất - shortest path) Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 58 Thang độ hoá kntq (Capacity Scaling) Trực giác: chọn đường đi với kntq lớn nhất sẽ tăng giá trị luồng lên nhiều nhất.  Không cần quan tâm đến tìm đường với kntq lớn nhất.  Chọn thông số thang độ .  Gọi Gf () là đồ thị con của đồ thị tăng luồng chỉ gồm các cung có kntq ít nhất là . 4 110 4 102 1 s 122 Gf Toán rời rạc – Fall 2005 t 170 2 110 102 s t 122 170 2 Gf (100) NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 59 Thuật toán Capacity Scaling ScalingMaxFlow(V, E, s, t, c) FOR e  E, f(e)  0 q = min { k  Z : 2k  C };  = 2q WHILE (  1) Xây dựng đồ thị Gf() WHILE (tìm được đường đi P từ s đến t trong Gf()) f  augment(f, P) Hiệu chỉnh Gf()    / 2 RETURN f Pha nấc  Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 60 Tính đúng đắn của thuật toán Capacity Scaling Giả thiết. Khả năng thông qua của các cung là các số nguyên trong khoảng từ 1 đến C. Tính bất biến. Mọi luồng và khả năng thông qua trong suốt quá trình thực hiện thuật toán luôn là số nguyên. Tính đúng đắn: Nếu thuật toán kết thúc thì f là luồng cực đại. Chứng minh.  Theo tính bất biến, khi  = 1  Gf() = Gf  Pha nấc  = 1 kết thúc khi không tìm được đường tăng luồng  Vậy f là luồng cực đại. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 61 Thời gian tính của Capacity Scaling Bổ đề 1. Vòng lặp ngoài lặp 1 + log2 C lần. CM. Thoạt tiên C   < 2C, và  chỉ còn một nửa sau mỗi lần lặp. Bổ đề 2. Giả sử f là luồng tại thời điểm kết thúc pha nấc . Thế thì giá trị của luồng cực đại không vượt quá val( f ) + m . CM. Xem Silde tiếp theo Bổ đề 3. Có nhiều nhất là 2m lần tăng luồng tại mỗi pha nấc .  Gọi f là luồng tại cuối pha nấc 2 (là pha ngay trước pha nấc ).  Từ BĐ2  val(f*)  val( f ) + m (2).  Mỗi lần tăng trong pha nấc  tăng giá trị cuả val( f ) lên ít nhất . Định lý. Thuật toán Scaling max-flow kết thúc sau không quá O(m log C) lần tăng luồng và có thể cài đặt với thời gian O(m 2 log C ). Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 62 Capacity Scaling: Analysis Bổ đề 2. Giả sử f là luồng tại thời điểm kết thúc pha nấc . Thế thì giá trị của luồng cực đại không vượt quá val( f ) + m . CM.   Ta sẽ chỉ ra là khi kết thúc pha nấc  phải tìm được lát cắt (S, T) sao cho cap(S, T)  val( f ) + m . Gọi S là tập các đỉnh đạt tới được từ s trong Gf(). – rõ ràng s  S, và t  S theo định nghĩa của S val ( f )     f (e)  eS  T   eS  T S eT  S ( c ( e)   )  eS  T  f (e )      T t eT  S c (e )   eS  T eT  S  s  cap( S , T ) - mΔ Mạng đã cho Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 63 Ví dụ C = 109; q = 30; 0= 230 = 1 073 741 824; Gf(230) = (V,) 4 0 109 10 s Toán rời rạc – Fall 2005 0 109 t 109 109 0 0 2 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 64 Ví dụ Đường tăng luồng: s, 4, t 4 109 4 109 109 109 s t 109 109 2 Gf(229) Toán rời rạc – Fall 2005 109 109 1 s 0 t 109 109 0 0 2 G NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 65 Ví dụ Đường tăng luồng: s, 2, t 4 109 4 109 109 109 s t 109 109 2 Gf(229) Toán rời rạc – Fall 2005 109 109 1 s 0 t 109 109 109 109 2 G NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 66 Ví dụ Kết thúc pha nấc 229 4 10 4 10 9 109 109 9 s t 109 109 2 Gf(229) Toán rời rạc – Fall 2005 109 109 1 s 0 t 109 109 109 109 2 G NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 67 Ví dụ Gf(2k), k = 28, 27, ..., 2, 1 như nhau. Các pha nấc 2k kết thúc mà không tăng được luồng 4 10 4 10 9 109 109 9 s t 109 109 2 Gf(2k), k=28, 27, ...,,2,1 Toán rời rạc – Fall 2005 109 109 1 s 0 t 109 109 109 109 2 G NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 68 Ví dụ Trên Gf(1) không tìm được đường đi từ s đến t. Thuật toán kết thúc. 4 10 4 10 9 1 s 109 t 109 2 Gf(1) 109 109 9 109 109 1 s 0 t 109 109 109 109 2 G Do Gf(1) ≡ Gf nên trên Gf không tìm được đường đi từ s đến t. Vậy luồng đang có trong mạng là cực đại. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 69 Chọn đường tăng luồng như thế nào? Cần hết sức cẩn thận khi lựa chọn đường tăng, bởi vì  Một số cách chọn dẫn đến thuật toán hàm mũ.  Cách chọn khôn khéo dẫn đến thuật toán đa thức.  Nếu kntq là các số vô tỷ, thuật toán có thể không dừng Mục đích: chọn đường tăng sao cho:  Có thể tìm đường tăng một cách hiệu quả.  Thuật toán đòi hỏi thực hiện càng ít bước lặp càng tốt. Chọn đường tăng với (Edmonds-Karp 1972, Dinitz 1970)  khả năng thông qua lớn nhất. (đường béo - fat path)  khả năng thông qua đủ lớn. (thang độ hoá kntq – capacity scaling)  số cạnh trên đường đi là ít nhất. (đường ngắn nhất - shortest path) Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 70 Edmonds – Karp Algorithm Edmonds and Karp, JACM 1972  Nếu đường tăng được chọn là đường ngắn nhất từ s đến t, thì thời gian tính của thuật toán sẽ là O(|E|2 |V|). Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 2008/5/2 Jack Edmonds Jack Edmonds is a Canadian mathematician, regarded as one of the most important contributors to the field of combinatorial optimization. He was the recipient of the 1985 John von Neumann Theory Prize. From 1969 on, with the exception of 1991-1993, he held a faculty position at the Department of Combinatorics and Optimization at the University of Waterloo's Faculty of Mathematics. Edmonds retired in 1999. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 2008/5/2 Richard Karp, 1935~  “Reducibility Among Combinatorial Problems”, 1972  Turing Award in 1985.  Harvard University,Bachelor's degree in 1955, Master's degree in 1956, and Ph.D. in applied mathematics in 1959.  IBM's Thomas J. Watson Research Center  Professor, UC Berkeley, 1968. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 2008/5/2 Thuật toán đường tăng ngắn nhất Ý tưởng: Tìm đường tăng luồng nhờ thực hiện BFS.  Dễ thực hiện.  Đường tăng có ít cạnh nhất. ShortestAugmentingPath(V, E, s, t) FOREACH e  E f(e)  0 Gf  đồ thị tăng luồng (residual graph) WHILE (tồn tại đường tăng) tìm đường tăng P bởi BFS f  augment(f, P) hiệu chỉnh Gf RETURN f Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 74 Đường tăng ngắn nhất: Các kết quả Bổ đề 1. Trong suốt thuật toán, độ dài đường tăng ngắn nhất không khi nào bị giảm. CM sau.  Bổ đề 2. Sau nhiều nhất m đường tăng ngắn nhất, độ dài đường tăng ngắn nhất sẽ tăng ngặt. CM sau.  Định lý. Thuật toán đường tăng luồng ngắn nhất đòi hỏi thời gian tính O(m2n). CM O(m+n) thời gian để tìm đường ngắn nhất nhờ sử dụng BFS. O(m) lần tăng đối với đường đi có đúng k cung. Nếu có đường tăng thì luôn tìm được đường tăng là đơn.  1k

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.