Bài giảng Toán rời rạc - Chương 5: Bài toán ghép cặp

Bài toán ghép cặp Graph Matching 1 Graph Matching Bài toán ghép cặp trên đồ thị Gi ¶ sö G =( V,E ) lµ ® å thÞ v« h­íng , trong ®ã mçi c¹nh ( v,w ) ®­ îc g¸n víi mét sè thùc c ( v,w ) gäi lµ träng sè cña nã . § Þnh nghÜa . CÆp ghÐp M trªn ® å thÞ G lµ tËp c¸c c¹nh cña ® å thÞ trong ® ã kh«ng cã hai c¹nh nµo cã ® Ønh chung . Sè c¹nh trong M - kÝch th­íc , Tæng träng sè cña c¸c c¹nh trong M - träng l­îng cña cÆp ghÐp . CÆp ghÐp víi kÝch th­íc lín nhÊt ®­ îc gäi lµ cÆp ghÐp cùc ®¹i. CÆp ghÐp víi träng l­îng lín nhÊt ®­ îc gäi lµ cÆp ghÐp lín nhÊt . CÆp ghÐp ®­ îc gäi lµ ® Çy ®ñ ( hoµn h¶o ) nÕu mçi ® Ønh cña ® å thÞ lµ ® Çu mót cña Ýt nhÊt mét c¹nh trong cÆp ghÐp . 2 Graph Matching Hai bài toán Bµi to¸n cÆp ghÐp cùc ®¹i : T×m cÆp ghÐp víi kÝch th­íc lín nhÊt trong ® å thÞ G. Bµi to¸n cÆp ghÐp lín nhÊt : T×m cÆp ghÐp víi träng l­îng lín nhÊt trong ® å thÞ G. Ta h¹n chÕ xÐt c¸c bµi to¸n ® Æt ra trªn ® å thÞ hai phÝa G = ( X  Y, E ) . 3 Graph Matching Ví dụ Cặp ghép cực đại Cặp ghép không là cặp ghép Cặp ghép Cặp ghép hoàn hảo 4 Graph Matching Ví dụ Cặp ghép lớn nhất : M = {( x 1 , y 1 ), ( x 2 , y 3 ), ( x 3 , y 2 ), ( x 4 , y 4 )} Có trọng lượng 29. y 4 y 3 y 2 y 1 x 4 x 3 x 2 x 1 12 3 4 8 3 2 4 6 5 Graph Matching Bµi to¸n cÆp ghÐp cùc ®¹i  trªn ® å thÞ hai phÝa XÐt ® å thÞ hai phÝa  G = ( X  Y, E ) . CÆp ghÐp lµ tËp c¹nh mµ kh«ng cã hai c¹nh nµo cã chung ® Ønh Bµi to¸n : T×m cÆp ghÐp kÝch th­íc lín nhÊt 1 2 3 4 5 6 7 8 9 10 6 Graph Matching Qui vÒ Bµi to¸n luång cùc ®¹i 1 2 3 4 5 6 7 8 9 10 s t Mỗi cung (s, i) có kntq 1. Mỗi cung (j, t) có kntq 1. Mỗi cạnh được thay thế bởi cung có kntq 1. 7 Graph Matching Tìm luồng cực đại Luồng cực đại từ s->t có giá trị 4. Cặp ghép cực đại có kích thước 4. 1 2 3 4 5 6 7 8 9 10 s t 8 Graph Matching Bµi to¸n cÆp ghÐp cùc ®¹i  trªn ® å thÞ hai phÝa Gi ¶ sö M lµ mét cÆp ghÐp trªn G . NÕu c¹nh e = ( x, y )  M , ta nãi e lµ c¹nh cña cÆp ghÐp (hay c¹nh ® Ëm ) vµ c¸c ® Ønh x, y lµ c¸c ® Ønh ® Ëm (hay kh«ng tù do). NÕu c¹nh e = ( x, y )  M , th × ta nãi e lµ c¹nh nh¹t cßn c¸c ® Ønh x, y lµ c¸c ® Ønh nh¹t (hay tù do). 9 Graph Matching Đường tăng cặp ghép Mét ®­ êng ®i trªn ® å thÞ G mµ trong ® ã hai c¹nh liªn tiÕp lµ kh«ng cïng ® Ëm hay nh¹t sÏ ®­ îc gäi lµ ®­ êng ®i lu©n phiªn ®Ëm/nh¹t ( hay gäi ng¾n gän lµ ®­ êng ®i lu©n phiªn ) . §­ êng ®i lu©n phiªn b¾t ® Çu tõ mét ® Ønh tù do thuéc tËp X vµ kÕt thóc ë mét ® Ønh tù do thuéc tËp Y ®­ îc gäi lµ ®­ êng t¨ng cÆp ghÐp . 10 Graph Matching Định lý Berge § Þnh lý 1 (Berge C). CÆp ghÐp M lµ cùc ®¹i khi vµ chØ khi kh«ng t×m ®­ îc ®­ êng t¨ng cÆp ghÐp . CM : § iÒu kiÖn cÇn . B»ng ph¶n chøng . Gi ¶ sö M lµ cÆp ghÐp cùc ®¹i nh­ng vÉn t×m ®­ îc ®­ êng t¨ng cÆp ghÐp P  x 0 , y 1 , x 1 , y 2 , ..., x k , y 0 trong ® ã x 0 vµ y 0 lµ c¸c ® Ønh tù do. Gäi E P lµ tËp c¸c c¹nh cña ® å thÞ n»m trªn ®­ êng ®i P E P = { ( x 0 ,y 1 ) , ( y 1 , x 1 ) , ..., ( x k , y 0 ) } . DÔ thÊy sè l­îng c¹nh nh¹t trong E P lµ b»ng sè l­îng c¹nh ® Ëm cña nã céng víi 1 . §Ó ®¬n gi¶n trong phÇn d­íi ®©y ta ® ång nhÊt ký hiÖu ®­ êng ®i P víi tËp c¹nh E P cña nã . X©y dùng cÆp ghÐp M’ theo qui t¾c: M’ = ( M  P ) \ ( M  P ) . DÔ thÊy M’ còng lµ cÆp ghÐp vµ râ rµng | M’ | = | M | + 1 . M©u thuÉn thu ®­ îc ®· chøng minh ® iÒu kiÖn cÇn . 11 Graph Matching Định lý Berge § iÒu kiÖn ®ñ. Gi ¶ sö cÆp ghÐp M ch­a lµ cÆp ghÐp cùc ®¹i. Gäi M * lµ cÆp ghÐp cùc ®¹i. XÐt ® å thÞ G ’ = ( V , M  M *). Râ rµng hai c¹nh liªn tiÕp trong mçi ®­ êng ®i còng nh ­ mçi chu tr×nh trong G’ kh«ng thÓ thuéc cïng mét cÆp ghÐp M hoÆc M *. V× vËy , mçi ®­ êng ®i còng nh ­ mçi chu tr×nh trong G ’ ® Òu lµ ®­ êng lu©n phiªn M / M *. Do | M *| > | M |, nªn râ rµng lµ lu«n t×m ®­ îc Ýt nhÊt mét ®­ êng ®i lu©n phiªn M / M * mµ trong ® ã sè l­îng c¹nh thuéc M * lµ lín h¬n sè l­îng c¹nh thuéc M. §­ êng ®i ® ã chÝnh lµ ®­ êng t¨ng cÆp ghÐp trªn ® å thÞ G . § Þnh lý ®­ îc chøng minh . Chó ý: Trong chøng minh ® Þnh lý ta kh«ng sö dông tÝnh hai phÝa cña G . Do ® ã , § Þnh lý 1 lµ ® óng víi ® å thÞ v« h­íng bÊt kú . 12 Graph Matching ThuËt to¸n t×m cÆp ghÐp cùc ®¹i § Çu vµo : § å thÞ v« h­íng G = ( V, E ). B­íc khëi t¹o. X©y dùng cÆp ghÐp M trong ® å thÞ G ( cã thÓ b¾t ® Çu tõ M =  ). B­íc lÆp . KiÓm tra tiªu chuÈn tèi ­u: NÕu ® å thÞ G kh«ng chøa ®­ êng t¨ng cÆp ghÐp th × M lµ cÆp ghÐp cùc ®¹i, thuËt to¸n kÕt thóc . Ng­îc l¹i, gäi P lµ mét ®­ êng t¨ng cÆp ghÐp xuÊt ph¸t tõ ® Ønh tù do x 0  X , kÕt thóc ë ® Ønh tù do y 0  Y . T¨ng cÆp ghÐp theo qui t¾c M := ( M  P ) \ ( M  P ), råi lÆp l¹i b­íc lÆp . 13 Graph Matching Tìm đường tăng Tõ ® å thÞ G ta x©y dùng ® å thÞ cã h­íng G M = ( X  Y , E M ) víi tËp cung E M ®­ îc b»ng c¸ch ® Þnh h­íng l¹i c¸c c¹nh cña G theo quy t¾c sau : i) NÕu ( x,y )  M  E , th × ( y,x )  E M ; ii) NÕu ( x,y )  E \ M , th × ( x,y )  E M . § å thÞ G M sÏ ®­ îc gäi lµ ® å thÞ t¨ng cÆp ghÐp . DÔ thÊy : Đ­êng t¨ng cÆp ghÐp t­¬ng øng víi mét ®­ êng ®i xuÊt ph¸t tõ mét ® Ønh tù do x 0  X kÕt thóc t¹i mét ® Ønh tù do y 0  Y trªn ® å thÞ G M . Ng­îc l¹i, mét ®­ êng ®i trªn ® å thÞ G M xuÊt ph¸t tõ mét ® Ønh tù do x 0  X kÕt thóc t¹i mét ® Ønh tù do y 0  Y sÏ t­¬ng øng víi mét ®­ êng t¨ng cÆp ghÐp trªn ® å thÞ G. V× vËy , ®Ó xÐt xem ® å thÞ G cã chøa ®­ êng t¨ng cÆp ghÐp hay kh«ng , cã thÓ thùc hiÖn thuËt to¸n t×m kiÕm theo chiÒu réng trªn ® å thÞ G M b¾t ® Çu tõ c¸c ® Ønh tù do thuéc tËp X . 14 Graph Matching Thuật toán Sö dông c¸ch t×m ®­ êng t¨ng cÆp ghÐp theo nhËn xÐt võa nªu , tõ s¬ ® å tæng qu¸t dÔ dµng x©y dùng thuËt to¸n ®Ó gi¶i bµi to¸n t×m cÆp ghÐp cùc ®¹i trªn ® å thÞ hai phÝa víi thêi gian tÝnh O ( n 3 ), trong ® ã n = max (| X |, | Y |). 15 Graph Matching Cài đặt Cấu trúc dữ liệu Var A : Array[1..100,1..100] of Byte; (* Ma trận kề của đồ thi hai phía G *) Truoc , (* Ghi nhận đường đi *) Vo, (* Vo[x ]- đỉnh được ghép với x X *) Chong : Array[1..100] of Byte; (* Chong[y]-đỉnh được ghép với y Y *) N, x0, y0, Cnt : Byte; Stop : Boolean; (* Nếu (x, y)  M thì Vo[x ]=y; Chong[y ]=x. Vo[x ]=0 => x là đỉnh nhạt ; Chong[y ]=0 => y là đỉnh nhạt *) 16 Graph Matching Tìm đường tăng Procedure Tim(x:Byte ); var y: Byte; begin For y:=1 to N do If ( A[x,y ]=1)and(Truoc[y]=0)and(y0=0) then begin Truoc[y ]:=x; If Chong[y ]0 then Tim(Chong[y ]) else begin y0:=y; Exit; end; end; end; Procedure Tim_Duong_Tang ; begin Fillchar(Truoc,Sizeof(Truoc),0); y0:=0; For x0:=1 to N do begin If Vo[x0]=0 then Tim(x0); If y00 then exit; end; Stop:=true; end; 17 Graph Matching Thủ tục MaxMatching Procedure Tang; var temp: Byte; begin Inc(Cnt ); While Truoc[y0]x0 do begin Chong[y0]:=Truoc[y0]; Temp:=Vo[Truoc[y0]]; Vo[Truoc[y0]]:=y0; y0:=Temp; end; Chong[y0]:=x0; Vo[x0]:=y0; end; Procedure MaxMatching ; begin Stop:=false; Fillchar(Vo,Sizeof(Vo),0); Fillchar(Chong,Sizeof(Chong),0); Cnt :=0; While not Stop do begin Tim_duong_tang ; If not Stop then Tang; end; end; 18 Graph Matching Bµi to¸n ph©n c«ng Cã n c«ng viÖc vµ n thî . Mçi thî ® Òu cã kh ¶ n¨ng thùc hiÖn tÊt c¶ c¸c c«ng viÖc . BiÕt w ij - hiÖu qu ¶ ph©n c«ng thî i lµm viÖc j , ( i, j = 1, 2,..., n ). CÇn t×m c¸ch ph©n c«ng thî thùc hiÖn c¸c c«ng viÖc sao cho mçi thî chØ thùc hiÖn mét viÖc vµ mçi viÖc chØ do mét thî thùc hiÖn , ® ång thêi tæng hiÖu qu ¶ thùc hiÖn c¸c c«ng viÖc lµ lín nhÊt . 19 Graph Matching Qui về bài toán cặp ghép lớn nhất X©y dùng ® å thÞ hai phÝa ® Çy ®ñ G = ( X  Y , E ) X ={ x 1 , x 2 ,..., x n } t­¬ng øng víi c¸c thî , Y = { y 1 , y 2 ,..., y n }- t­¬ng øng víi c¸c c«ng viÖc . Mçi c¹nh ( x i , y j ) ®­ îc g¸n cho träng sè w ( x i , y j ) = w ij . Khi ® ã trong ng«n ng ÷ ® å thÞ , bµi to¸n ph©n c«ng cã thÓ ph¸t biÓu nh ­ sau : T×m trong ® å thÞ G cÆp ghÐp ® Çy ®ñ cã tæng träng sè lµ lín nhÊt . CÆp ghÐp nh ­ vËy ®­ îc gäi lµ cÆp ghÐp tèi ­u. 20 Graph Matching C¬ së thuËt to¸n Ta gäi mét phÐp g¸n nh·n chÊp nhËn ®­ îc cho c¸c ® Ønh cña ® å thÞ G= ( X  Y,E ) lµ mét hµm sè f x¸c ® Þnh trªn tËp ® Ønh X  Y: f: X  Y  R, tho ¶ m·n f ( x ) + f ( y )  w ( x,y ) ,  x  X,  y  Y. Mét phÐp g¸n nh·n chÊp nhËn ®­ îc nh ­ vËy dÔ dµng cã thÓ t×m ®­ îc , ch¼ng h¹n phÐp g¸n nh·n sau ®©y lµ chÊp nhËn ®­ îc f ( x ) = max { w ( x,y ): y  Y }, x  X , f ( y ) = 0 , y  Y . 21 Graph Matching Đồ thị cân bằng Gi ¶ sö cã f lµ mét phÐp g¸n nh·n chÊp nhËn ®­ îc , ký hiÖu E f = {( x,y )  E : f ( x ) + f ( y ) = w ( x,y )}. Ký hiÖu G f lµ ® å thÞ con cña G sinh bëi tËp ® Ønh X  Y vµ tËp c¹nh E f . Ta sÏ gäi G f lµ ® å thÞ c©n b»ng . 22 Graph Matching Tiêu chuẩn tối ưu § Þnh lý 2. Gi ¶ sö f lµ phÐp g¸n nh·n chÊp nhËn ®­ îc . NÕu G f chøa cÆp ghÐp ® Çy ®ñ M*, th × M* lµ cÆp ghÐp tèi ­u. Chøng minh . Gi ¶ sö G f chøa cÆp ghÐp ® Çy ®ñ M *. Khi ® ã tõ ® Þnh nghÜa G f suy ra M * còng lµ cÆp ghÐp ® Çy ®ñ cña ® å thÞ G . Gäi w ( M *) lµ träng l­îng cña M *: Do mçi c¹nh e  M * ® Òu lµ c¹nh cña G f vµ mçi ® Ønh cña G kÒ víi ® óng mét c¹nh cña M *, nªn Gi ¶ sö M lµ mét cÆp ghÐp ® Çy ®ñ tuú ý cña G , khi ® ã Suy ra w ( M *)  w ( M ). VËy M * lµ cÆp ghÐp tèi ­u. 23 Graph Matching Sơ đồ thuật toán Ta sÏ b¾t ® Çu tõ mét phÐp g¸n nh·n chÊp nhËn ®­ îc f . X©y dùng ® å thÞ G f . B¾t ® Çu tõ mét cÆp ghÐp M nµo ® ã trong G f ta x©y dùng cÆp ghÐp ® Çy ®ñ trong G f . NÕu t×m ®­ îc cÆp ghÐp ® Çy ®ñ M *, th × nã chÝnh lµ cÆp ghÐp tèi ­u. Ng­îc l¹i, ta sÏ t×m ®­ îc cÆp ghÐp cùc ®¹i kh«ng ® Çy ®ñ M '. Tõ M ' ta sÏ t×m c¸ch söa phÐp g¸n nh·n thµnh f ' sao cho M ' vÉn lµ cÆp ghÐp cña G f ' vµ cã thÓ tiÕp tôc ph¸t triÓn M ' trong G f '., v.v ... Qu ¸ tr×nh ®­ îc tiÕp tôc cho ® Õn khi thu ®­ îc cÆp ghÐp ® Çy ®ñ trong ® å thÞ c©n b»ng . 24 Graph Matching Điều chỉnh nhãn Gi ¶ sö M lµ cÆp ghÐp cùc ®¹i trong ® å thÞ G f vµ M ch­a lµ cÆp ghÐp ® Çy ®ñ cña G . Ta cÇn t×m c¸ch ® iÒu chØnh phÐp g¸n nh·n f tho ¶ m·n c¸c yªu cÇu ® Æt ra . Thùc hiÖn t×m kiÕm theo chiÒu réng tõ c¸c ® Ønh tù do trong X . Gäi S lµ c¸c ® Ønh ®­ îc th¨m trong X , cßn T lµ c¸c ® Ønh ®­ îc th¨m trong Y trong qu ¸ tr×nh thùc hiÖn t×m kiÕm . Ký hiÖu | S | > | T | (do mçi ® Ønh trong T ®¹t ®­ îc tõ mét ® Ønh nµo ® ã trong S ). . 25 Graph Matching Điều chỉnh nhãn Tõ tÝnh chÊt cña thuËt to¸n t×m kiÕm theo chiÒu réng , râ rµng , kh«ng cã c¹nh nµo tõ S ® Õn T * . §Ó söa ch÷a nh·n , chóng ta sÏ tiÕn hµnh gi¶m ® ång lo¹t c¸c nh·n trong S ®i cïng mét gi ¸ trÞ  nµo ® ã , vµ ® ång thêi sÏ t¨ng ® ång lo¹t nh·n cña c¸c ® Ønh trong T lªn  . § iÒu ® ã ®¶m b¶o c¸c c¹nh tõ S sang T ( nghÜa lµ nh÷ng c¹nh mµ mét ® Çu mót thuéc S cßn mét ® Çu mót thuéc T ) kh«ng bÞ lo¹i bá khái ® å thÞ c©n b»ng C¸c tËp S vµ T trong thùc hiÖn thuËt to¸n . ChØ vÏ c¸c c¹nh trong G f . S * T * 26 Graph Matching Điều chỉnh nhãn Khi c¸c nh·n trong S bÞ gi¶m , c¸c c¹nh trong G tõ S sang T * sÏ cã kh ¶ n¨ng gia nhËp vµo ® å thÞ c©n b»ng G f . Ta sÏ t¨ng  ® Õn khi cã thªm Ýt nhÊt mét c¹nh míi gia nhËp ® å thÞ c©n b»ng . Cã hai kh ¶ n¨ng : NÕu c¹nh míi gia nhËp ® å thÞ c©n b»ng gióp ta th¨m ®­ îc mét ® Ønh kh«ng tù do y  T * th × tõ nã ta sÏ th¨m ®­ îc mét ® Ønh ®­ îc ghÐp víi nã trong cÆp ghÐp x  S * , vµ c¶ hai ® Ønh nµy ®­ îc bæ sung vµo S vµ T t­¬ng øng , vµ nh ­ vËy viÖc t×m kiÕm ®­ êng t¨ng sÏ ®­ îc tiÕp tôc më réng . NÕu c¹nh míi gia nhËp ® å thÞ c©n b»ng cho phÐp th¨m ®­ îc mét ® Ønh tù do y  T * th × ta t×m ®­ îc ®­ êng t¨ng cÆp ghÐp , vµ kÕt thóc mét pha ® iÒu chØnh nh·n . 27 Graph Matching Điều chỉnh nhãn Ta gäi mét pha ® iÒu chØnh lµ tÊt c¶ c¸c lÇn söa nh·n cÇn thiÕt ®Ó t¨ng ®­ îc kÝch th­íc cña cÆp ghÐp M . V× sau mçi pha ® iÒu chØnh kÝch th­íc cña cÆp ghÐp t¨ng lªn 1, nªn ta ph¶i thùc hiÖn nhiÒu nhÊt n pha ® iÒu chØnh . Trong mçi pha ® iÒu chØnh , do sau mçi lÇn söa nh·n cã Ýt nhÊt hai ® Ønh míi ®­ îc bæ sung vµo danh s¸ch c¸c ® Ønh ®­ îc th¨m , nªn ta ph¶i thùc hiÖn viÖc söa nh·n kh«ng qu ¸ n lÇn . MÆt kh¸c , trong thêi gian O ( n 2 ) ta cã thÓ x¸c ® Þnh ®­ îc c¹nh nµo tõ S sang T * lµ c¹nh gia nhËp ® å thÞ c©n b»ng ( b»ng viÖc duyÖt hÕt c¸c c¹nh). Tõ ® ã suy ra ®¸ nh gi ¸ thêi gian tÝnh cña thuËt to¸n lµ O ( n 4 ). 28 Graph Matching Thuật toán B­íc 0: T×m mét phÐp g¸n nh·n chÊp nhËn ®­ îc f . B­íc 1: X©y dùng ® å thÞ c©n b»ng G f . B­íc 2: T×m cÆp ghÐp cùc ®¹i M trong G f . B­íc 3: NÕu M lµ cÆp ghÐp ® Çy ®ñ th × nã lµ cÆp ghÐp lín nhÊt cÇn t×m . ThuËt to¸n kÕt thóc . B­íc 4: Gäi S lµ tËp c¸c ® Ønh tù do trong X . Thùc hiÖn t×m kiÕm tõ c¸c ® Ønh trong S . Gäi T lµ tËp c¸c ® Ønh cña Y ®­ îc th¨m trong qu ¸ tr×nh t×m kiÕm . Bæ sung c¸c ® Ønh trong X ®­ îc th¨m trong qu ¸ tr×nh t×m kiÕm vµo S . B­íc 5: TiÕn hµnh ® iÒu chØnh nh·n f ta sÏ bæ sung ®­ îc c¸c c¹nh vµo G f cho ® Õn khi t×m ®­ îc ®­ êng t¨ng , bæ sung c¸c ® Ønh míi ®­ îc th¨m vµo S vµ T t­¬ng øng nh ­ ®· m« t¶ ë trªn . T¨ng cÆp ghÐp M vµ quay l¹i b­íc 3. 29 Graph Matching Tăng hiệu quả §Ó cã ®­ îc thuËt to¸n víi ®¸ nh gi ¸ thêi gian tÝnh tèt h¬n , vÊn ®Ò ® Æt ra lµ lµm thÕ nµo cã thÓ tÝnh ®­ îc gi ¸ trÞ  t¹i mçi lÇn söa nh·n cña pha ® iÒu chØnh mét c¸ch nhanh chãng . Ta x¸c ® Þnh ®é lÖch cña c¸c c¹nh theo c«ng thøc slack ( x , y ) = f ( x ) + f ( y ) – c ( x , y ). 30 Graph Matching Tăng hiệu quả Khi ® ã Râ rµng viÖc tÝnh trùc tiÕp  theo c«ng thøc ® ßi hái thêi gian O ( n 2 ). B©y giê , nÕu víi mçi ® Ønh trong T * ta ghi nhËn l¹i c¹nh víi ®é lÖch nhá nhÊt 31 Graph Matching Tăng hiệu quả ViÖc tÝnh gi ¸ trÞ ®é lÖch slack ( y j ) ® ßi hái thêi gian O ( n 2 ) ë ® Çu pha ® iÒu chØnh . Khi tiÕn hµnh pha ® iÒu chØnh ta cã thÓ söa l¹i tÊt c¶ c¸c ®é lÖch trong thêi gian O ( n ) do chóng bÞ thay ® æi cïng mét gi ¸ trÞ (do nh·n cña c¸c ® Ønh trong S gi¶m ® ång lo¹t ®i cïng mét gi ¸ trÞ  ). Khi mét ® Ønh x ®­ îc chuyÓn tõ S * sang S ta cÇn tÝnh l¹i c¸c ®é lÖch cña c¸c ® Ønh trong T * , viÖc ® ã ® ßi hái thêi gian O ( n ). Tuy nhiªn sù kiÖn mét ® Ønh ®­ îc chuyÓn tõ S * sang S chØ x¶y ra nhiÒu nhÊt n lÇn . Nh ­ vËy , mçi pha ® iÒu chØnh cã thÓ cµi ® Æt víi thêi gian O ( n 2 ). Do cã kh«ng qu ¸ n pha ® iÒu chØnh trong thuËt to¸n , nªn c¸ch cµi ® Æt nµy cho ta thuËt to¸n víi thêi gian tÝnh O ( n 3 ). 32 Graph Matching Ví dụ Xét bài toán với ma trận hiệu quả 33 Graph Matching Ví dụ Bắt đầu từ phép gán nhãn Đồ thị cân bằng G f CÆp ghÐp cùc ®¹i t×m ®­ îc M = {( x 1 , y 2 ), ( x 2 , y 1 ), ( x 4 , y 4 ) }. T×m kiÕm theo chiÒu réng b¾t ® Çu tõ ® Ønh tù do x 3 ta cã S = { x 2 , x 3 }, T = { y 1 } 34 Graph Matching Ví dụ TÝnh  = min { f ( x )+ f ( y )- w ( x,y ): x  { x 2 , x 3 }, y  { y 2 , y 3 , y 4 } } = 1. TiÕn hµnh söa nh·n , ta ®i ® Õn phÐp g¸n nh·n míi 35 Graph Matching Ví dụ Theo ®­ êng t¨ng cÆp ghÐp x 3 , y 3 , x 4 , y 4 ta t¨ng cÆp ghÐp M thµnh cÆp ghÐp ® Çy ®ñ M ={( x 1 , y 2 ), ( x 3 , y 1 ), ( x 2 , y 3 ), ( x 4 , y 4 )}, ® ång thêi lµ cÆp ghÐp tèi ­u víi träng l­îng w ( M ) = 4 + 2 + 5 + 2 = 13. 36 Graph Matching Cài đặt trên Pascal const maxn = 170; type data1=array [1..maxn,1..maxn] of integer; data2=array [1..2* maxn ] of integer; data3=array [1..2* maxn ] of longint ; var c: data1; px , py , q, queue: data2; a, b, f: data3; n, n2, k, u, z: integer; 37 Graph Matching Khởi tạo procedure init; var i, j: integer; begin n2:= n+n ; fillchar(f,sizeof(f),0); for i:=1 to n do for j:=1 to n do if f[i ]< c(i,j ) then f[i ]:= c(i,j ); k:=0; fillchar(px,sizeof(px),0); fillchar(py,sizeof(py),0); for i:=1 to n do for j:=1 to n do if ( py[j ]=0) and ( f[i]+f[j+n ]= c(i,j )) then begin px[i ]:=j; py[j ]:=i; inc(k ); break; end; end; 38 Graph Matching function FoundIncPath : boolean ; var dq , cq , v, w: integer; begin fillchar(q,sizeof(q),0); dq :=1; cq :=1; queue[dq ]:=u; q[u ]:=u; while dq <= cq do begin v:= queue[dq ]; inc(dq ); if v<=n then begin for w:=n+1 to n2 do if ( f[v]+f[w ]= c(v,w-n )) and ( q[w ]=0) then begin inc(cq ); queue[cq ]:=w; q[w ]:=v; end; end else if ( py[v-n ]=0) then begin FoundIncPath := true;z := v;exit ; end else begin w:= py[v-n ]; inc(cq ); queue[cq ]:=w; q[w ]:=v; end; end; FoundIncPath :=false; end; Tìm đường tăng 39 Graph Matching Tìm đỉnh tự do function FreeNodeFound : boolean ; var i:integer ; begin for i:=1 to n do if px[i ]=0 then begin u:=i; FreeNodeFound :=true; exit; end; FreeNodeFound :=false; end; 40 Graph Matching Tăng cặp ghép và Sửa nhãn procedure Tangcapghep ; var i, j: integer; ok: boolean ; begin j:=z; ok:=true; while ju do begin i:= q[j ]; if ok then begin px[i ]:= j-n ; py[j-n ]:=i; end; j:=i; ok:= not ok; end; inc(k ); end; procedure Suanhan ; var i, j: integer; d: longint ; begin d:= maxlongint ; for i:=1 to n do if q[i ]>0 then for j:=n+1 to n2 do if q[j ]=0 then if d> longint(f[i]+f[j]-c(i,j-n )) then d:= longint(f[i]+f[j]-c(i,j-n )); for i:=1 to n do if q[i ]>0 then dec(f[i],d ); for j:=n+1 to n2 do if q[j ]>0 then inc(f[j],d ); end; 41 Graph Matching Main Procedure procedure Solve; begin init; while FreeNodeFound do begin while not FoundIncPath do suanhan ; Tangcapghep ; end; end; 42 Graph Matching 43 Graph Matching