Báo cáo nghiên cứu khoa học: "THUẬT TOÁN HOÁN CHUYỂN NGUỒN ĐÍCH TÌM LUỒNG CỰC ĐẠI (1)"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

80
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Báo cáo đề cập bài toán tìm luồng cực đại trên mạng. Các kết quả cơ bản được hệ thống và chứng minh. Thuật toán nổi tiếng Ford-Fulkerson được trình bày chi tiết kèm ví dụ minh hoạ. 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 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 (thuật toán Ford-Fulkerson tìm đường đi tăng luồng chỉ từ đỉnh nguồn). Kết quả tính toán qua các ví dụ cho thấy thuật toán hoán...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "THUẬT TOÁN HOÁN CHUYỂN NGUỒN ĐÍCH TÌM LUỒNG CỰC ĐẠI (1)"

THUẬT TOÁN HOÁN CHUYỂN NGUỒN ĐÍCH TÌM LUỒNG CỰC ĐẠI (1) SOURCE-SINK ALTERNATIVE ALGORITHM TO FIND THE 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 Báo cáo đề cập bài toán tìm luồng cực đại trên mạng. Các kết quả cơ bản được hệ thống và chứng minh. Thuật toán nổi tiếng Ford-Fulkerson được trình bày chi tiết kèm ví dụ minh hoạ. 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 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 (thuật toán Ford-Fulkerson tìm đường đi tăng luồng chỉ từ đỉnh nguồn). 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 làm giảm đáng kể khối lượng tính toán so với thuật toán Ford-Fulkerson. 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, and the main result of this work is the source-sink alternative algorithm. The idea of the algorithm is to find augmented paths simultaneously from the source and the sink vertex (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 1. Bµi to¸n luång cùc ®¹i  M¹ng (network) lµ ®¬n träng ®å cã híng G=(V, E, c) tho¶ m·n ( i) Cã duy nhÊt mét ®Ønh, gäi lµ nguån. (ii) Cã duy nhÊt mét ®Ønh, gäi lµ ®Ých. (iii) Träng sè cij cña cung (i,j) lµ c¸c sè kh«ng ©m vµ gäi lµ kh¶ n¨ng th«ng qua cña cung. (iv) §å thÞ liªn th«ng (yÕu).  Luång. Cho m¹ng G víi kh¶ n¨ng th«ng qua cij, (i,j)G. TËp c¸c gi¸ trÞ {fij  (i,j)G} gäi lµ luång trªn m¹ng G nÕu tho¶ m·n 0  fij  cij (i,j)G ( i) (ii) Víi mäi ®Ønh k kh«ng ph¶i nguån hoÆc ®Ých f f = kj ik ( k , j )G ( i , k )G §Þnh lý 1. Cho fij,(i,j)G, lµ luång trªn m¹ng G víi nguån a vµ ®Ých z. Khi ®ã  f f f f   = ia iz zi ai ( i , a )G ( i , z )G ( z , i )G ( a ,i )G Chøng minh
Gäi V lµ tËp c¸c ®Ønh. Víi c¸c ®Ønh i,j kh«ng kÒ nhau ta g¸n fij = 0. Ta cã   f   f ij ji jV iV jV iV     f   f ji   0 ij   jV iV iV        f   f ji     f iz   f zi     f ia   f ai   0 ij    iV   iV  jV \{a , z } iV iV iV iV       f iz   f zi     fia   f ai   0  iV   iV  iV iV  f f f f   = ia iz zi ai ( i , a )G ( i , z )G ( z , i )G ( a ,i )G ®pcm  Gi¸ trÞ cña luång. Cho luång f trªn m¹ng G. Gi¸ trÞ cña luång f ®îc ®Þnh nghÜa lµ ®¹i lîng f f f f   v(f) = = ia iz zi ai ( i , a )G ( i , z )G ( z , i )G ( a ,i )G  Ph¸t biÓu bµi to¸n luång cùc ®¹i. Trong thùc tÕ ta thêng gÆp bµi to¸n gäi lµ bµi to¸n t×m luång cùc ®¹i nh sau: Cho m¹ng G víi nguån a, ®Ých z vµ kh¶ n¨ng th«ng qua cij, (i,j)G. Trong sè c¸c luång trªn m¹ng G t×m luång cã gi¸ trÞ lín nhÊt. Bµi to¸n luång cùc ®¹i cã thÓ biÓu diÔn nh bµi to¸n quy ho¹ch tuyÕn tÝnh f f   v(f) = max ia ai ( i , a )G ( a ,i )G víi ®iÒu kiÖn 0  fij  cij (i,j)G f f k  V \ {a; z} = kj ik ( k , j )G ( i , k )G c V× gi¸ trÞ luång v(f)  vµ tån t¹i luång fij = 0 (i,j)G, nªn theo lý thuyÕt quy ai ( a ,i )G ho¹ch tuyÕn tÝnh tån t¹i luång cùc ®¹i.  §Þnh lý 2. Víi mçi m¹ng G=(V, E, c) lu«n lu«n tån t¹i luång cùc ®¹i.
ý tëng x©y dùng luång cùc ®¹i nh sau: xuÊt ph¸t tõ luång nµo ®ã, ta t×m ®êng ®i (kh«ng ®Þnh híng) tõ a ®Õn z cho phÐp hiÖu chØnh gi¸ trÞ luång trªn ®êng ®i ®ã sao cho luång míi cã gi¸ trÞ lín h¬n. NÕu kh«ng t×m ®îc ®êng ®i nh vËy th× ta cã luång cùc ®¹i. Gi¶ sö P = (a, u,..., i, j,..., v, z) lµ ®êng ®i kh«ng cã híng tõ a ®Õn z. NÕu c¹nh (i,j) lµ cung trªn P th× cung ®ã cïng híng víi P. Ngîc l¹i nÕu (j,i) lµ cung th× cung ®ã ngîc híng víi P. TËp c¸c cung cïng híng víi P ký hiÖu lµ P+. TËp c¸c cung ngîc híng víi P ký hiÖu lµ P. C¬ së cña thuËt gi¶i lµ ®Þnh lý sau.  §Þnh lý 3. Cho f lµ luång trªn G. Gi¶ sö P = (a, u,..., i, j,..., v, z) lµ ®êng ®i kh«ng ®Þnh híng tõ a ®Õn z tho¶ ( i) Víi mçi cung (i,j) cïng híng víi P fij < cij (ii) Víi mçi cung (i,j) ngîc híng víi P 0 < fij §Æt := min{ x  x  M} > 0, trong ®ã M lµ tËp c¸c gi¸ trÞ cij  fij, (i,j)P+ vµ fij, (i,j)P. Ta x©y dùng luång f’ nh sau (i,j)P fij fij +  (i,j)P+ f’ij:= fij   (i,j)P Khi ®ã luång f’ cã gi¸ trÞ lín h¬n gi¸ trÞ cña luång f mét lîng lµ , tøc lµ v(f’) = v(f) + . Chøng minh Theo c¸ch x©y dùng th× f’ tho¶ m·n c¸c ®iÒu kiÖn cña luång. Cã thÓ x¶y ra mét trong hai trêng hîp sau. (i) Tån t¹i cung (a,u)P+ cã f’au = fau +  Khi ®ã gi¸ trÞ    f' f =     f' f  = v(f) +  v(f') =   ai ai ia ia  ( a ,i )G  ( a ,i )G ( i , a )G ( i , a )G (ii) Tån t¹i cung (u,a)P cã f’ua = fua   Khi ®ã gi¸ trÞ
   f' f f  f'     = v(f) +   v(f’) = =   ai ai ia ia  ( i ,a )G  ( a ,i )G ( a ,i )G ( i , a )G ®pcm  ThuËt to¸n Ford-Fulkerson 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. 1. Khëi t¹o Luång xuÊt ph¸t: fij:= 0 (i,j)G §Æt nh·n cho ®Ønh nguån a(, ) T¹o lËp tËp S gåm c¸c ®Ønh ®· cã nh·n nhng cha ®îc dïng ®Ó sinh nh·n, S’ lµ tËp ®Ønh ®îc g¸n nh·n nhê c¸c ®Ønh cña tËp S S: = { a }, S’:=  2. Sinh nh·n 2.1. Chän ®Ønh sinh nh·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 cña u lµ (p, ) vµ A lµ tËp c¸c ®Ønh cha cã nh·n vµ kÒ ®Ønh sinh nh·n u. Qua bíc 2.2.  Trêng hîp S =  vµ S’  : G¸n S:= S’ vµ S’:= . Quay l¹i bíc 2.1.  Trêng hîp S =  vµ S’ = , th× kÕt thóc, luång F lµ cùc ®¹i. 2.2. G¸n nh·n cho ®Ønh cha cã nh·n vµ kÒ ®Ønh sinh nh·n  Trêng hîp A = : Quay l¹i bíc 2.1.  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 cho t nh sau: NÕu (u,t)E vµ fu,t < cu,t, ®Æt nh·n ®Ønh t lµ (u, min{, cu,t  fu,t}). NÕu (t, u)E vµ ft,u > 0, ®Æt nh·n ®Ønh t lµ (u, min{, ft,u}). NÕu t kh«ng ®îc g¸n nh·n th× quay l¹i bíc 2.2. NÕu t ®îc g¸n nh·n vµ t = z th× sang bíc hiÖu chØnh t¨ng luång 3. NÕu t ®îc g¸n nh·n vµ t  z th× bæ sung t vµo S’, S’:= S’  { t }, vµ quay l¹i bíc 2.2. 3. HiÖu chØnh t¨ng luång Gi¶ sö z cã nh·n (q, ). Ta hiÖu chØnh luång f nh sau. 3.1. Khëi t¹o j:= z, i:= q 3.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  . 3.3. TÞnh tiÕn NÕu i = a th× xo¸ tÊt c¶ nh·n cña c¸c ®Ønh trªn m¹ng, trõ ®Ønh nguån a, vµ quay l¹i bíc 2.
NÕu i  a, th× ®Æt j:= i vµ i:= p, víi p lµ thµnh phÇn thø nhÊt cña nh·n ®Ønh j. Sau ®ã quay l¹i bíc 3.2.  §Þnh lý 4. 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 Theo ®Þnh lý 1, qua mçi bíc hiÖu chØnh luång, gi¸ trÞ luång t¨ng lªn Ýt nhÊt 1 ®¬n vÞ (do cij nguyªn, kÐo theo  nguyªn d¬ng). MÆt kh¸c gi¸ trÞ luång bÞ chÆn trªn bëi tæng c¸c kh¶ n¨ng th«ng qua cña c¸c cung ®i khái ®Ønh nguån. V× vËy qua mét sè h÷u bíc qu¸ tr×nh gi¶i ph¶i kÕt thóc.  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 Quy ®ång mÉu sè c¸c gi¸ trÞ th«ng qua cij. Gi¶ sö mÉu sè chung lµ M. Theo ®Þnh lý 1, qua mçi bíc hiÖu chØnh luång, gi¸ trÞ luång t¨ng lªn Ýt nhÊt lµ 1/M. MÆt kh¸c gi¸ trÞ luång bÞ chÆn trªn bëi tæng c¸c kh¶ n¨ng th«ng qua cña c¸c cung ®i khái ®Ønh nguån. V× vËy qua mét sè h÷u bíc qu¸ tr×nh gi¶i ph¶i kÕt thóc. + Ghi chó. ThuËt to¸n sÏ ®îc chøng minh sau. + VÝ dô 1. Cho m¹ng G sau 1 2 n a z 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. Ap dông thuËt to¸n Ford-Fulkerson t×m luång cùc ®¹i cña G, ta ph¶i duyÖt qua (2.n+1)2 ®Ønh vµ 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. TÀI LIỆU THAM KHẢO
[ 1] Richard Johnsonbauch, Discrete Mathematics, Macmillan Publishing Company, New York 1992. 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 [ 2] Bách khoa Hà Nội, Hà Nội, 1994. 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. [ 3] [ 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. [ 7] Kenneth H. Rosen, Discrete Mathematics and Its Applications, McGraw Hill Book Company, New York, 1994. Nguyễn Cam, Chu Đức Khánh, Lý thuyết đồ thị, NXB TP.HCM, 1999. [ 8] [ 9] V.K. Balakrishnan, Theory and Problems of Graph Theory, McGraw Hill, 1997. Trần Quốc Chiến, Giáo trình lý thuyết đồ thị, Đại học Đà Nẵng, 2002. [10] [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. 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 [13] tập đỉnh, Tạp chí Khoa học và Công nghệ, Đại học Đà Nẵng, 3(7)/ 2004.