Đề tài Các thuật toán cơ bản về xử lý mảng trong Pascal

S¬ l­îc vÒ c¸c chñ ®Ò Sau ®©y lµ s¬ l­îc vÒ c¸c chñ ®Ò sÏ ®­îc ®Ò cËp trong phÇn nµy cña ch­¬ng tr×nh: + PhÇn c¬ së: lµ c¸c c«ng cô vµ ph­¬ng ph¸p ®­îc dïng xuyªn suèt cho tÊt c¶ c¸c ch­¬ng sau cña phÇn nµy. Nã gåm mét phÇn bµn luËn ng¾n vÒ Pascal, theo sau lµ giíi thiÖu vÒ c¸c cÊu tróc d÷ liÖu c¬ b¶n gåm m¶ng, x©u liªn kÕt, ng¨n xÕp, hµng ®îi vµ c©y. Chóng ta sÏ bµn luËn vÒ c«ng dông thùc tiÔn ®Ö quy vµ b¾t ®Çu h­íng tíi viÖc ph©n tÝch vµ tiÕp cËn thùc to¸n. + S¾p xÕp: C¸c ph­¬ng ph¸p s¾p xÕp sÏ ®­îc ph¸t triÓn, ®­îc m« t¶, ®­îc so s¸nh víi nhau. C¸c thuËt to¸n cho nhiÒu vÊn ®Ò cã liªn quan sÏ ®­îc xem xÐt gåm cã hµng ®îi ­u tiªn, phÐp chän vµ phÐp trén. Mét vµi nÒn t¶ng trong sè nµy ®­îc dïng nh­ lµ nÒn t¶ng cho c¸c thuËt to¸n kh¸c tiÕp sau trong phÇn nµy. + Xö lý chuçi: gåm mét lo¹t c¸c ph­¬ng ph¸p ®Ó ph©n tÝch c©u. C¸c ky thuËt nÐn tËp vµ mËt m· còng sÏ ®­îc kh¶o s¸t. Còng vËy, mét giíi thiÖu vÒ c¸c chñ ®Ò n©ng cao cïng ®­îc cung cÊp qua viÖc xem xÐt mét vµi bµi to¸n c¬ b¶n quan träng trong ph¹m vi cña chóng. + H×nh häc: lµ mét sù tËp hîp cã chän läc c¸c ph­¬ng ph¸p ®Ó gi¶i quyÕt c¸c bµi to¸n liªn quan ®Õn ®iÓm vµ ®­êng ( vµ c¸c ®èi t­îng h×nh häc ®¬n gi¶n kh¸c ). Chóng ta sÏ xem xÐt c¸c thuËt to¸n ®Ó t×m bao låi cña mét tËp ®iÓm, phÇn giao cña c¸c ®èi t­îng, ®Ó gi¶i bµi to¸n ®iÓm gÇn nhÊt, t×m kiÕm nhiÒu chiÒu ... + §å thÞ: Mét chiÕn l­îc tæng qu¸t ®Ó t×m kiÕm trªn c¸c ®å thÞ sÏ ®­îc ph¸t triÓn vµ ®­îc ¸p dông cho c¸c bµi to¸n liªn th«ng c¬ b¶n, gåm cã ®­êng ®i ng¾n nhÊt, c©y liªn th«ng tèi thiÓu, m¹ng vµ so khíp. Mét sù xem xÐt thèng nhÊt ®èi víi c¸c thuËt to¸n nµy chøng tá r»ng tÊt c¶ ®Òu dùa vµo mét thñ tôc vµ thñ tôc nµy phô thuéc vµo mét cÊu tróc d÷ liÖu c¬ b¶n ®· ph¸t triÓn tr­íc ®ã. + C¸c thuËt to¸n to¸n häc: gåm c¸c ph­¬ng ph¸p c¬ b¶n tõ sè häc vµ c¸c sè nguyªn, ®a thøc, vµ ma trËn còng nh­ c¸c thuËt to¸n ®Ó gi¶i quyÕt cac vÊn ®Ò to¸n häc mµ nã ph¸t sinh trong nhiÒu ng÷ c¶nh : viÖc t¹o sè ngÉu nhiªn, lìi gi¶i cña c¸c ch­¬ng tr×nh ®ång thêi, xÊp xØ d÷ liÖu, vµ lÊy tÝch ph©n. Sù nhÊn m¹nh thiªn vÒ c¸c khÝa c¹nh thuËt to¸n cña ph­¬ng ph¸p, chø kh«ng ph¶i trªn nÒn t¶ng cña to¸n häc + C¸c chñ ®Ò cao cÊp: ®­îc th¶o luËn nh»m môc ®Ých liªn hÖ c¸c chñ ®Ò trong tËp s¸ch nµy víi nhiÒu lÜnh vùc nghiªn cøu cao cÊp kh¸c. PhÇn cøng chuyªn dông, quy ho¹ch ®éng, quy ho¹ch tuyÕn tÝnh, t×m kiÕm- vÐt c¹n ... I. Sắp xếp: 1. Kh¸i niÖm: a) S¾p xÕp lµ mét qu¸ tr×nh tæ chøc l¹i mét d·y c¸c d÷ liÖu theo mét trËt tù nhÊt ®Þnh. b) Môc ®Ých cña viÖc s¾p xÕp lµ nh»m gióp cho viÖc t×m kiÕm d÷ liÖu mét c¸ch dÔ dµng vµ nhanh chãng. S¾p xÕp lµ mét viÖc lµm hÕt søc c¬ b¶n vµ ®­îc dïng réng r·i trong c¸c kÜ thuËt lËp tr×nh nh»m sö lý d÷ liÖu. c) C¸c gi¶i thuËt s¾p xÕp ®­îc ph©n chia thµnh hai nhãm chÝnh lµ: - S¾p xÕp trong (hay s¾p xÕp m¶ng). Toµn bé c¬ së d÷ liÖu cÇn s¾p xÕp ph¶i ®­îc ®­a vµo bé nhí chÝnh cña m¸y tÝnh. Do ®ã nã th­êng ®­îc sö dông khi khèi l­îng d÷ liÖu kh«ng v­ît qu¸ dung l­îng bé nhí chÝnh. Nhãm s¾p xÕp trong bao gåm c¸c ph­¬ng ph¸p : * Ph­¬ng ph¸p ®Õm. * Ph­¬ng ph¸p chÌn. * Ph­¬ng ph¸p chän. * Ph­¬ng ph¸p ®æi chæ. * Ph­¬ng ph¸p trén. - S¾p xÕp ngoµi (hay s¾p xÕp tËp tin). VËn dông trong tr­êng hîp ta ph¶i s¾p xÕp c¸c tËp tin chøa nhiÒu mÉu tin vµ mçi mÉu tin cã chiÒu dµi t­¬ng ®èi lín do ®ã ta kh«ng thÓ n¹p toµn bé vµo bé nhí chÝnh ®Ó s¾p xÕp thø tù. V× vËy ta ph¶i cã nh÷ng ph­¬ng ph¸p thÝch hîp cho viÖc s¾p xÕp tËp tin. 2. S¾p xÕp trong: a) Kh¸i niÖm: CÊu tróc d÷ liÖu thÝch hîp cho c¸c phÇn tö cÇn s¾p xÕp thø tù lµ Record. Mçi phÇn tö cã hai vïng ®Æc tr­¬ng lµ: Vïng Key ®Ó chøa kho¸ cña phÇn tö vµ ®­îc sö dông trong c¸c gi¶i thuËt t×m kiÕm, vïng info dïng ®Ó chøa ®÷ liÖu c¸c phÇn tö. Ta khai b¸o : Type Item = Record key : Integer; Info : Integer; End; Var A : Array[1..n] of Item; Kho¸ cña phÇn tö cã thÓ lµ ch÷ hoÆc sè. Yªu cÇu gi¶i thÝch lµ dïng Ýt vïng nhí vµ thêi gian thùc hiÖn nhanh. b) Ph­¬ng ph¸p ®Õm (Counting sort) * Gi¶i thÝch: Néi dung cña ph­¬ng ph¸p nµy lµ ®Õm c¸c phÇn tö cã kho¸ nhá h¬n hay b»ng kho¸ cña c¸c phÇn tö A[i]. NÕu cã j phÇn tö cã kho¸ nhá h¬n kho¸ cña phÇn tö A[i] th× phÇn tö A[i] sÏ cã vÞ trÝ theo thø tù (j+1) trong d·y ®· cã thø tù. Trong gi¶i thuËt, ta dïng m¶ng Count[i] ( i = 1, 2, .. n ) víi Count[i] cho biÕt sè phÇn tö cã kho¸ nhá h¬n kho¸ cña phÇn tö A[i]. Nh­ vËy Count[i+1] lµ vÞ trÝ cña phÇn tö A[i] trong d·y ®· cã thø tù. * VÝ dô: S¾p xÕp d·y 2 3 1 5 2 7 6 9 4 i: 1 2 3 4 5 6 7 8 Count: 2 0 4 1 6 5 7 3 Nh­ vËy phÇn tö cã kho¸ 9 ë vÞ trÝ 8 v× Count[9]=7. * ThÓ hiÖn b»ng Pascal: Procedure Count_Sort; Var Count : Array[1..n] of Integer; A : Array[1..n] of Item; i,j : Integer; Begin For i := 1 to n do Count[i] := 0; For i := n downto 2 do For j := i-1 downto 1 do If A[i].Key < A[j].Key Then Count[j] := Count[j] + 1 Else Count[i] := Count[i] + 1; For i := 1 to n do S[Count[i] + 1] := A[i]; For i := 1 to n do A[i] := S[i]; End; c) Ph­¬ng ph¸p chÌn (Insertion Sort) * Gi¶i thÝch: Néi dung cña ph­¬ng ph¸p nµy lµ gi¶ sö ta cã d·y A[1]..A[i-1] ®· cã thø tù, cã ph¶i x¸c ®Þnh vÞ trÝ thÝch hîp cña phÇn tö A[i] trong d·y A[1]..A[i - 1] b»ng ph­¬ng ph¸p t×m kiÕm tuÇn tù tõ A[i - 1] trë vÒ A[1] ®Ó t×m ra vÞ trÝ thÝch hîp cña A[i]. Ta chÌn A[i] vµo vÞ trÝ nµy vµ kÕt qu¶ lµ ®·y A[1] .. A[i] cã thø tù. Ta ¸p dông c¸ch lµm nµy víi i = 2, 3, ..., n. * VÝ dô: Ta ph¶i s¾p xÕp d·y sè: 39 50 7 37 89 13 1 62 i=2 39 50 7 37 89 13 1 62 i=3 39 50 7 37 89 13 1 62 i=4 7 39 50 37 89 13 1 62 i=5 7 37 39 50 89 13 1 62 i=6 7 37 39 50 89 13 1 62 i=7 7 13 37 39 50 89 1 62 i=8 1 7 13 37 39 50 89 62 1 7 13 37 39 50 89 62 * ThÓ hiÖn b»ng Pascal: Procedure Insertion_Sort; Var x : Item; i,j : Integer; Begin For i := 2 to n do Begin x := A[i]; A[0] := x; j := j - 1; While x.Key < A[j].Key do Begin A[j+1] := A[j]; j := j - 1; End; A[j+1] := x; End; End; d) Ph­¬ng ph¸p chän (Selection Sort) * Gi¶i thÝch: Néi dung cña ph­¬ng ph¸p nµy lµ ë b­íc thø i (i = 1, 2, 3, ..., n-1 ) ta lùa chän phÇn tö nhá nhÊt trong d·y A[i]..A[n] råi ®æi chæ phÇn tö nµy víi phÇn tö A[i]. Cuèi cïng ta sÏ cã d·y A[1]..A[n] cã thø tù. * VÝ dô: Ta ph¶i s¾p xÕp d·y sè : 39 50 7 37 89 13 1 62 i=1 39 50 7 37 89 13 1 62 i=2 1 50 7 37 89 13 39 62 i=3 1 7 50 37 89 13 39 62 i=4 1 7 13 37 89 50 39 62 i=5 1 7 13 37 89 50 39 62 i=6 1 7 13 37 50 50 39 62 i=7 1 7 13 37 39 50 89 62 1 7 13 37 39 50 89 62 * ThÓ hiÖn b»ng Pascal: Procedure Selection_Sort; Var x : Item; i,j ,k : Integer; min : Integer; Begin For i := 2 to n-1 do Begin min := A[i].Key; k := i; For i := 1 to n-1 do For j := i+1 to n do If A[j].Key < min Then Begin min := A[j].Key; k := j; End; x := A[k]; A[k] := A[i]; A[i] := x; End; End; e) Ph­¬ng ph¸p ®æi chç: Cã rÊt nhiÒu ph­¬ng ph¸p s¾p xÕp dùa trªn viÖc ®æi chç gi÷a 2 phÇn tö cña d·y. Sau ®©y chóng ta xÐt c¸c ph­¬ng ph¸p: - Bubble Sort. - Shake Sort. - Sell Sort. - Quick Sort. * Bubble Sort: * Gi¶i thÝch: Néi dung cña ph­¬ng ph¸p nµy lµ duyÖt c¸c d·y A[1], ..., A[n]. NÕu A[i].Key > A[i+1].Key (i = 1, 2, 3, ..., n-1)#0 th× ta ®æi chç A[i].Key víi phÇn tö A[i+1].Key. LËp l¹i qu¸ tr×nh duyÖt d·y nµy cho ®Õn khi kh«ng cßn viÖc ®æi chæ cña hai phÇn tö. Chó ý r»ng bÊt cø lóc nµo phÇn tö nhá nhÊt còng gÆp tr­íc tiªn. Nã nh­ nh÷ng bét khÝ nhÑ sÏ næi lªn trªn khi ®un n­íc. Sau ®ã ë thø hai phÇn tö nhá thø 2 sÏ ®­îc ®Æ vµo ®óng mét vÞ trÝ. V× vËy s¾p xÕp næi bét thao t¸c nh­ mét kiÓu s¾p xÕp chän, mÆc dï nã kh«ng lµm nhiÒu viÖc h¬n ®Ó ®­a tõng phÇn tö vµo ®óng vÞ trÝ. * VÝ dô: Ta ph¶i s¾p xÕp d·y sè: 39 50 7 37 89 13 1 62 B­íc 0 1 2 3 4 5 6 7 50 1 1 1 1 13 1 62 39 39 7 7 7 7 7 7 7 50 39 13 13 13 13 13 37 7 50 39 37 37 37 37 89 37 13 50 39 39 39 39 13 89 37 37 50 50 50 50 1 13 89 62 62 62 62 62 62 62 62 89 89 89 89 89 * ThÓ hiÖn b»ng Pascal: Procedure Bubble_Sort; Var x : Item; i,j : Integer; Begin For i := 2 to n do For j := n downto i do If A[j-1].Key > A[j].Key Then Begin x := A[j-1]; A[j-1] := A[j]; A[j-1] := x; End; End; * C¶i tiÕn: Ta nhËn thÊy r»ng nÕu ë mét lÇn duyÖt d·y nµo ®ã mµ kh«ng co s xÈy ra sù ®æi chæ gi÷a hai phÇn tö th× d·y dang s¾p ®· cã thø tù vµ gi¶i thuËt kÕt thóc. Ta cã thÓ cµi ®Æt cê ®Ó ghi nhËn ®iÒu nµy vµ cã ch­¬ng tr×nh sau: Procedure Bubble_Sort2; Var x : Item; i : Integer; flag : Boolean; Begin flag := true; While flag do Begin flag := False; For i := 1 to n-1 do If A[i].Key > A[i+1].Key Then Begin x := A[i]; A[i] := A[i+1]; A[i+1] := x; End; End; End; f* Shake Sort: * Gi¶i thÝch: Ph­¬ng ph¸p nµy lµ mét c¶i tiÕn cña ph­¬ng ph¸p Bubble Sort theo h­íng "Kh«ng nh÷ng phÇn tö nhÑ næi lªn trªn mµ c¶ phÇn tö nÆng còng xuèng d­íi" gièng nh­ khi ta rung"rung" mét c¸i nåi vµ thuËt to¸n s¾p xÕp ph¶i ®­îc ®iÒu khiÓn c¶ hai qu¸ tr×nh "næi lªn" vµ "ch×m xuèng" nµy mét c¸ch tù gi¸c. Muèn vËy ta ph¶i ghi nhí lÇn ®æi chæ cuèi cïng khi duyÖt d·y tõ trªn lªn vµ khi duyÖt tõ trªn xuoãng ®Ó quyÕt ®Þnh chu tr×nh kÕ tiÕp sÏ duyÖt tõ ®©u ®Õn ®©u. * VÝ dô: S¾p xÕp d·y sè: 39 50 7 37 89 13 1 62 d = 2 3 3 4 4 c = 8 8 7 7 4 39 1 1 1 1 50 39 39 7 7 7 50 7 39 13 37 7 37 13 37 89 37 50 37 39 13 89 13 50 50 1 13 62 62 62 62 62 89 89 89 * ThÓ hiÖn b»ng Pascal: Procedure Shake_Sort; Var x : Item; i,k,d,c : Integer; Begin d := 2; c := n; k := n; Repeat For i := c downto d do If A[i-1].Key > A[i].Key Then Begin x := A[i-1]; A[i-1] := A[i]; A[i-1] := x; k := i; End; d := d + 1; For i := d to c do If A[i-1].Key > A[i].Key Then Begin x := A[i-1]; A[i-1] := A[i]; A[i-1] := x; k := i; End; c := k-1; Until d>c; End; g. * Shell Sort: * Gi¶i thÝch: C¸c ph­¬ng ph¸p s¾p xÕp d· tr×nh bµy ë trªn nãi chung ®Òu di chuyÓn mçi phÇn tö ®i mét vÞ trÝ trong mçi b­íc. Ph­¬ng ph¸p Shell Sort dùa trªn ý t­ëng chÝnh lµ ho¸n c¸c phÇn tö ë xa nhau. §Ó lµm ®­îc viÖc ®ã ta cÇn ph¶i s¾p c¸c tËp tin ®Ó nã cã tÝnh chÊt lµ viÖc lÊy mäi phÇn tö thø h (b¾t ®Çu tõ vÞ trÝ bÊt k× nµo) còng ®Òu cho ra tËp tin ®· s¾p. Mét tËp tin nh­ vËy ®­îc gäi lµ s¾p theo ®é dµi b­íc h. Mét c¸ch nãi kh¸c, mét tËp tin d­îc s¾p theo ®é dµi b­íc h lµ tËp tin ®­îc s¾p ®éc lËp víi nhau, ®an xen vµo nhau. B»ng c¸ch s¾p xÕp theo ®é dµi b­íc h øng víi vµi gi¸ trÞ h kh¸ lín, chóng ta cã thÓ di chuyÓn c¸c phÇn tö ë nh÷ng kho¶ng c¸ch xa nhau trong m¶ng vµ v× vËy dÔ dµng h¬n ®Ó s¾p xÕp ®é dµi b­íc h c¸c gi¸ tri nhá h¬n. Dïng thñ tôc cho bÊt k× mét d·y c¸c gi¸ trÞ cña h tËn cïng lµ 1 sÏ cho ra mét tËp tin ®· s¾p xong: Dã chÝnh lµ Shell Sort. * VÝ dô: Ta ph¶i s¾p xÕp d·y sè: 39 50 7 39 89 13 1 62 B­íc 1: 4-Sort 39 50 7 39 89 13 1 62 39 13 1 37 89 50 7 62 B­íc 2: 2-Sort 39 13 1 37 89 50 7 62 1 13 7 37 39 50 89 62 B­íc 3: 1-Sort 1 13 7 37 39 50 89 62 1 7 13 37 39 50 89 62 * ThÓ hiÖn b»ng Pascal: Chó ý: - Ta dïng d·y phô chøa dé t¨ng h[i], ..., h[t] ®Ó ®iÒu khiÓn qu¸ tr×nh s¾p xÕp thø tù víi h[t]=1. ViÖc chén c¸c ®é t¨ng thÝch hîp sÏ lµm gi¶m thêi gian s¾p thø tù. - DÆt h1 = h[1] ta ph¶i khai b¸o d·y a nh­ sau: A : Array[1..n] of Item; c¸c phÇn tö A[i] (i<=0) lµ c¸c lÝnh canh. Sau ®©y ta chän: h[1] = 9, h[2] = 5, h[3] = 3, h[4] = 1 Procedure Shell_Sort; Const t = 4; Var x : Item; i,j,k,s,m: Integer; h : Array[1..t] of Integer; Begin h[1] = 9; h[2] = 5; h[3] = 3; h[4] = 1; For m := 1 to t do Begin k := h[m]; s := -k; For i := k+1 to n do Begin x := A[i]; j := i - k; If s = 0 Then s:=-k; s := s + 1; A[s] := x; While x.Key<A[j].Key do Begin A[j+k] :=A[j]; j := j - k; End; A[j+k] := x; End; End; End; h. Quick Sort: * Gi¶i thÝch: Néi dung cña ph­¬ng ph¸p nµy lµ chän phÇn tö x ë gi÷a cña d·y lµm chuÈn ®Ó so s¸nh. Ta ph©n ho¹ch d·y nµy thµnh 3 d·y con liªn tiÕp nhau: - D·y con thø nhÊt gåm phÇn tö cã kho¸ nhá h¬n x.key. - D·y con thø hai gåm c¸c phÇn tö cã kho¸ b»ng x.key. - D·y con thø ba gåm c¸c phÇn tö cã kho¸ lín h¬n x.key. Sau ®ã ¸p dông gi¶i thuËt ph©n ho¹ch nµy cho d·y con thø nhÊt nhÊt vµ d·y con thø ba, nÕu c¸c d·y con cã nhiÒu h¬n mét phÇn tö (§Ö qui). Cô thÓ lµ xÐt mét do¹n cña d·y tõ thµnh phÇn L ®Õn thµnh phÇn thø R. - LÊy gi¸ trÞ cña thµnh phÇn thø (L+R) Div 2 g¸n vµo biÕn X. - Cho i ban ®Çu lµ L. - Cho j ban ®Çu lµ R. - LËp l¹i. * Chõng nµo cßn A[i] < X th× t¨ng i. * Chõng nµo cßn A[j] > X th× gi¶m j. * i<=j th× + Ho¸n vÞ A[i] vµ A[j] + T¨ng i + Gi¶m j Cho ®Õn khi i>j + S¾p xÕp ®o¹n tõ A[L] ®Õn A[j] + S¾p xÕp ®o¹n tõ A[i] ®Õn A[R] * VÝ dô: S¾p xÕp d·y sè: 39 50 7 37 89 13 1 62 X = 37 Sau 2 lÇn ®æi chæ ta ®­îc d·y: 1 13 7 37 89 50 39 62 Xö lý d·y con: 1 13 7 Ta ®­îc: 1 7 13 Sö lý d·y con: 89 50 39 62 Ta ®­îc: 39 50 89 62 39 50 62 89 VËy d·y ®· s¾p xÕp lµ: 1 7 13 39 50 62 89 * ThÓ hiÖn b»ng Pascal: §Ó ®¬n gi¶n ta viÕt thñ tôc s¾p mét m¶ng sè nguyªn ®­îc truyÒn tham biÕn. Procedure Quick_Sort(Var A : Array[1..n] of Integer); Procedure Sort(L,R : Integer); Var i,j,Tg,X : Integer; Begin X := A[(L+R) Div 2]; i := L; j := R; Repeat While (A[i] < X) do Inc(i); While (A[j] > X) do Dec(j); If i <= j Then Begin Tg := A[i]; A[i] := A[j]; A[j] := Tg; Inc(i); Dec(j); End; Until i>j; If L < j Then Sort(L,j); If i < R Then Sort(i,R); End; Begin Sort(1,n); End; i. Ph­¬ng ph¸p trän (Merging Sort) * Gi¶i thÝch: Néi dung cña ph­¬ng ph¸p nµy lµ chia d·y sè cÇn s¾p thµnh c¸c d·y con ®· cã thø tù(goi lµ c¸c Run) vµ cã sè phÇn tö lµ luü thõa 2 sau ®ã t×m c¸ch trén dÇn chóng víi nhau thµnh c¸c Run cã thø tù chiÒu dµi t¨ng dÇn cho ®Õn khi chØ cßn mét Run th× qu¸ tr×nh s¾p xÕp kÕt thóc. Ta cã gi¶i thuËt sau ®©y ®Ó trén 2 Run x vµ y cïng thø tù cã chiÒu dµi lÇn l­ît lµ m vµ n thµnh mét run z cã chiÒu dµi lµ m + n. Procedure Merge; Var i,j,k : Integer; Begin i := 1; j := 1; k := 1; While (i <= m) and (j <= n) do Begin If X[i] < Y[j] Then Begin Z[k] := X[j]; i := i + 1; End Else Begin Z[k] := Y[j] j := j + 1; End; k := k + 1; End; While i<=m do Begin Z[k] := X[j]; k := k + 1; i := i + 1; End; While j<=n do Begin Z[k] := X[j]; k := k + 1; j := j + 1; End; End; Cô thÓ lµ nÕu ta ph¶i s¾p xÕp d·y: A[1], A[2], ...,A[n]. Ta ph¶i sö dông 2*n phÇn tö ®­îc chia thµnh 2 vïng. Vïng 1 gåm c¸c phÇn tö A[1] .. A[n], vïng 2 gåm c¸c phÇn tö A[n+1] .. A[2*n]. Ta trén c¸c Run tõ vïng nµy vµ ph©n phèi vµo vïng kia. Khi trén vµ ph©n phèi, ta trén c¸c Run ng­îc chiÒu nhau cña vïng trén vµ ph©n phèi lu©n phiªn vµo 2 ®Çu cña vïng ph©n phèi b­íc kÕ tiÕp dÔ trén h¬n. Qu¸ tr×nh s¾p xÕp sÏ kÕt thóc nÕu vïng ph©n phèi chØ cßn mét Run. Khi kÕt thóc, nÕu vïng ph©n phèi gåm c¸c phÇn tö A[n+1] .. A[2*n] th× ta chÐp d·y A[n+1] .. A[2*n] vµo d·y A[1] .. A[n] ThÓ hiÖn b»ng Pascal Procedure mergesort ( l , r : integer ); Var i , j , k , m: integer; Begin If r-l>0 then Begin m := (r+l) div 2; mergesort (l,m); mergesort (m+1,r); for i:=m downto l do b [i] := a [i]; for j:=m+1 to r do b [r+m+1-j] := a [j]; for k := l to r do if b[i] < b [j] then begin a [k] := b[i]; i:=i+1; end else begin a [k] := b[j]; j:=j-1; end; end; End; End; II. Hình học: - §iÓm lµ ®èi t­îng c¬ së trong h×nh häc. Mçi ®iÓm mµ chóng ta xÐt sau ®©y ®­îc biÓu diÔn b»ng mét cÆp sè nguyªn- to¹ ®é ®iÓm ®ã trong hÖ trôc Descart th­êng dïng. - Mét ®o¹n th¼ng lµ mét cÆp ®iÓm ®­îc nèi víi nhau bëi 1 phÇn cña ®­êng th¼ng. - Mét ®a gi¸c lµ mét danh s¸ch c¸c ®iÓm, víi hai ®iÓm c¹nh nhau ®­îc nèi bëi mét ®­êng th¼ng vµ ®iÓm ®Çu nèi víi ®iÓm cuèi t¹o thµnh mét h×nh ®ãng. Th«ng th­êng chóng ta dïng mét m¶ng ®Ó biÓu diÔn mét ®a gi¸c, dï r»ng trong mét sè tr­êng hîp ta cã thÓ dïng danh s¸ch liªn kÕt hay c¸c kiÓu kh¸c. HÇu hÕt trong c¸c ch­¬ng tr×nh chóng ta dïng kiÓu sau ®©y: Type point = record x , y : integer; end; line = record p1 , p2 : pointer; end; Var polygon : array [0 .. nmax] of point; Chó ý r»ng c¸c ®iÓm ®­îc biÓu diÔn trªn to¹ ®é nguyªn, còng cã thÓ dïng sè thùc nh­ng dïng täa ®é nguyªn th× thuËt to¸n sÏ ®¬n gi¶n h¬n nhiÒu vµ phÐp tÝnh thùc hiÖn nhanh h¬n ®¸ng kÓ. NhiÒu ®èi t­îng h×nh häc phøc t¹p sÏ ®­îc biÓu diÔn dùa trªn c¸c phÇn tö c¬ së nµy. 1/Giao c¸c ®o¹n th¼ng: Trong bµi häc s¬ cÊp ®Çu tiªn, chóng ta sÏ xÐt xem 2 ®o¹n th¼ng cã giao nhau hay kh«ng. Mét ph­¬ng ph¸p dÔ hiÓu ®Ó gi¶i quyÕt bµi to¸n nµy lµ t×m giao ®iÓm cña c¸c ®­êng th¼ng x¸c ®Þnh bëi c¸c ®o¹n th¼ng ®ã råi kiÓm tra xem nã cã n»m gi÷a hai ®iÓm ®Çu cña hai ®o¹n th¼ng ®ã hay kh«ng. Mét c¸ch dÔ dµng kh¸c lµ xem thö xem ®­êng ®i tõ ®iÓm thø nhÊt sang ®iÓm thø 2 råi sang ®iÓm thø 3 theo chiÒu kim ®ång hå hay ng­îc chiÒu kim ®ång hå: Function ccw ( p0 , p1 , p2 : pointer ) : integer; Var dx1 , dx2 , dy1 , dy2 : integer; Begin dx1:=p1.x; dy1:=p1.y-p0.y; dx2:=p2.x; dy2:=p2.y-p0.y; If dx1*dy2>dy1*dx2 then ccw:=1; If dx1*dy2<dy1*dx2 then ccw:=1; If dx1*dy2=dy1*dx2 then Begin If (dx1*dx2<0) or (dy1*dy2<0) then ccw:=-1 else If (dx1*dx1+dy1*dy1) >= (dx2*dx2+dy2*dy2) then ccw := 0 else ccw := 1; End; End; §Ó hiÓu ®­îc ch­¬ng tr×nh ho¹t ®éng nh­ thÕ nµo, ®Çu tiªn ta gi¶ sö tÊt c¶ c¸c gi¸ trÞ dx1 , dx2 , dy1 , dy2 ®Òu d­¬ng. Sau ®ã nhËn xÐt r»ng ®é dèc cña ®­êng nèi p0 víi p1 lµ dy1 / dx1, cña ®­êng nèi p0 víi p2 lµ dy2 / dx2. Do ®ã, nÕu ®é dèc cña ®­êng thø hai lín h¬n ®­êng thø nhÊt th× ®­êng ®i tõ p0 sang p1 , p2 lµ ng­îc chiÒu kim ®ång hå vµ ng­îc l¹i. So s¸nh ®é dèc h¬i bÊt tiÖn v× ®­êng cã thể theo ph­¬ng th¼ng ®øng ( dx1 hay dx2 = 0 ), chóng ta tÝnh tÝch dx1 * dx2 ®Ó tr¸nh tr­êng hîp nµy. Do ®ã ®é dèc kh«ng cÇn ph¶i d­¬ng míi ®óng. Hµm ccw tr¶ l¹i gi¸ trÞ 0 cho tr­êng hîp p2 ë gi÷a p0 vµ p1, b»ng -1 nÕu p0 ë gi÷a p2 vµ p1 vµ nÕu p1 ë gi÷a p0 vµ p2 th× chóng ta g¸n ccw = 1. Chóng ta cã thÓ dïng trùc tiÕp ccw ®Ó cµi ®Æt hµm intersect ( xÐt giao nhau ). NÕu c¶ hai ®Çu cña mét ®o¹n th¼ng ë hai bªn ®o¹n kia, nghÜa lµ cã gi¸ trÞ ccw kh¸c nhau th× chóng giao nhau: Function intersect ( l1 , l2 : line ) : boolean; Begin intersect:=(( ccw(l1.p1,l1.p2,l2.p1) * ccw(l1.p1,l1.p2,l2 .p2)) <= 0) and (( ccw(l1.p1,l1.p2,l2 .p1) * ccw(l1.p1,l1.p2,l2 .p2)) <= 0); End; Gi¶i ph¸p nµy cã vÏ ®· dïng mét sè l­îng lín tÝnh to¸n ®Ó gi¶i quyÕt mét bµi to¸n ®¬n gi¶n. Ng­êi ®äc h·y m¹nh d¹n thö t×m mét ph­¬ng ph¸p ®¬n gi¶m h¬n nh­ng chó ý ph¶i ®Çy ®ñ c¸c tr­êng hîp. 2/ §­êng khÐp kÝn ®¬n: §Ó thÊy ®­îc ®Æc ®iÓm riªng cña bµi to¸n øng víi tËp hîp c¸c ®iÓm, chóng ta xÐt bµi to¸n t×m mét ®­êng ®i, qua mét tËp hîp n ®iÓm x¸c ®Þnh, qua tÊt c¶ c¸c ®iÓm, kh«ng giao nhau vµ cuèi cïng trë vÒ ®iÓm b¾t ®Çu. §­êng ®i nh­ trªn gäi lµ ®­êng khÐp kÝn ®¬n. §Ó gi¸i quyÕt bµi to¸n nµy ta ph¶i chän mét ®iÓm lµm "®iÓm gèc". Sau ®ã tÝnh gãc t¹o b»ng c¸ch vÏ mét ®êng tõ mçi ®iÓm trong tËp hîp ®Õn gèc vÏ ra theo ph­¬ng ngang. Sau ®ã, s¾p thø tù c¸c ®iÓm theo thø tù t¨ng dÇn cña gãc t­¬ng øng, cuèi cïng nèi c¸c ®iÓm c¹nh nhau l¹i. Gäi dx , dy lµ kho¶ng c¸ch tõ ®iÓm gèc ®Õn mét ®iÓm kh¸c theo trôc hoµnh vµ tung th× gãc cÇn tÝnh trong gi¶i thuËt nµy lµ cotan dy / dx. Nh­ng hµm nµy cã vÏ chËm, v× vËy ta cã thÓ thay b»ng mét hµm kh¸c t­¬ng tù nh­ng dÔ tÝnh h¬n, ®ã lµ dy / ( dy + dx ). Ch­¬ng tr×nh sau tr¶ l¹i gi¸ trÞ tõ 0 ®Õn 360, kh«ng ph¶i lµ gãc t¹o bëi p1 vµ p2 so víi ph­¬ng ngang nh­ng cã cïng thuéc tÝnh nh­ gãc ®ã. Function theta ( p1 , p2 : pointer ) : real; Var dx , dy , ax , ay : integer; Begin dx:=p2.x - p1.x; ax:= abs(dx); dy:=p2.y - p1.y; ay:= abs(dy); If (dx=0) and (dy=0) then t:=0 else t:=dy/(ax+ay); If dx < 0 then t:=2-t else If dy < 0 then t:=4+t; theta := t*90; End; 3/ §iÓm n»m trong ®a gi¸c: TiÕp theo, chóng ta sÏ xÐt mét bµi to¸n rÊt tù nhiªn: cho mét ®iÓm vµ mét ®a gi¸c biÓu diÔn b»ng mét m¶ng c¸c ®iÓm, x¸c ®Þnh xem ®iÓm nµy n»m trong hay ngoµi ®a gi¸c. Mét gi¶i ph¸p dÔ hiÓu ®Ó gi¶i bµi to¸n nµy lµ vÏ mét ®­äan th¼ng dµi b¾t ®Çu tõ ®iÓm ®ã theo mét h­íng bÊt kú vµ ®Õm sè l­îng ®o¹n th¼ng t¹o ®­îc do nã c¾t qua ®a gi¸c. NÕu lµ sè lÏ, ®iÓm ®ã n»m trong ®a gi¸c vµ ng­îc l¹i. ®iÒu nµy dÔ thÊy nÕu chóng ta theo dâi nh÷ng g× x·y ra khi ®i tõ mét ®iÓm n»m ngoµi ®a gi¸c. Tuy nhiªn, kh«ng ph¶i chØ nh­ thÕ, bëi v× mét sè giao ®iÓm cã thÓ trïng víi ®a gi¸c, hoÆc ®o¹n th¼ng dïng ®Ó kiÓm tra trïng víi mét c¹nh cña ®a gi¸c. Nhu cÇu xö lý c¸c t×nh huèng khi c¸c ®Ønh c¶u ®a gi¸c r¬i trªn ®o¹n th¼ng kiÓm tra buéc chóng ta ph¶i lµm nhiÒu h¬n lµ chØ ®Õm sè giao ®iÓm cña c¸c c¹nh ®a gi¸c víi ®o¹n th¼ng kiÓm tra. Thùc chÊt, chóng ta muèn ®i vßng quanh ®a gi¸c, t¨ng mét biÕn ®Õm khi nµo ta di tõ mét bªn cña ®o¹n th¼ng kiÓm tra sang mét bªn kh¸c. Mét c¸ch ®Ó thùc hiÖn lµ ®¬n gi¶n bá qua c¸c ®iÓm r¬i trªn ®o¹n th¼ng kiÓm tra, nh­ trong ch­¬ng tr×nh sau ®©y: Function inside (t:point):boolean; Var count,i,j:integer; lt,lp:line; Begin count:=0; j:=0; p[0]:=p[N]; p[N+1]:=p[1]; lt.p1:=t; lt.p2:=t; lt.p2.x:=maxint; For i:=1 to N do Begin lp.p1 := p [i]; lp.p2 := p [i]; If not intersect (lp,lt) then Begin lp . p2 := p [j]; j := i; If intersect (lp,lt) then count := count + 1; End; End; inside := ((count mod 2) = 1); End; Ch­¬ng tr×nh nµy dïng ®­êng th¼ng kiÓm tra theo ph­¬ng ngang ®Ó dÔ tÝnh to¸n. BiÕn j ®­îc dïng ®Ó l­u tr÷ chØ sè cña ®iÓm cuèi cïng cña ®a gi¸c mµ kh«ng n»m trªn ®o¹n kiÓn tra. Ch­¬ng tr×nh gi¶ sö r»ng p [ 1 ] lµ ®iÓm cã täa ®é x nhá nhÊt trong sè tÊt c¶ c¸c ®iÓm cã täa ®é y nhá nhÊt, v× vËy nÕu p [ 1 ] n»m trªn ®o¹n kiÓm tra th× p [ 0 ] kh«ng thÓ. Cïng mét ®a gi¸c cã thÓ biÓu diÔn b»ng N m¶ng kh¸c nhau, nh­ng ®iÒu nµy cho thÊy ¸p dông mét quy luËt chuÈn cho p [ 1 ] ®«i khi l¹i tiÖn lîi. NÕu ®iÓm kÕt tiÕp trªn ®a gi¸c mµ kh«ng n»m trªn ®o¹n kiÓm tra, ë cïng mét phÝa nh­ ®iÓm thø j ®èi víi ®o¹n kiÓm tra th× chóng ta kh«ng cÇn ph¶i t¨ng biÕn ®Õm giao ®iÓm ( count ). Ng­îc l¹i, chóng ta cã ®­îc mét giao ®iÓm. NÕu ®a gi¸c chØ cã 3 hay 4 c¹nh, th­êng gÆp trong nhiÒu øng dông th× mét ch­¬ng tr×nh phøc t¹p nh­ vËy sÏ kh«ng ®­îc sö dông, mét thñ tôc ®¬n gi¶n ®Æt c¬ së trªn viÖc gäi ccw sÏ thÝch hîp h¬n. Mét tr­êng hîp ®Æc biÖt quan träng kh¸c l¸ ®èi víi ®a gi¸c låi, ®­îc xÐt trong ch­¬ng kÕ, nã cã ®Æc ®iÓm lµ kh«ng cã ®o¹n kiÓm tra nµo cã h¬n 2 giao ®iÓm víi ®a gi¸c. Trong tr­êng hîp nµy, mét thñ tôc nh­ t×m nhÞ ph©n cã thÓ dïng ®Ó x¸c ®Þnh trong O ( log N ) b­íc ®Ó biÕt ®­îc ®iÓm cã ë bªn trong hay kh«ng. III. Cặp ghép: 1. Giíi thiÖu chung: XÐt hai t¹p h÷u h¹n X, Y gåm n phÇn tö: X= { x1, x2, ... xn } Y= { y1, y2, ... yn } CÆp phÇn tö (x, y) víi x thuéc X, y thuéc Y ®­îc gäi lµ mét cÆp ghép. Hai cÆp ghép (x , y) vµ (x1, y1) ®­îc gäi lµ rêi nhau nÕu x # x1 vµ y # y1. TËp M gåm c¸c cÆp ghÐp rêi nhau ®­îc gäi lµ mét tËp cÆp ghÐp. Th«ng th­êng bµi to¸n x©y dùng c¸c cÆp ghÐp ®­îc tiÕp cËn theo 2 h­íng: HoÆc tho¶ m·n mét sè ®iÒu kiÖn ghÐp cÆp nµo ®Êy, khi ®ã ng­êi ta quan t©m ®Õn kh¶ n¨ng ghÐp cÆp tèi ®a, hoÆc l­îng ho¸ viÖc ghÐp cÆp, khi ®ã ng­êi ta quan t©m ®Õn viÖc tèi ­u ho¸ theo c¸c gi¸ trÞ ®· l­îng ho¸. V× sè tËp cÆp ghÐp lµ h÷u h¹n, nªn cã mét ph­¬ng ph¸p x©y dùng tÇm cì lµ thö tÊt c¶ c¸c kh¶ n¨ng. Tuy nhiªn, sè kh¶ n¨ng nh­ vËy rÊt lín (cì n!). V× thÕ, ng­êi ta quan t©m ®Õn viÖc t×m kiÕm nh÷ng thuËt gi¶i h÷u hiÖu, dÔ cµi ®Æt ch­¬ng tr×nh vµ cã tÝnh kh¶ thi cao. Bµi to¸n nµy nh»m giíi mét sè mô h×nh ghÐp cÆp nh­ vËy. 2. CÆp ghÐp ®Çy ®ñ tèi ­u a. Giíi thiÖu bµi to¸n Mét cÆp ghÐp, sao cho tÊt c¶ c¸c phÇn tö cña X vµ Y ®Òu ®­îc ghÐp cÆp (nghÜa lµ cã ®ñ n cÆp víi n lµ sè phÇn tö cña X vµ Y), ®­îc gäi lµ ghÐp cÆp ®Çy ®ñ. Râ rµng mçi song ¸nh p: X -> Y x¸c ®Þnh mét tËp ghÐp cÆp ®Çy ®ñ, trong ®ã mçi cÆp ghÐp ®­îc viÕt d­íi d¹ng (x , p(x)), x thuéc X. Tõ ®ã suy ra cã tÊt c¶ n! c¸ch x©y dùng tËp cÆp ghÐp ®Çy ®ñ kh¸c nhau. Víi c¸c tËp cÆp ghÐp ®Çy ®ñ, mét c¸ch tù nhiªn, ng­êi ta quan t©m ®Õn tËp cÆp ghÐp "tèt nhÊt" theo mét nghÜa nµo ®ã ®· ®­îc l­îng ho¸. TËp cÆp ghÐp nµy ®­îc gäi lµ "TËp cÆp ghÐp ®Çy ®ñ vµ tèi ­u", Bµi to¸n t×m cÆp ghÐp ®Çy ®ñ tèi ­u cã nhiÒu m« h×nh øng dông thùc tÕ. Mét trong nh÷ng m« h×nh nµy ng­êi ta quan t©m dÕn viÖc ghÐp cÆp sao cho cã hiÖu qña nhÊt. §Ó l­îng ho¸ viÖc ghÐp cÆp mçi phÇn tö x thuéc X víi mét phÇn tö y thuéc Y, ng­êi ta ®­a vµo ma trËn träng sè Cij (i,j = 1, 2, .., n) víi ý nghÜa Cij m« t¶ hiÖu qu¶ cña viÖc ghÐp xi víi þ. Bµi to¸n ®­îc ®Æt ra lµ: X©y dùng mét tËp cËp ghÐp ®Çy dñ cã tæng hiÖu qu¶ lín nhÊt. Bµi to¸n võa nªu th­êng ®­îc ph¸t biÓu d­íi d¹ng mét m« h×nh thùc tÕ lµ bµi to¸n ph©n c«ng d­íi ®©y: Bµi to¸n ph©n c«ng: Cã n ng­êi vµ n c«ng viÖc. BiÕt Cij lµ sè tiÒn lµm ra nÕu giao c«ng viÖc j cho ng­êi thø i thùc hiÖn. H·y t×m c¸ch ph©n c«ng mçi ng­êi mçi viÖc ®Ó tæng sè tiÒn lµm ra lµ lín nhÊt. b. Ph­¬ng ph¸p tham lam §©y lµ mét ph­¬ng ph¸p gÇn ®óng, xuÊt ph¸t tõ viÖc chän tèi ­u trong tõng b­íc v× thÕ nã kh«ng ®¶m b¶o ®­îc tÝnh tèi ­u toµn côc. Tuy nhiªn, nã cho ngay mét ph­¬ng ¸n, gÇn ®óng víi ph­¬ng ¸n tèi ­u: 1. XuÊt ph¸t tõ b¶n Cij ®ãng vai trß b¶ng hiÖn hµnh. TËp cÆp ghÐp ®­îc khëi g¸n b»ng rçng. 2. T×m dßng i cét j ra khái b¶ng hiÖn hµnh vµ lÆp l¹i b­íc thø 2 cho ®Õn khi b¶ng rçng. 3. Xo¸ dßng i, cét j ra khái b¶ng hiÖn hµnh vµ lÆp l¹i b­íc 2 cho ®Õn khi b¶ng rçng. ThÝ dô, xÐt b¶ng träng sè víi n = 4: 2 5 1 6 8 7 6 4 6 9 3 5 5 1 2 7 c¸c cÆp ghÐp ®­îc chän lÇn l­ît lµ (1 8 9 7) (x3, y2), (x2, y1), (x4, y4), (x1, y3). Víi ph­¬ng ¸n trªn ta cã tæng träng sè lµ 25. Tr­êng hîp nµy c¸c c¸ch ghÐp t×m ®­îc ch­a ph¶i lµ cÆp ghÐp ®Çy ®ñ vµ tèi ­u( xem l¹i vÝ dô nµy ë d­íi). c. ĐÞnh lý c¬ së ViÖc x©y dùng tËp cÆp ghÐp ®Çy ®ñ tèi ­u dùa vµo dÊu hiÖu nhËn biÕt mét tËp ghÐp ®Çy ®ñ khi nµo lµ tèi ­u. DÜ nhiªn viÖc thö dÊu hiÖu nµy kh«ng ph¶i lµ viÖc so s¸nh víi tÊt c¶ c¸c cÆp ghÐp, mµ ph¶i ®­îc mang tÝnh kh¶ thi. §Ó lam ®iÒu nµy ng­êi ta x©y dùng hµm sè F, x¸c ®Þnh trªn tËp cña c¸c phÇn tö Xi thuéc X , Yj thuéc Y , mµ ta sÏ gäi lµ nh·n cña c¸c phÇn tö . Nh·n F ®­îc gäi lµ nh·n chÊp nhËn ®­îc nÕu thâa m·n bÊt ®¼ng thøc F(Xi)+F(Yj)>=Cij víi mäi Xi thuéc X , Yj thuéc Y . TËp cÆp ghÐp M vµ nh·n F ®­îc gäi lµ t­¬ng thÝch víi nhau nÕu tho· m·n ®¼ng thøc F(Xi)+F(Yj)=Ci víi mäi (Xi,Yj)thuéc M , Noi riªng , tËp cÆp ghÐp rçng ®­îc xem nh­ t­¬ng thÝch víi mäi nh·n . §Þnh lý: TËp cÆp ghÐp ®Çy ®ñ M* lµ tèi ­u khi tån t¹i nh·n F chÊp nhËn ®­îc lµ t­¬ng thÝch víi nã . Dùa vµo ®Þnh lý võa chøng minh , ng­êi ta cã 2 h­íng tiÕp cËn cÆp ghÐp ®Çy ®ñ tèi ­u : * Mét lµ , xuÊt ph¸t tõ cÆp ghÐp ®Çy ®ñ M nµo ®ã , ng­êi ta x©y dùng mét nh·n F t­¬ng thÝch víi M . NÕu F chÊp nhËn ®­îc , th× M tèi ­u . Tr¸i l¹i , ng­êi ta ®iÒu chØnh M cho ®Õn khi F t­¬ng thÝch lµ chÊp nhËn ®­îc khi ®ã M lµ téi ­u . * Hai lµ , xuÊt ph¸t tõ mét nh·n F chÊp nhËn ®­îc vµ mét cÆp ghÐp M bÊt kú t­¬ng øng víi F ( cã thÓ rçng ) , ng­êi ta t¨ng dÇn sè cÆp ghÐp M sao cho vÉn ®¶m b¶o tim ®­îc nh·n F t­¬ng thÝch víi M chÊp nhËn ®­îc . Qu¸ tr×nh t¨ng sÏ kÕt thóc khi M ®Çy ®ñ vµ khi ®ã M lµ tèi ­u . D­íi ®©y tr×nh bÇy mét thuËt to¸n tim cÆp ghÐp ®Çy ®ñ téi ­u theo h­íng thø hai . d. ThuËt to¸n Kuhn-Munkes Néi dung chñ yÕu cña ph­¬ng ph¸p lµ xuÊt ph¸t tõ mét tËp cÆp ghÐp nµo ®ã ch­a ®©ú ®ñ (co thÓ lËp hîp rçng ) , ta t¨ng dÇn sè cÆp ghÐp sao cho khi trë thµnh ®Çy ®ñ , c¸c cÆp ghÐp thu ®­îc còng ®ång thêi tho· m·n tÝnh tèi ­u . Cã nhiÒu h×nh thøc tr×nh bµy ph­¬ng ph¸p nµy . D­íi ®©y lµ c¸ch tr×nh bÇy trªn ng«n ng÷ ®å thÞ víi c¸c thao t¸c t×m kiÕm . C¸ch nµy cã nhiÒu ­u ®iÓm : trùc gi¸c , dÔ ph¸p biÓu , dÓ chøng minh vµ ®Æc biÖt , dÓ cµi ®Æt ch­¬ng tr×nh v× viÖc t×m d­êng trªn ®å thÞ lµ mét thao t¸c c¬ b¶n vµ quen thuéc . Gi¶ sö F lµ mét nh·n chÊp nhËn ®­îc vµ M mét tËp cÆp ghÐp t­¬ng thÝch víi F . Xem c¸c phÇn tö cña X vµ Y nh­ nh÷ng ®Ønh cña ®å thÞ cã hai h­íng (mét phÝa X mét phÝa Y ). C¸c c¹nh cña ®å thÞ nµy ®­îc x¸c ®Þnh tuú thuéc néi dung cña nh·n F vµ tËp cÆp ghÐp M nh­ sau : - Mçi cÆp phÇn tö Xi thuéc X , Yj thuéc Y tho· m·n ®¼ng thøc F(Xi)+F(Yj)=Cij sÏ x¸c ®Þnh mét c¹nh cña ®å thÞ , - C¹nh nµy cã h­íng tõ X sang Y nÕu cÆp (Xi ,Yj) kh«ng thuéc M gäi (lµ c¹nh thuËn) vµ ng­îc l¹i , cã xu h­íng tõ Y sang X nÕu cÆp (Xi ,Yj) thuéc M (gäi lµ c¹nh nghÞch). §å thÞ x©y dùng theo quy t¾c võa nªu ®­îc gäi lµ ®å thÞ c©n b»ng t­¬ng øng víi F , M vµ ®­îc ký hiÖu lµ G(F,M). B­íc 1: Khëi t¹o : X©y dùng ®­îc nh·n F chÊp nhËn ®­îc nh­ sau : F( xi ) := Max {C[ i , j ] , yj thuéc Y } F( yj ) := 0 yj thuéc Y M lµ tËp cÆp ghÐp rçng . Chó ý r»ng , cã thÓ xuÊt ph¸p tõ bÊt kú nh·n F nµo chÊp nhËn ®­îc vµ bÊt ký mét tËp cÆp ghÐp M nµo t­¬ng øng víi F. B­íc 2: T×m ®Ønh tù do thuéc X: T×m ®Ønh u thuéc X ch­a ®­îc ghÐp cÆp. NÕu kh«ng cßn ®Ønh nµo cña X ch­a ghÐp cÆp th× kÕt thóc, tËp cÆp ghÐp M hiÖn hµnh lµ tËp cËp ghÐp tèi ­u. Tr¸i l¹i sang b­íc tiÕp theo. B­íc 3: XuÊt ph¸t tõ u, thùc hiÖn viÖc t×m kiÕm trªn ®å thÞ G(F, M). KÕt qu¶ t×m ®­îc cã hai tr­êng hîp sau: - NÕu ®Õn ®­îc mét ®Ønh z thuéc Y ch­a ghÐp cÆp th× ghi nhËn ®­êng ®i tõ u -> z (gäi lµ ®­êng t¨ng cÆp ghÐp) vµ chuyÓn sang b­íc t¨ng cÆp ghÐp trªn ®­êng ®i nµy. - NÕu kh«ng tån t¹i mét ®­êng ®Þ nh­ vËy th× chuyÓn sang b­íc söa nh·n F. B­íc 4: T¨ng cÆp ghÐp: §iÒu chØnh M nh­ sau: - Gi÷ nguyªn nh÷ng cÆp ghÐp cña M n»m ngoµi ®­êng t¨ng cÆp ghÐp - Trªn ®­êng t¨ng cÆp ghÐp, thay ®æi nh÷ng cÆp ghÐp cña M (c¹nh ng­îc) b¨ng nh÷ng cÆp ghÐp c¹nh thuËt (vÒ mÆt ®å thÞ nghÜa lµ ®æi chiÒu c¸c c¹nh trªn ®­êng t¨ng cÆp ghÐp) Sau b­íc nµy, sè cÆp ghÐp thuéc M ®­îc t¨ng them 1 vµ ®Ønh u trë thµnh ®· ghÐp cÆp, ngoµi ra, tÝnh t­¬ng thÝch gi÷a F vµ M vÉn ®­îc b¶o toµn. Sau ®ã quay l¹i b­íc 2 ®Ó thùc hiÖn viÖc söa nh·n tù do kh¸c. B­íc 5: Söa nh·n: Gäi S lµ tËp c¸c ®Ønh thuéc X vµ T lµ tËp cÆp ghÐp thuéc Y ®· ®­îc ®i trong qu¸ tr×nh t×m ®­êng ®i ë b­íc 3. ViÖc söa nh·n ®­îc tiÕn hµnh nh­ sau: - T×m l­îng söa nh·n: d := Min { F(xi) + F(yj) - C[i,j] , yj thuéc T} - G¸n l¹i nh·n: F(xi) := F(xi) - d víi xi thuéc S F(yj) := F(yj) + d víi yj thuéc T Sau ®ã, quay trë l¹i b­íc 3 ®Ó lÆp l¹i t×m ®­êng t¨ng cÆp ghÐp (víi ®Ønh xuÊt ph¸t u cò vµ nh·n F míi). Chó ý r»ng, sau khi thay ®æi, nh·n F vÉn gi÷ nguyªn tÝnh chÊp nhËn ®­îc vµ tÝnh t­¬ng thÝch M. Ngoµi ra cã thªm Ýt nhÊt mét cÆp (xi, yj) tho¶ m·n F(xi) + F(yj) = C[i,j], v× thÕ, sau mét sè lÇn ®æi s÷a nh·n, ch¾c ch¾n sÏ t¨ng ®­îc cÆp ghÐp. D­íi ®©y lµ s¬ ®å minh ho¹ c¸c b­íc ®· nªu: (S¬ ®å) NhËn xÐt r»ng, khi t¨ng cÆp ghÐp, c¸c ®Ønh ®· ®­îc tiÕn ghÐp cÆp råi kh«ng bao giê trë thµnh tù do, v× thÕ viÖc t×m ®Ønh tù do cã thÓ ®­îc tiÕn hµnh tuÇn tù. Qu¸ tr×nh t×m tËp cÆp ghÐp ®Çy ®ñ tèi ­u cã thÓ ®­îc m« pháng qua do¹n ch­¬ng trinh sau: FOR IF THEN BEGIN WHILE NOT DO END; e. VÝ dô Quay trá l¹i thÝ dô tr­íc. Nh·n F chÊp nhËn ban ®Çu lµ: F 0 0 0 0 6 2 5 1 6 8 8 7 6 4 9 6 9 3 5 7 5 1 2 7 XuÊt ph¸t tõ cÆp ghÐp M rçng, lÇn l­ît t¨ng cÆp ghÐp cho c¸c ®Ønh tù do x1, x2, x3, ta nhËn ®­îc M={ (x1, y4), (x2, y1), (x3, y2) } vµ ®å thÞ G(F,M) t­¬ng øng: ViÖc t×m ®­êng t¨ng cÆp ghÐp t­¬ng ®èi víi ®Ønh tù do x4 kh«ng t×m thÊy vµ cho ta c¸c tËp S = {x1, x4}, T ={y4). TiÕn hµnh s÷a nh·n trªn c¸c tËp cÆp ghÐp nµy, ta ®­îc d=1 vµ nh·n F míi lµ F 0 0 0 1 5 2 5 1 6 8 8 7 6 4 9 6 9 3 5 6 5 1 2 7 nh·n F nµy thªm ®­îc c½p1, y2 tho¶ m·m F(x1) + F(x2) = C[1,2] vµ ta ®­îc ®å thÞ G(F,M): §­êng t¨ng cÆp ghÐp ®èi víi x4 vÉn kh«ng tåm t¹i. Tuy nhiªn S vµ T ®· ®­îc më réng thªm: S ={x1, x3, x4} vµ T = {y2, y4} vµ l­îng nh·n ®­îc sña trªn c¸c tËp nµy lµ d = 1: F 0 1 0 2 4 2 5 1 6 8 8 7 6 4 8 6 9 3 5 5 5 1 2 7 LÇn nµy F thªm ®­îc cÆp x4, y1 tho¶ m·m F(x4) + F(y1) = C[4,1] vµ ®­îc ®å thÞ G(F,M): ViÖc t×m kiÕm vÉn ch­a kÕt thóc vµ cho S = {x1, x2, x3, x4}, T = {y1, y2, y4}. L­îng nh·n ®­îc söa lÇn nµy lµ 2, vµ ta nhËn ®­îc: F 2 3 0 4 2 2 5 1 6 6 8 7 6 4 6 6 9 3 5 3 5 1 2 7 cïng víi ®å thÞ G(F,M) (thªm c¹nh x2, y3): ViÖc t×m kiÕm trªn ®å thÞ nµy kÕt thóc t¹i y1 cho ta ®­êng t¨ng cÆp ghÐp: x4 -> y1 -> x2 -> y3 vµ trªn ®­êng nµy, cÆp ghÐp cò (x2, y1) ®­îc thay b»ng 2 cÆp ghÐp míi (x2, y3) vµ (x4, y1) KÕt qu¶ cuèi cïng cho tËp cÆp ghÐp ®Çy ®ñ tèi ­u M = {(x1, y4), (x2, y1), (x3, y2), (x4, y1)} víi tæng träng sè lµ 6 + 6 + 9 + 5 = 26.