Bài giảng Kỹ thuật phân tích giải thuật

Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 1 1. Mөc tiêu 2. KiӃn thӭc cѫ bҧn cҫn có ÿӇ hӑc chѭѫng này 3. Tài liӋu tham khҧo có liên quan ÿӃn chѭѫng 4. Nӝi dung: I.1 - Sӵ cҫn thiӃt phҧi phân tích giҧi thuұt. I.2 - Thӡi gian thӵc hiӋn cӫa giҧi thuұt. I.3 - Tӹ suҩt tăng và ÿӝ phӭc tҥp cӫa giҧi thuұt. I.4 - Cách tính ÿӝ phӭc tҥp. I.5 - Phân tích các chѭѫng trình ÿӋ quy. 5. Vҩn ÿӅ nghiên cӭu cӫa trang kӃ tiӃp Trong chѭѫng này chúng ta sӁ nghiên cӭu các vҩn ÿӅ sau: · Sӵ cҫn thiӃt phҧi phân tích các giҧi thuұt. · Thӡi gian thӵc hiӋn cӫa chѭѫng trình. · Tӹ suҩt tăng và ÿӝ phӭc tҥp cӫa giҧi thuұt. · Tính thӡi gian thӵc hiӋn cӫa chѭѫng trình. · Phân tích các chѭѫng trình ÿӋ quy. I.1- SӴ CҪN THIӂT PHҦI PHÂN TÍCH GIҦI THUҰT Trong khi giҧi mӝt bài toán chúng ta có thӇ có mӝt sӕ giҧi thuұt khác nhau, vҩn ÿӅ là cҫn phҧi ÿánh giá các giҧi thuұt ÿó ÿӇ lӵa chӑn mӝt giҧi thuұt tӕt (nhҩt). Thông thѭӡng thì ta sӁ căn cӭ vào các tiêu chuҭn sau: 1.- Giҧi thuұt ÿúng ÿҳn. 2.- Giҧi thuұt ÿѫn giҧn. 3.- Giҧi thuұt thӵc hiӋn nhanh. Vӟi yêu cҫu (1), ÿӇ kiӇm tra tính ÿúng ÿҳn cӫa giҧi thuұt chúng ta có thӇ cài ÿһt giҧi thuұt ÿó và cho thӵc hiӋn trên máy vӟi mӝt sӕ bӝ dӳ liӋu mүu rӗi lҩy kӃt quҧ thu ÿѭӧc so sánh vӟi kӃt quҧÿã biӃt. Thӵc ra thì cách làm này không chҳc chҳn bӣi vì có thӇ giҧi thuұt ÿúng vӟi tҩt cҧ các bӝ dӳ liӋu chúng ta ÿã thӱ nhѭng lҥi sai vӟi mӝt bӝ dӳ liӋu nào ÿó. Vҧ lҥi cách làm này chӍ phát hiӋn ra giҧi thuұt sai chӭ chѭa chӭng minh ÿѭӧc là nó ÿúng. Tính ÿúng ÿҳn cӫa giҧi thuұt cҫn phҧi ÿѭӧc chӭng minh Eҵng toán hӑc. Tҩt nhiên ÿLӅu này không ÿѫn giҧn và do vұy chúng ta sӁ không ÿӅ cұp ÿӃn ӣÿây. Khi chúng ta viӃt mӝt chѭѫng trình ÿӇ sӱ dөng mӝt vài lҫn thì yêu cҫu (2) là quan trӑng nhҩt. Chúng ta cҫn mӝt giҧi thuұt dӉ viӃt chѭѫng trình ÿӇ nhanh chóng có ÿѭӧc kӃt qӫa , thӡi gian thӵc hiӋn chѭѫng trình không ÿѭӧc ÿӅ cao vì dù sao thì chѭѫng trình ÿó cNJng chӍ sӱ dөng mӝt vài lҫn mà thôi. Tuy nhiên khi mӝt chѭѫng trình ÿѭӧc sӱ dөng nhiӅu lҫn thì thì yêu cҫu tiӃït kiӋm thӡi gianUpload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 2 thӵc hiӋn chѭѫng trình lҥi rҩt quan trӑng ÿһc biӋt ÿӕi vӟi nhӳng chѭѫng trình mà khi thӵc hiӋn cҫn dӳ liӋu nhұp lӟn do ÿó yêu cҫu (3) sӁÿѭӧc xem xét mӝt cách kӻ càng. Ta gӑi nó là hiӋu quҧ thӡi gian thӵc hiӋn cӫa giҧi thuұt. I.2- THӠI GIAN THӴC HIӊN CӪA GIҦI THUҰT I.2.1- Thӡi gian thӵc hiӋn chѭѫng trình. I.2.2- Ĉѫn vӏÿo thӡi gian thӵc hiӋn. I.2.3- Thӡi gian thӵc hiӋn trong trѭӡng hӧp xҩu nhҩt. Mӝt phѭѫng pháp ÿӇ xác ÿӏnh hiӋu quҧ thӡi gian thӵc hiӋn cӫa mӝt giҧi thuұt là lұp trình nó và ÿo Oѭӡng thӡi gian thӵc hiӋn cӫa hoҥt ÿӝng trên mӝt máy tính xác ÿӏnh ÿӕi vӟi tұp hӧp ÿѭӧc chӑn lӑc các Gӳ liӋu vào. Thӡi gian thӵc hiӋn không chӍ phө thuӝc vào giҧi thuұt mà còn phө thuӝc váo tұp các chӍ thӏ Fӫa máy tính, chҩt lѭӧng cӫa máy tính và kӻ xҧo cӫa ngѭӡi lұp trình. Sӵ thi hành cNJng có thӇÿLӅu chӍnh ÿӇ thӵc hiӋn tӕt trên tұp ÿһc biӋt các dӳ liӋu vào ÿѭӧc chӑn. ĈӇ vѭӧt qua các trӣ ngҥi này, các nhà khoa hӑc máy tính ÿã chҩp nhұn tính phӭc tҥp cӫa thӟi gian ÿѭӧc tiӃp cұn nhѭ mӝt sӵÿo lѭӡng cѫ Eҧn sӵ thӵc thi cӫa giҧi thuұt. Thuұt ngӳ tính hiӋu quҧ sӁÿӅ cұp ÿӃn sӵÿo lѭӡng này và ÿһc biӋt ÿӕi Yӟi sӵ phӭc tҥp thӡi gian trong trѭӡng hӧp xҩu nhҩt. I.2.1- Thӡi gian thӵc hiӋn chѭѫng trình. Thӡi gian thӵc hiӋn mӝt chѭѫng trình là mӝt hàm cӫa kích thѭӟc dӳ liӋu vào, ký hiӋu T(n) trong ÿó n là kích thѭӟc (ÿӝ lӟn) cӫa dӳ liӋu vào. Ví dө 1-1: Chѭѫng trình tính tәng cӫa n sӕ có thӡi gian thӵc hiӋn là T(n) = cn trong ÿó c là Pӝt hҵng sӕ. Thӡi gian thӵc hiӋn chѭѫng trình là mӝt hàm không âm, tӭc là T(n) ³0 "n³0. I.2.2- Ĉѫn vӏÿo thӡi gian thӵc hiӋn. Ĉѫn vӏ cӫa T(n) không phҧi là ÿѫn vӏÿo thӡi gian bình thѭӡng nhѭ giӡ, phút giây... mà thѭӡng ÿѭӧc xác ÿӏnh bӣi sӕ các lӋnh ÿѭӧc thӵc hiӋn trong mӝt máy tính lý tѭӣng. Ví dө 1-2: Khi ta nói thӡi gian thӵc hiӋn cӫa mӝt chѭѫng trình là T(n) = cn thì có nghƭa là chѭѫng trình ҩy cҫn cn chӍ thӏ thӵc thi. I.2.3- Thӡi gian thӵc hiӋn trong trѭӡng hӧp xҩu nhҩt. Nói chung thì thӡi gian thӵc hiӋn chѭѫng trình không chӍ phө thuӝc vào kích thѭӟc mà còn phө thuӝc vào tính chҩt cӫa dӳ liӋu vào. Nghƭa là dӳ liӋu vào có cùng kích thѭӟc nhѭng thӡi gian thӵc hiӋn chѭѫng trình có thӇ khác nhau. Chҷng hҥn chѭѫng trình sҳp xӃp dãy sӕ nguyên tăng dҫn, khi ta cho vào dãy có thӭ tӵ thì thӡi gian thӵc hiӋn khác vӟi khi ta cho vào dãy chѭa có thӭ tӵ, hoһc khi ta cho vào mӝt dãy ÿã có thӭ tӵ tăng thì thӡi gian thӵc hiӋn cNJng khác so vӟi khi ta cho vào mӝt dãy ÿã có thӭ tӵ giҧm. Vì vұy thѭӡng ta coi T(n) là thӡi gian thӵc hiӋn chѭѫng trình trong trѭӡng hӧp xҩu nhҩt trên Gӳ liӋu vào có kích thѭóc n, tӭc là: T(n) là thӡi gian lӟn nhҩt ÿӇ thӵc hiӋn chѭѫng trình ÿӕi vӟi mӑi dӳ liӋu vào có cùng kích thѭӟc n. I.3- TӸ SUҨT TĂNG VÀ ĈӜ PHӬC TҤP CӪA GIҦI THUҰT Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 3 I.3.1- Tӹ suҩt tăng I.3.2- Khái niӋm ÿӝ phӭc tҥp cӫa giҧi thuұt I.3.1- Tӹ suҩt tăng Ta nói rҵng hàm không âm T(n) có Wӹ suҩt tăng (growth rate) f(n) nӃu tӗn tҥi các hҵng sӕ c và n0 sao cho T(n) ” f(n) vӟi mӑi n • n0. Ta có thӇ chӭng minh ÿѭӧc rҵng “Cho mӝt hàm không âm T(n) bҩt kǤ, ta luôn tìm ÿѭӧc tӹ suҩt tăng f(n) cӫa nó”. Ví dө 1-3: Giҧ sӱ T(0) = 1, T(1) = 4 và tәng quát T(n) = (n+1)2. Ĉһt n0 = 1 và c = 4 thì vӟi mӑi n • 1 chúng ta dӉ dàng chӭng minh rҵng T(n) = (n+1)2” 4n2 vӟi mӑi n • 1, tӭc là tӹ suҩt tăng cӫa T(n) là n2. Ví dө 1-4: Tӹ suҩt tăng cӫa hàm T(n) = 3n3 + 2n2 là n3. Thӵc vұy, cho n0 = 0 và c = 5 ta dӉ dàng chӭng minh rҵng vӟi mӑi n • 0 thì 3n3 + 2n2” 5n3 I.3.2- Khái niӋm ÿӝ phӭc tҥp cӫa giҧi thuұt Giҧ sӱ ta có hai giҧi thuұt P1 và P2 vӟi thӡi gian thӵc hiӋn tѭѫng ӭng là T1(n) = 100n2 (vӟi tӹ suҩt tăng là n2) và T2(n) = 5n3 (vӟi tӹ suҩt tăng là n3). Giҧi thuұt nào sӁ thӵc hiӋn nhanh hѫn? Câu trҧ Oӡi phө thuӝc vào kích thѭӟc dӳ liӋu vào. Vӟi n < 20 thì P2 sӁ nhanh hѫn P1 (T2<T1), do hӋ sӕ cӫa 5n3 nhӓ hѫn hӋ sӕ cӫa 100n2 (5 20 thì ngѭѫc lҥi do sӕ mNJ cӫa 100n2 nhӓ hѫn sӕ mNJ Fӫa 5n3 (220 vì khi n<20 thì thӡi gian thӵc hiӋn cӫa cҧ P1 và P2 ÿӅu không lӟn và sӵ khác biӋt giӳa T1 và T2 là không ÿáng kӇ.. Nhѭ vұy mӝt cách hӧp lý là ta xét tӹ suҩt tăng cӫa hàm thӡi gian thӵc hiӋn chѭѫng trình thay vì xét chính bҧn thân thӡi gian thӵc hiӋn. Cho mӝt hàm T(n), T(n) gӑi là có ÿӝ phӭc tҥp f(n) nӃu tӗn tҥi các hҵng c, N0 sao cho T(n) ” cf(n) vӟi mӑi n • N0 (tӭc là T(n) có tӹ suҩt tăng là f(n)) và kí hiӋu T(n) là O(f(n)) (ÿӑc là “ô cӫa f(n)”) Ví dө 1-5: T(n)= (n+1)2 có tӹ suҩt tăng là n2 nên T(n)= (n+1)2 là O(n2) Chú ý: O(c.f(n))=O(f(n)) vӟi c là hҵng sӕ. Ĉһc biӋt O(c)=O(1) Nói cách khác ÿӝ phӭc tҥp tính toán cӫa giҧi thuұt là mӝt hàm chһn trên cӫa hàm thӡi gian. Vì Kҵng nhân tӱ c trong hàm chһn trên không có ý nghƭa nên ta có thӇ bӓ qua vì vұy hàm thӇ hiӋn ÿӝ phӭc Wҥp có các dҥng thѭӡng gһp sau: log2n, n, nlog2n, n2, n3, 22, n!, nn. Ba hàm cuӕi cùng ta gӑi là dҥng hàm mNJ, các hàm khác gӑi là hàm ÿa thӭc. Mӝt giҧi thuұt mà thӡi gian thӵc hiӋn có ÿӝ phӭc tҥp là mӝt hàm ÿa thӭc thì chҩp nhұn ÿѭӧc tӭc là có thӇ cài ÿһt ÿӇ thӵc hiӋn, còn các giҧi thuұt có ÿӝ phӭc tҥp hàm mNJ thì phҧi tìm cách cҧi tiӃn giҧi thuұt. Khi nói ÿӃn ÿӝ phӭc tҥp cӫa giҧi thuұt là ta muӕn nói ÿӃn hiӋu quҧ cӫa thӡi gian thӵc hiӋn cӫa chѭѫng trình nên ta có thӇ xem viӋc xác ÿӏnh thӡi gian thӵc hiên cӫa chѭѫng trình chính là xác ÿӏnh ÿӝ phӭc tҥp cӫa giҧi thuұt. I.4- CÁCH TÍNH ĈӜ PHӬC TҤP I.4.1- Qui tҳc cӝng I.4.2- Qui tҳc nhân Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 4 I.4.3- Qui tҳc tәng quát ÿӇ phân tích mӝt chѭѫng trình I.4.4- Ĉӝ phӭc tҥp cӫa chѭѫng trình có gӑi chѭѫng trình con không ÿӋ qui Cách tính ÿӝ phӭc tҥp cӫa mӝt giҧi thuұt bҩt kǤ là mӝt vҩn ÿӅ không ÿѫn giҧn. Tuy nhiên ta có thӇ tuân theo mӝt sӕ nguyên tҳc sau: I.4.1- Qui tҳc cӝng: NӃu T1(n) và T2(n) là thӡi gian thӵc hiӋn cӫa hai ÿRҥn chѭѫng trình P1 và P2; và T1(n)=O(f(n)), T2(n)=O(g(n) thì thӡi gian thӵc hiӋn cӫa ÿRҥn hai chѭѫng trình ÿó Qӕi tiӃp nhau là T(n)=O(max(f(n),g(n))) Ví dө 1-6: LӋnh gán x:=15 tӕn mӝt hҵng thӡi gian hay O(1) LӋnh ÿӑc dӳ liӋu READ(x) tӕn mӝt hҵng thӡi gian hay O(1) Vұy thӡi gian thӵc hiӋn cҧ hai lӋnh trên nӕi tiӃp nhau là O(max(1,1))=O(1) I.4.2- Qui tҳc nhân: NӃu T1(n) và T2(n) là thӡi gian thӵc hiӋn cӫa hai ÿRҥn chѭѫng trình P1và P2 và T1(n) = O(f(n)), T2(n) = O(g(n) thì thӡi gian thӵc hiӋn cӫa ÿRҥn hai ÿRҥn chѭѫng trình ÿó Oӗng nhau là T(n) = O(f(n).g(n)) I.4.3- Qui tҳc tәng quát ÿӇ phân tích mӝt chѭѫng trình: - Thӡi gian thӵc hiӋn cӫa mӛi lӋnh gán, READ, WRITE là O(1) - Thӡi gian thӵc hiӋn cӫa mӝt chuӛi tuҫn tӵ các lӋnh ÿѭӧc xác ÿӏnh bҵng qui tҳc cӝng. Nhѭ Yұy thӡi gian này là thӡi gian thi hành mӝt lӋnh nào ÿó lâu nhҩt trong chuӛi lӋnh. - Thӡi gian thӵc hiӋn cҩu trúc IF là thӡi gian lӟn nhҩt thӵc hiӋn lӋnh sau THEN hoһc sau ELSE và thӡi gian kiӇm tra ÿLӅu kiӋn. Thѭӡng thӡi gian kiӇm tra ÿLӅu kiӋn là O(1). - Thӡi gian thӵc hiӋn vòng lһp là tәng (trên tҩt cҧ các lҫn lһp) thӡi gian thӵc hiӋn thân vòng Oһp. NӃu thӡi gian thӵc hiӋn than vòng lһp không ÿәi thì thӡi gian thӵc hiӋn vòng lһp là tích cӫa sӕ lҫn Oһp vӟi thӡi gian thӵc hiӋn thân vòng lһp. Ví dө 1-7: Tính thӡi gian thӵc hiӋn cӫa ÿRҥn chѭѫng trình procedure Bubble (var a: array[1..n] of integer); var i,j,temp: integer; begin {1} for i:=1 to n-1 do {2} for j:=n downto i+1 do {3} if a[j-1]>a[j] then begin { ÿәi chә a[i], a[j] } {4} temp:=a[j-1]; {5} a[j-1]:=a[j]; {6} a[j]:=temp; end; end; Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 5 Cҧ ba lӋnh ÿәi chӛ {4} {5} {6} tӕn O(1) thӡi gian, do ÿó lӋnh {3} tӕn O(1). Vòng lһp {2} thӵc hiӋn (n-i) lҫn, mӛi lҫn O(1) do ÿó vòng lһp {2} tӕn O((n-i).1)=O(n-i). Vòng lһp {1} lһp (n-1) lҫn vұy ÿӝ phӭc tҥp cӫa giҧi thuұt là: I.4.4- Ĉӝ phӭc tҥp cӫa chѭѫng trình có gӑi chѭѫng trình con không ÿӋ qui NӃu chúng ta có mӝt chѭѫng trình vӟi các chѭѫng trình con không ÿӋ quy, ÿӇ tính thӡi gian thӵc hiӋn cӫa chѭѫng trình, trѭӟc hӃt chúng ta tính thӡi gian thӵc hiӋn cӫa các chѭѫng trình con không Jӑi các chѭѫng trình con khác. Sau ÿó chúng ta tính thӡi gian thӵc hiӋn cӫa các chѭѫng trình con chӍ Jӑi các chѭѫng trình con mà thӡi gian thӵc hiӋn cӫa chúng ÿã ÿѭӧc tính. Chúng ta tiӃp tөc quá trình ÿánh giá thӡi gian thӵc hiӋn cӫa mӛi chѭѫng trình con sau khi thӡi gian thӵc hiӋn cӫa tҩt cҧ các chѭѫng trình con mà nó gӑi ÿã ÿѭӧc ÿánh giá. Cuӕi cùng ta tính thӡi gian cho chѭѫng trình chính. Giҧ sӱ ta cô mӝt hӋ thӕng các chѭѫng trình gӑi theo sѫÿӗ sau: Chѭѫng trình A gӑi hai chѭѫng trình con là B và C, chѭѫng trình B gӑi hai chѭѫng trình con là B1 và B2, chѭѫng trình B1 gӑi hai chѭѫng trình con là B11 và B12. ĈӇ tính thӡi gian thӵc hiӋn cӫa A, ta tính theo các bѭӟc sau: - Tính thӡi gian thӵc hiӋn cӫa C, B2, B11 và B12. - Tính thӡi gian thӵc hiӋn cӫa B1. - Tính thӡi gian thӵc hiӋn cӫa B. - Tính thӡi gian thӵc hiӋn cӫa A. Ví dө 1-8: Ta có thӇ viӃt lҥi chѭѫng trình sҳp xӃp bubble nhѭ sau: procedure Swap (var x, y: integer); var temp: integer; begin temp := x; x := y; y := temp; end; Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 6 procedure Bubble (var a: array[1..n] of integer); var i,j :integer; begin {1} for i:=1 to n-1 do {2} for j:=n downto i+1 do {3} if a[j-1]>a[j] then Swap(a[j-1], a[j]); end; Trong cách viӃt trên, chѭѫng trình Bubble gӑi chѭѫng trình con Swap, do ÿó ÿӇ tính thӡi gian thӵc hiӋn cӫa Bubble, trѭӟc hӃt ta cҫn tính thӡi gian thӵc hiӋn cӫa Swap. DӉ thҩy thӡi gian thӵc hiӋn Fӫa Swap là O(1) vì nó chӍ bao gӗm 3 lӋnh gán. Trong Bubble, lӋnh {3} gӑi Swap nên chӍ tӕn O(1), lӋnh {2} thӵc hiӋn n-i lҫn, mӛi lҫn tӕn O(1) nên tӕn O(n-i). LӋnh {1} thӵc hiӋn n-1 lҫn nên I.5- PHÂN TÍCH CÁC CHѬѪNG TRÌNH Ĉӊ QUY I.5.1- Thành lұp phѭѫng trình ÿӋ quy I.5.2- Giҧi phѭѫng trình ÿӋ quy Vӟi các chѭѫng trình có gӑi các chѭѫng trình con ÿӋ quy, ta không thӇ áp dөng cách tính nhѭ Yӯa trình bày trong mөc I.4.4 bӣi vì mӝt chѭѫng trình ÿӋ quy sӁ gӑi chính bҧn thân nó. Vӟi các chѭѫng trình ÿӋ quy, trѭӟc hӃt ta cҫn thành lұp các phѭѫng trình ÿӋ quy, sau ÿó giҧi phѭѫng trình ÿӋ quy, nghiӋm cӫa phѭѫng trình ÿӋ quy sӁ là thӡi gian thӵc hiӋn cӫa chѭѫng trình ÿӋ quy. I.5.1- Thành lұp phѭѫng trình ÿӋ quy Phѭѫng trình ÿӋ quy là mӝt phѭѫng trình biӇu diӉn mӕi liên hӋ giӳa T(n) và T(k), trong ÿó T(n) là thӡi gian thӵc hiӋn chѭѫng trình vӟi kích thѭӟc dӳ liӋu nhұp là n, T(k) thӡi gian thӵc hiӋn chѭѫng trình vӟi kích thѭӟc dӳ liӋu nhұp là k, vӟi k < n. ĈӇ thành lұp ÿѭӧc phѭѫng trình ÿӋ quy, ta phҧi căn cӭ vào chѭѫng trình ÿӋ quy. Ví dө 1-9: Xét hàm tính giai thӯa viӃt bҵng giҧi thuұt ÿӋ quy nhѭ sau: function Giai_thua(n:integer): integer; begin if n=0 then Giai_thua :=1 else Giai_thua := n* Giai_thua(n-1); end; *ӑi T(n) là thӡi gian thӵc hiӋn viӋc tính n giai thӯa, thì T(n-1) là thӡi gian thӵc hiӋn viӋc tính n-1 giai thӯa. Trong trѭӡng hӧp n=0 thì chѭѫng trình chӍ thӵc hiӋn mӝt lӋnh gán Giai_thua:=1, nên tӕn O(1), do ÿó ta có T(0) = C1. Trong trѭӡng hӧp n>0 chѭѫng trình phҧi gӑi ÿӋ quy Giai_thua(n-1), viӋc Jӑi ÿӋ quy này tӕn T(n-1), sau khi có kӃt quҧ cӫa viӋc gӑi ÿӋ quy, chѭѫng trình phҧi nhân kӃt quҧÿó Yӟi n và gán cho Giai_thua. Thӡi gian ÿӇ thӵc hiӋn phép nhân và phép gán là mӝt hҵng C2. Vұy ta có Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 7 Ĉây là phѭѫng trình ÿӋ quy ÿӇ tính thӡi gian thӵc hiӋn cӫa chѭѫng trình ÿӋ quy Giai_thua. Ví dө 1-10: Chúng ta xét thӫ tөc MergeSort mӝt cách phác thҧo nhѭ sau: function MergeSort (L:List ; n:integer) : List; var L1,L2 : List; begin if n = 1 then return(L) else begin Chia L thành 2 nӱa L1 và L2 , mӛi mӝt nӱa có ÿӝ dài n/2; return(Merge(MergeSort (L1 , n/2), MergeSort(L2, n/2))); end; end; Chҷng hҥn ÿӇ sҳp xӃp danh sách L gӗm 8 phҫn tӱ 7, 4, 8, 9, 3, 1, 6, 2 ta có mô hình minh hӑa Fӫa MergeSort nhѭ sau: Hàm MergeSort nhұn mӝt danh sách có ÿӝ dài n và trҧ vӅ mӝt danh sách ÿã ÿѭӧc sҳp xӃp. Thӫ Wөc Merge nhұn hai danh sách ÿã ÿѭӧc sҳp L1 và L2 mӛi danh sách có ÿӝ dài n/2, trӝn chúng lҥi vӟi nhau ÿӇÿѭӧc mӝt danh sách gӗm n phҫn tӱ có thӭ tӵ. Giҧi thuұt chi tiӃt cӫa Merge ta sӁ bàn sau, chúng ta chӍÿӇ ý rҵng thӡi gian ÿӇ Merge các danh sách có ÿӝ dài n/2 là O(n). Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 8 Gӑi T(n) là thӡi gian thӵc hiӋn MergeSort mӝt danh sách n phҫn tӱ thì T(n/2) là thӡi gian thӵc hiӋn MergeSort mӝt danh sách n/2 phҫn tӱ , ta có thӇ viӃt phѭѫng trình ÿӋ quy nhѭ sau: Trong ÿó c1 là thӡi gian phҧi tӕn khi L có ÿӝ dài 1. Trong trѭӡng hӧp n > 1, thӡi gian cӫa MergeSort ÿѭӧc chia làm hai phҫn. Phҫn gӑi ÿӋ quy MergeSort mӝt danh sách có ÿӝ dài n/2 là T(n/2) do ÿó ta có 2T(n/2). Phҫn thӭ hai bao gӗm phép thӱ n >1, chia danh sách L thành hai nӱa bҵng nhau và Merge. Ba thao tác này lҩy thӡi gian không ÿәi ÿӕi vӟi phép thӱ hoһc tӹ lӋ vӟi n ÿӕi vӟi ngҳt và Merge. Nhѭ vұy hҵng c2ÿѭӧc chӑn và c2n là thӡi gian tәng ÿӇ làm các viӋc ÿó ngoҥi trӯ gӑi ÿӋ quy. I.5.2- Giҧi phѭѫng trình ÿӋ quy Có ba phѭѫng pháp giҧi phѭѫng trình ÿӋ quy: 1.- Phѭѫng pháp truy hӗi 2.- Phѭѫng pháp ÿoán nghiӋm. 3.- Lӡi giҧi tәng quát cӫa mӝt lӟp các phѭѫng trình ÿӋ quy. Phѭѫng pháp truy hӗi Dùng ÿӋ quy ÿӇ thay thӃ bҩt kǤ T(m) vӟi m < n vào phía phҧi cӫa phѭѫng trình cho ÿӃn khi tҩt Fҧ T(m) vӟi m > 1 ÿѭӧc thay thӃ bӣi biӇu thӭc cӫa các T(1). Vì T(1) luôn là hҵng nên chúng ta có công thӭc cӫa T(n) chӭa các sӕ hҥng chӍ liên quan ÿӃn n và các hҵng sӕ. Giҧi phѭѫng trình. Ví dө 1-10: Giҧi phѭѫng trình: Ta có: Giҧ sӱ n = 2k, quá trình suy rӝng sӁ kӃt thúc khi i =k, khi ÿó ta có: T(n) = 2kT(1) + kC2n Vì 2k = n nên k = logn và vӟi T(1) =C1 nên ta có Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................ Trang 9 T(n) = C1n + C2nlogn Hay T(n) là O(nlogn). Ĉoán nghiӋm Ta ÿoán mӝt nghiӋm f(n) và dùng chӭng minh quy nҥp ÿӇ chӭng tӓ rҵng T(n) ” f(n) vӟi mӑi n. Thông thѭӡng f(n) là mӝt trong các hàm quen thuӝc nhѭ logn, n, nlogn, n2, n3, 2n, n!, nn. Ĉôi khi chúng ta chӍÿoán dҥng cӫa f(n) trong ÿó có mӝt vài tham sӕ chѭa xác ÿӏnh (chҷng hҥn f(n) = an2 vӟi a chѭa xác ÿӏnh) và trong quá trình chӭng minh quy nҥp ta sӁ suy diӉn ra giá trӏ thích Kӧp cӫa các tham sӕ. Ví dө 1-11: Giҧi phѭѫng trình ÿӋ quy Giҧ sӱ chúng ta ÿoán f(n) = anlogn. Vӟi n = 1 ta thҩy rҵng cách ÿoán nhѭ vұy không ÿѭӧc bӣi vì anlog n có giá trӏ 0 không phө thuӝc vào giá trӏ cӫa a. Vì thӃ ta thӱ tiӃp theo f(n) = anlogn + b. Vӟi n = 1 ta có, T(1) = C1 và f(1) = b, muӕn T(1) ” f(1) thì b • C1 (*) Giҧ sӱ rҵng T(k) ” aklogk + b vӟi mӑi k < n (I.2).Ta sӁ chӭng minh T(n) ” anlogn + b Giҧ sӱ n • 2, tӯ (I.1) ta có T(n) = 2T(n/2) + C2n Áp dөng (I.2) vӟi k = n/2 < n ta có: T(n) = 2T(n/2) + C2n ” 2[an/2log(n/2) + b] + C2n T(n) ” anlogn - an + 2b + C2n T(n) ” (anlogn + b) + [b + (C2 - a)n] . NӃu lҩy a • C2 + b (**) ta ÿѭӧc T(n) ” (anlogn + b) + [b +(C2 - C2 - b )n ] T(n) ” (anlogn + b) + (1-n) b T(n) ” an logn + b. NӃu ta lҩy a và b sao cho cҧ (*) và (**) ÿӅu thoҧ mãn thì T(n) ” an logn + b vӟi mӑi n. DӉ dàng ta có b = C1 và a= C1 +C2 ta ÿѭӧc T(n) ” (C1 + C2)nlogn + C1 vӟi mӑi n.Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 10 Hay nói cách khác T(n) là O(nlogn). /ӡi giҧi tәng quát cho mӝt lӟp các phѭѫng trình ÿӋ quy ĈӇ giҧi bài toán kích thѭӟc n, ta chia bài toán ÿã cho thành a bài toán con, mӛi bài tóan con có kích thѭӟc n/b. Giҧi các bài toán con này và tәng hӧp kӃt quҧ lҥi ÿӇÿѭӧc kӃt quҧ cӫa bài toán ÿã cho. 9ӟi các bài toán con chúng ta cNJng làm nhѭ vұy. Kӻ thuұt này sӁ dүn chúng ta ÿӃn mӝt chѭѫng trình ÿӋ quy. Giҧ thiӃt rҵng mӛi bài toán con kích thѭӟc 1 lҩy mӝt ÿѫn vӏ thӡi gian và thӡi gian ÿӇ chia bài toán kích thѭӟc n thành các bài toán con kích thѭӟc n/b và tәng hӧp kӃt quҧ tӯ các bài toán con ÿӇ ÿѭӧc lӡi giҧi cӫa bài toán ban ÿҫu là d(n). (Chҷng hҥn ÿӕi vӟi thí dө MergeSort, chúng ta có a = b = 2, và d(n) = C2n/C1. Xem C1 là mӝt ÿѫn vӏ). Gӑi T(n) là thӡi gian ÿӇ giҧi bài toán kích thѭӟc n thì ta có phѭѫng trình ÿӋ quy: Ta sӱ dөng phѭѫng pháp truy hӗi ÿӇ giҧi phѭѫng trình này Giҧ sӱ n = bk ta ÿѭӧc: T(n/bk) = T(1) = 1. Thay vào trên vӟi i = k ta có: Hàm tiӃn triӇn, nghiӋm thuҫn nhҩt và nghiӋm riêng Trong phѭѫng trình ÿӋ quy (I.1) hàm thӡi gian d(n) ÿѭӧc gӑi là hàm tiӃn triӇn (driving function) Trong công thӭc (I.2), ak = nlogbaÿѭӧc gӑi là nghiӋm thuҫn nhҩt (homogeneous solutions). NghiӋm thuҫn nhҩt là nghiӋm chính xác khi d(n) = 0 vӟi mӑi n. Nói mӝt cách khác, nghiӋm thuҫn nhҩt biӇu diӉn thӡi gian ÿӇ giҧi tҩt cҧ các bài toán con. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 11 Trong công thӭc (I.2), ÿѭӧc gӑi là nghiӋm riêng (particular solutions). NghiӋm riêng biӇu diӉn thӡi gian phҧi trҧÿӇ tҥo ra các bài toán con và tәng hӧp các kӃt quҧ Fӫa chúng. Nhìn vào công thӭc ta thҩy nghiӋm riêng phө thuӝc vào hàm tiӃn triӇn, sӕ lѭӧng và kích thѭӟc các bài toán con. Khi tìm nghiӋm cӫa phѭѫng trình (I,1), chúng ta phҧi tìm nghiӋm riêng và so sánh vӟi nghiӋm thuҫn nhҩt. NӃu nghiӋm nào lӟn hѫn, ta lҩy nghiӋm ÿó làm nghiӋm cӫa phѭѫng trình (I,1). ViӋc xác ÿӏnh nghiӋm riêng không ÿѫn giҧn chút nào, tuy vұy, chúng ta cNJng tìm ÿѭӧc mӝt lӟp các hàm tiӃn triӇn có thӇ dӉ dàng xác ÿӏnh nghiӋm riêng. Hàm nhân Mӝt hàm f(n) ÿѭӧc gӑi là hàm nhân (multiplicative function) nӃu f(m.n) = f(m).f(n) vӟi mӑi Vӕ nguyên dѭѫng m và n. Ví dө 1-12: Hàm f(n) = nk là mӝt hàm nhân, vì f(m.n) = (m.n)k = mk.nk = f(m) f(n) 1Ӄu d(n) trong (I.1) là mӝt hàm nhân thì theo tính chҩt cӫa hàm nhân ta có d(bk-j) = (d(b))k-j và nghiӋm riêng cӫa (I.2) là: Xét ba trѭӡng hӧp sau: 1.- NӃu a > d(b) thì nghiӋm riêng là O(ak) = O(nlogba). Nhѭ vұy nghiӋm riêng và nghiӋm thuҫn nhҩt bҵng nhau do ÿó T(n) là O(nlogba). Ta cNJng thҩy thӡi gian thӵc hiӋn chӍ phө thuӝc vào a, b mà không phө thuӝc vào hàm tiӃn triӇn d(n). Vì vұy ÿӇ cҧi tiӃn giҧi thuұt ta cҫn giҧm a hoһc tăng b. 2.- NӃu a < d(b) thì nghiӋm riêng là O(d(b)k) = O(nlogbd(b)). Trong trѭӡng hӧp này nghiӋm riêng Oӟn hѫn nghiӋm thuҫn nhҩt nên T(n) = O(nlogbd(b)). ĈӇ cҧi tiӃn giҧi thuұt chúng ta cҫn ÿӇ ý ÿӃn cҧ d(n), a và b cùng mӭc ÿӝ nhѭ nhau. Trѭӡng hӧp ÿһc biӋt quan trӑng khi d(n) = nĮ . Khi ÿó d(b) = bĮ và logb(bĮ) = Į. Vì thӃ nghiӋm riêng là O(nĮ) và do vұy T(n) là O(nĮ). 3.- NӃu a = d(b) thì công thӭc (I.5) không xác ÿinh nên ta tính trӵc tiӃp nghiӋm riêng: Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 12 Vì a= d(b) nên nghiӋm riêng là nlogbalogbn và nghiӋm này lӟn gҩp logbn lҫn nghiӋm thuҫn nhҩt. Do ÿó T(n) = O(nlogbalogbn). Trong trѭӡng hӧp ÿһc biӋt d(n) = nĮ ta ÿѭӧc T(n) = O(nĮlogn). Chú ý khi giҧi mӝt phѭѫng trình ÿӋ quy cө thӇ, ta phҧi xem phѭѫng trình ÿó có thuӝc dҥng phѭѫng trình tәng quát hay không. NӃu có thì phҧi xét xem hàm tiӃn triӇn có phҧi là hàm nhân không. 1Ӄu có thì ta xác ÿӏnh a, d(b) và dӵa vào sӵ so sánh giӳa a và d(b) mà vұn dөng mӝt trong ba trѭӡng Kӧp nói trên. Ví dө 1-13: Giҧi các phѭѫng trình ÿӋ quy sau vӟi T(1) = 1 và 1/- T(n) = 4T(n/2) + n 2/- T(n) = 4T(n/2) + n2 3/- T(n) = 4T(n/2) + n3 Trong mӛi trѭӡng hӧp, a=4, b=2 và nghiӋm thuҫn nhҩt là n2. Vӟi d(n) = n ta có d(b) = 2 vì a = 4 > d(b) nên nghiӋm riêng cNJng là n2 và T(n) = O(n2) trong phѭѫng trình (1). Trong phѭѫng trình (3), d(n) = n3, d(b) = 8 và a < d(b). Vì vұy nghiӋm riêng là O(nlogbd(b)) = O(n3) và T(n) cӫa (3) là O(n3). Trong phѭѫng trình (2) chúng ta có d(b) = 4 = a nên T(n) = O(n2logn). Các hàm tiӃn triӇn khác Ta xét hai trѭӡng hӧp dѭӟi dҥng hai ví dө, trѭӡng hӧp 1 là tәng quát hóa cӫa hàm bҩt kǤ là tích Fӫa mӝt hàm nhân vӟi mӝt hҵng lӟn hѫn hoһc bҵng 1. Trѭӡng hӧp thӭ hai là hàm tiӃn triӇn không phҧi là mӝt hàm nhân. Ví dө 1-14: Giҧi pgѭѫng trình ÿӋ quy sau : T(1) = 1 T(n) = 3T(n/2) + 2n1.5 Ӣÿây, 2n1.5 không phҧi là hàm nhân nhѭng n1.5 là hàm nhân. Ĉһt U(n) = T(n)/2 vӟi mӑi n thì U(1) = 1/2 U(n) = 3U(n/2) + n1.5 NghiӋm thuҫn nhҩt khi U(1) = 1 là nlog3 = n1.59; vì U(1) = 1/2 nên nghiӋm thuҫn nhҩt là n1.59/2 là O(n1.59). Vì a = 3 và b = 2 và b1.5 = 2.82 < a, nghiӋm riêng cNJng là O(n1.59) và do ÿó U(n) = O(n1.59) . Vì Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 13 T(n) = 2U(n) nên T(n) = O(n1.59) hay T(n) = O(nlog3). Ví dө 1-15: Giҧi phѭѫng trình ÿӋ quy sau : T(1) = 1 T(n) = 2T(n/2) + nlogn Vì a = b = 2 nên nghiӋm thuҫn nhҩt là n. Tuy nhiên, d(n) = nlogn không phҧi là hàm nhân ta phҧi tính nghiӋm riêng bҵng cách xét trӵc tiӃp: Vì k = logn chúng ta có nghiӋm riêng là O(nlog2n), nghiӋm này lӟn hѫn nghiӋm thuҫn nhҩt và T(n) = O(nlog2n). Bài 1: Tính thӡi gian thӵc hiӋn cӫa các ÿRҥn chѭѫng trình sau: a) Tính tәng cӫa các sӕ Sum := 0; for i:=1 to n do begin readln(x); Sum := Sum + x; end; b) Tính tích hai ma trұn vuông cҩp n C = A*B: for i := 1 to n do for j := 1 to n do begin c[i,j] := 0; for k := 1 to n do c[i,j] := c[i,j] + a[i,k] * b[k,j]; end; Bài 2: Giҧi các phѭѫng trình ÿӋ quy sau vӟi T(1) = 1 và a) T(n) = 3T(n/2) + n b) T(n) = 3T(n/2) + n2 c) T(n) = 8T(n/2) + n3 Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 14 Bài 3: Giҧi các phѭѫng trình ÿӋ quy sau vӟi T(1) = 1 và a) T(n) = 4T(n/3) + n b) T(n) = 4T(n/3) + n2 c) T(n) = 9T(n/3) + n2 Bài 4: Giҧi các phѭѫng trình ÿӋ quy sau vӟi T(1) = 1 và a) T(n) = T(n/2) + 1 b) T(n) = 2T(n/2) + logn c) T(n) = 2T(n/2) + n d) T(n) = 2T(n/2) + n2 Bài 5: Giҧi các phѭѫng trình ÿӋ quy sau bҵng phѭѫng pháp ÿoán nghiӋm: a) T(1) = 2 và T(n) = 2T(n-1) + 1 vӟi " n • 2 b) T(1) = 1 và T(n) = 2T(n-1) + n vӟi " n • 2 Bài 6: Cho mӝt mҧng n sӕ nguyên ÿѭӧc sҳp thӭ tӵ tăng. ViӃt hàm tìm mӝt sӕ nguyên trong Pҧng ÿó, nӃu tìm thҩy thì trҧ vӅ TRUE, ngѭӧc lҥi trҧ vӅ FALSE. 6ӱ dөng hai phѭѫng pháp tìm kiӃm tuҫn tӵ và tìm kiӃm nhӏ phân. Vӟi mӛi phѭѫng pháp hãy viӃt mӝt hàm tìm và tính thӡi gian thӵc hiӋn cӫa hàm ÿó. Bài 7: Tính thӡi gian thӵc hiӋn cӫa giҧi thuұt ÿӋ quy giҧi bài toán Tháp Hà nӝi vӟi n tҫng? Bài 8: Xét ÿӏnh nghƭa sӕ tә hӧp chұp k cӫa n nhѭ sau: a) ViӃt mӝt hàm ÿӋ quy ÿӇ tính sӕ tә hӧp chұp k cӫa n. Tính thӡi gian thӵc hiӋn cӫa giҧi thuұt nói trên. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 15 1. Mөc tiêu 2. KiӃn thӭc cѫ bҧn cҫn có ÿӇ hӑc chѭѫng này 3. Tài liӋu tham khҧo có liên quan ÿӃn chѭѫng 4. Nӝi dung: II.1 - Bài toán sҳp xӃp. II.2 - Các phѭѫng pháp sҳp xӃp ÿѫn giҧn II.3 - Quicksort. II.4 - Heapsort. II.5 - Binsort. 5. Vҩn ÿӅ nghiên cӭu cӫa trang kӃ tiӃp Trong chѭѫng này chúng ta sӁ nghiên cӭu các vҩn ÿӅ sau: · Bài toán sҳp xӃp. · Mӝt sӕ giҧi thuұt sҳp xӃp ÿѫn giҧn. · QuickSort · HeapSort · BinSort II.1- BÀI TOÁN SҲP XӂP II.1.1 Tҫm quan trӑng cӫa bài toán sҳp xӃp II.1.2 Sҳp xӃp trong và sҳp xӃp ngoài II.1.3 Tә chӭc dӳ liӋu và ngôn ngӳ cài ÿһt II.1.1 Tҫm quan trӑng cӫa bài toán sҳp xӃp Sҳp xӃp mӝt danh sách các ÿӕi tѭӧng theo mӝt thӭ tӵ nào là mӝt bài toán thѭӡng ÿѭӧc vұn Gөng trong các ӭng dөng tin hӑc. Ví dө ta cҫn sҳp xӃp danh sách thí sinh theo tên vӟi thӭ tӵ Alphabet, hoһc sҳp xӃp danh sách sinh viên theo ÿLӇm trung bình vӟi thӭ tӵ tӯ cao ÿӃn thҩp. Mӝt ví dө khác là khi cҫn tìm kiӃm mӝt ÿӕi tѭӧng trong mӝt danh sách các ÿӕi tѭӧng bҵng giҧi thuұt tìm kiӃm nhӏ phân thì danh sách các ÿӕi tѭӧng này phҧi ÿѭӧc sҳp xӃp trѭӟc ÿó. Tóm lҥi sҳp xӃp là mӝt yêu cҫu không thӇ thiӃu trong khi thiӃt kӃ các phҫn mӅm. II.1.2 Sҳp xӃp trong và sҳp xӃp ngoài Sҳp xӃp trong là sӵ sҳp xӃp dӳ liӋu ÿѭӧc tә chӭc trong bӝ nhӟ trong cuҧ máy tính, ӣÿó ta có thӇ sӱ dөng khҧ năng truy nhұp ngүu nhiên cӫa bӝ nhӟ và do vұy sӵ thӵc hiӋn rҩt nhanh. Sҳp xӃp ngoài là sӵ sҳp xӃp ÿѭӧc sӱ dөng khi sӕ lѭӧng ÿӕi tѭӧng ÿѭӧc sҳp xӃp lӟn không thӇ Oѭu trӳ trong bӝ nhӟ trong mà phҧi lѭu trӳî trên bӝ nhӟ ngoài. Cө thӇ là ta sӁ sҳp xӃp dӳ liӋu ÿѭӧc lѭu trӳ trong các tұp tin. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 16 Chѭѫng này tұp trung giҧi quyӃt vҩn ÿӅ sҳp xӃp trong còn sҳp xӃp ngoài sӁÿѭӧc nghiên cӭu trong chѭѫng IV. II.1.3 Tә chӭc dӳ liӋu và ngôn ngӳ cài ÿһt Các ÿӕi tѭӧng cҫn ÿѭӧc sҳp xӃp là các mҭu tin gӗm mӝt hoһc nhiӅu trѭӡng. Mӝt trong các trѭӡng ÿѭӧc gӑi là khóa (key), kiӇu cӫa nó là mӝt kiӇu có quan hӋ thӭ tӵ (nhѭ các kiӇu sӕ nguyên, sӕ thӵc, chuӛi ký tӵ...). Danh sách các ÿӕi tѭӧng cҫn sҳp xӃp sӁ là mӝt mҧng cӫa các mҭu tin vӯa nói ӣ trên. Mөc ÿích Fӫa viӋc sҳp xӃp là tә chӭc lҥi các mҭu tin sao cho các khóa cӫa chúng ÿѭӧc sҳp thӭ tӵ tѭѫng ӭng vӟi quy luұt sҳp xӃp. ĈӇ trình bày các ví dө minh hӑa chúng ta sӁ dùng PASCAL làm ngôn ngӳ thӇ hiӋn và sӱ dөng khai báo sau: const N = 100; type KeyType = integer; OtherType = real; RecordType = Record Key : KeyType; OtherFields : OtherType; end; var a : array[1..N] of RecordType; procedure Swap(var x,y:RecordType); var temp : RecordType; begin temp := x; x := y; y := temp; end; &ҫn thҩy rҵng thӫ tөc Swap lҩy O(1) thӡi gian vì chӍ thӵc hiӋn 3 lӋnh gán nӕi tiӃp nhau. II.2- CÁC PHѬѪNG PHÁP SҲP XӂP ĈѪN GIҦN II.2.1- Sҳp xӃp chӑn II.2.2- Sҳp xӃp xen II.2.3- Sҳp xӃp nәi bӑt Các giҧi thuұt ÿѫn giҧn thѭӡng lҩy O(n2) thӡi gian ÿӇ sҳp xӃp n ÿӕi tѭӧng và các giҧi thuұt này thѭӡng chӍ dùng ÿӇ sҳp các danh sách có ít ÿӕi tѭӧng. Vӟi mӛi giҧi thuұt chúng ta sӁ nghiên cӭu các phҫn: giҧi thuұt, ví dө, chѭѫng trình và phân tích ÿánh giá. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 17 II.2.1- Sҳp xӃp chӑn (Selection Sort) Giҧi thuұt Ĉây là phѭѫng pháp sҳp xӃp ÿѫn giҧn nhҩt ÿѭӧc tiӃn hành nhѭ sau: · Ĉҫu tiên chӑn phҫn tӱ có khóa nhӓ nhҩt trong n phҫn tӱ tӯ a[1] ÿӃn a[n] và hoán vӏ nó Yӟi phҫn tӱ a[1]. · Chӑn phҫn tӱ có khóa nhӓ nhҩt trong n-1phҫn tӱ tӯ a[2] ÿӃn a[n] và hoán vӏ nó vӟi a[2]. · Tәng quát ӣ bѭӟc thӭ i, chӑn phҫn tӱ có khoá nhӓ nhҩt trong n-i+1 phҫn tӱ tӯ a[i] ÿӃn a[n] và hoán vӏ nó vӟi a[i]. · Sau n-1 bѭӟc này thì mҧng ÿã ÿѭӧc sҳp xӃp. Phѭѫng pháp này ÿѭӧc gӑi là phѭѫng pháp chӑn bӣi vì nó lһp lҥi quá trình chӑn phҫn tӱ nhӓ nhҩt trong sӕ các phҫn tӱ chѭa ÿѭӧc sҳp. Ví dө 2-1: Sҳp xӃp mҧng gӗm 10 mҭu tin có khóa là các sӕ nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3 Khoá %ѭӟc a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] Ban ÿҫu 5 6 2 2 10 12 9 10 9 3 %ѭӟc 1 2 6 5 2 10 12 9 10 9 3 %ѭӟc 2 2 5 6 10 12 9 10 9 3 %ѭӟc 3 3 6 10 12 9 10 9 5 %ѭӟc 4 5 10 12 9 10 9 6 %ѭӟc 5 6 12 9 10 9 10 %ѭӟc 6 9 12 10 9 10 %ѭӟc 7 9 10 12 10 %ѭӟc 8 10 12 10 %ѭӟc 9 10 12 .Ӄt quҧ 2 2 3 5 6 9 9 10 10 12 Hình 2-1: S̷p x͇p ch͕n Chѭѫng trình: procedure SelectionSort; var i,j,LowIndex: integer; LowKey: KeyType; begin (1) for i := 1 to n-1 do begin (2) LowIndex := i; (3) LowKey := a[i].key; (4) for j := i+1 to n do (5) if a[j].key < LowKey then Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 18 begin (6) LowKey := a[j].key; (7) LowIndex := j; end; (8) Swap(a[i] , a[LowIndex]); end; end; Ĉánh giá: Ph˱˯ng pháp s̷p x͇p ch͕n ḽy O(n2)ÿ͋ s̷p x͇p n ph̯n t͵. Trѭӟc hӃt ta có thӫ tөc Swap lҩy mӝt hҵng thӡi gian nhѭÿã nói ӣ mөc II.1.3. Các lӋnh (2), (3) ÿӅu lҩy O(1) thӡi gian. Vòng lһp for (4) - (7) thӵc hiӋn n-i lҫn, vì j chҥy tӯ i+1 ÿӃn n, mӛi lҫn lҩy O(1), nên lҩy O(n-i) thӡi gian. Do ÿó thӡi gian tәng cӝng là: II.2.2- Sҳp xӃp xen (Insertion Sort) Giҧi thuұt Trѭӟc hӃt ta xem phҫn tӱ a[1] là mӝt dãy ÿã có thӭ tӵ. · Bѭӟc 1, xen phҫn tӱ a[2] vào danh sách ÿã có thӭ tӵ a[1] sao cho a[1], a[2] là mӝt danh sách có thӭ tӵ. · Bѭӟc 2, xen phҫn tӱ a[3] vào danh sách ÿã có thӭ tӵ a[1], a[2] sao cho a[1], a[2], a[3] là Pӝt danh sách có thӭ tӵ. · Tәng quát, bѭӟc i, xen phҫn tӱ a[i+1] vào danh sách ÿã có thӭ tӵ a[1],a[2],..a[i] sao cho a[1], a[2],.. a[i+1] là mӝt danh sách có thӭ tӵ. · Phҫn tӱÿang xét a[j] sӁÿѭӧc xen vào vӏ trí thích hӧp trong danh sách các phҫn tӱÿã ÿѭӧc sҳp trѭӟc ÿó a[1],a[2],..a[j-1] bҵng cách so sánh khoá cӫa a[j] vӟi khoá cӫa a[j-1] ÿӭng ngay trѭӟc nó. NӃu khoá cӫa a[j] nhӓ hѫn khoá cӫa a[j-1] thì hoán ÿәi a[j-1] và a[j] cho nhau và tiӃp tөc so sánh khoá cӫa a[j-1] (lúc này a[j-1] chӭa nӝi dung cӫa a[j]) vӟi khoá cӫa a[j-2] ÿӭng ngay trѭӟc nó... Ví dө 2-2: Sҳp xӃp mҧng gӗm 10 mҭu tin ÿã cho trong ví dө 2-1. Khoá %ѭӟc a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] Ban ÿҫu 5 6 2 2 10 12 9 10 9 3 %ѭӟc 1 5 6 %ѭӟc 2 2 5 6 %ѭӟc 3 2 2 5 6 %ѭӟc 4 2 2 5 6 10 %ѭӟc 5 2 2 5 6 10 12 Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 19 %ѭӟc 6 2 2 5 6 9 10 12 %ѭӟc 7 2 2 5 6 9 10 10 12 %ѭӟc 8 2 2 5 6 9 9 10 10 12 %ѭӟc 9 2 2 3 5 6 9 9 10 10 12 Hình 2-2: S̷p x͇p xen Chѭѫng trình procedure InsertionSort; var i,j: integer; begin {1} for i := 2 to n do begin {2} J := i; {3} while (j>1) and (a[j].key < a[j-1].key) do begin {4} swap(a[j], a[j-1]); {5} j := j-1; end; end; end; Ĉánh giá: Ph˱˯ng pháp s̷p x͇p ch͕n ḽy O(n2)ÿ͋ s̷p x͇p n ph̯n t͵. Ta thҩy các lӋnh (4) và (5) ÿӅu lҩy O(1). Vòng lһp (3) chҥy nhiӅu nhҩt i-1 lҫn, mӛi lҫn tӕn O(1) nên (3) lҩy i-1 thӡi gian. LӋnh (2) và (3) là hai lӋnh nӕi tiӃp nhau, lӋnh (2) lҩy O(1) nên cҧ hai OӋnh này lҩy i-1. Vòng lһp (1) có i chҥy tӯ 2 ÿӃn n nên nӃu gӑi T(n) là thӡi gian ÿӇ sҳp n phҫn tӱ thì ta có II.2.3- Sҳp xӃp nәi bӑt (Bubble Sort) Giҧi thuұt Chúng ta tѭӣng tѭӧng rҵng các mҭu tin ÿѭӧc lѭu trong mӝt mҧng dӑc, qua quá trình sҳp, mҭu tin nào có khóa “nhҽ” sӁÿѭӧc nәi lên trên. Chúng ta duyӋt tòan mҧng, tӯ dѭӟi lên trên. NӃu hai phҫn Wӱӣ cҥnh nhau mà không ÿúng thӭ tӵ tӭc là nӃu phҫn tӱ “nhҽ hѫn” lҥi nҵm dѭӟi thì phҧi cho nó “nәi lên” bҵng cách ÿәi chӛ hai phҫn tӱ này cho nhau. Cө thӇ là: · Bѭӟc 1: Xét các phҫn tӱ tӯ a[n] ÿӃn a[2], vӟi mӛi phҫn tӱ a[j], so sánh khoá cӫa nó vӟi khoá cӫa phҫn tӱ a[j-1] ÿӭng ngay trѭӟc nó. NӃu khoá cӫa a[j] nhӓ hѫn khoá cӫa a[j-1] thì hoán ÿәi a[j] và a[j-1] cho nhau. · Bѭӟc 2: Xét các phҫn tӱ tӯ a[n] ÿӃn a[3], và làm tѭѫng tӵ nhѭ trên. · Tәng quát ӣ bѭӟc thӭ i, ta sӁ xét các phҫn tӱ tӯ a[n] ÿӃn a[i+1]. Sau n bѭӟc ta thu ÿѭӧc mҧng có thӭ tӵ Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 20 Ví dө 2-3: Sҳp xӃp mҧng gӗm 10 mҭu tin ÿã cho trong ví dө 2-1. Khoá %ѭӟc a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] Ban ÿҫu 5 6 2 2 10 12 9 10 9 3 %ѭӟc 1 2 5 6 2 3 10 12 9 10 9 %ѭӟc 2 2 5 6 3 9 10 12 9 10 %ѭӟc 3 3 5 6 9 9 10 12 10 %ѭӟc 4 5 6 9 9 10 10 12 %ѭӟc 5 6 9 9 10 10 12 %ѭӟc 6 9 9 10 10 12 %ѭӟc 7 9 10 10 12 %ѭӟc 8 10 10 12 %ѭӟc 9 10 12 .Ӄt quҧ 2 2 3 5 6 9 9 10 10 12 Hình 2-3: S̷p x͇p n͝i b͕t Chѭѫng trình procedure BubbleSort; var i,j: integer; begin (1) for i := 1 to n-1 do (2) for j := n downto i+1 do (3) if a[j].key < a[j-1].key then (4) Swap(a[j],a[j-1]); end; Ĉánh giá: Ph˱˯ng pháp s̷p x͇p n͝i b͕t ḽy O(n2)ÿ͋ s̷p n ph̯n t͵. Dòng lӋnh (3) lҩy mӝt hҵng thӡi gian. Vòng lһp (2) thӵc hiӋn (n-i) bѭӟc, mӛi bѭӟc lҩy O(1) nên lҩy O(n-i) thӡi gian. Nhѭ vұy ÿӕi vӟi toàn bӝ chѭѫng trình ta có: II.3- QUICKSORT II.3.1- Ý tѭӣng II.3.2- ThiӃt kӃ giҧi thuұt II.3.3- Cài ÿһt giҧi thuұt II.3.4- Thӡi gian thӵc hiӋn cӫa QuickSort Trong phҫn này chúng ta sӁ nghiên cӭu mӝt giҧi thuұt sҳp xӃp ÿѭӧc dùng mӝt cách phә biӃn là Quick Sort do A.R. Hoare phát minh vào năm 1960. Quick Sort ÿѭӧc ÿánh giá tӕt nhӡ vào sӵ phân tích toán hӑc và các khҷng ÿӏnh vӅ khҧ năng cӫa nó. Quick Sort ÿã ÿѭӧc cҧi tiӃn ÿӇ trӣ thành phѭѫng pháp ÿѭӧc chӑn trong các ӭng dөng sҳp xӃp thӵc tӃ khác nhau. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 21 II.3.1- Ý tѭӣng Chúng ta vүn xét mҧng a các mҭu tin a[1]..a[n]. Giҧ sӱ v là 1 giá trӏ khóa mà ta gӑi là chӕt (pivot). Ta phân hoҥch dãy a[1]..a[n] thành hai mҧng con "bên trái" và "bên phҧi". Mҧng con "bên trái" bao gӗm các phҫn tӱ có khóa nhӓ hѫn chӕt, mҧng con "bên phҧi" bao gӗm các phҫn tӱ có khóa lӟn hѫn hoһc bҵng chӕt. Sҳp xӃp mҧng con “bên trái” và mҧng con “bên phҧi” thì mҧng ÿã cho sӁÿѭӧc sҳp bӣi vì tҩt cҧ các khóa trong mҧng con “bên trái “ ÿӅu nhӓ hѫn các khóa trong mҧng con “bên phҧi”. ViӋc sҳp xӃp các mҧng con “bên trái” và “bên phҧi” cNJng ÿѭӧc tiӃn hành bҵng phѭѫng pháp nói trên. Mӝt mҧng chӍ gӗm mӝt phҫn tӱ hoһc gӗm nhiӅu phҫn tӱ có khóa bҵng nhau thì xem nhѭÿã có thӭ tӵ. II.3.2- ThiӃt kӃ giҧi thuұt 9ҩn ÿӅ chӑn chӕt Chӑn khóa lӟn nhҩt trong hai phҫn tӱ có khóa khác nhau ÿҫu tiên kӇ tӯ trái qua. NӃu mҧng chӍ Jӗm mӝt phҫn tӱ hay gӗm nhiӅu phҫn tӱ có khóa bҵng nhau thì không có chӕt. 9ҩn ÿӅ phҫn hoҥch ĈӇ phân hoҥch mҧng ta dùng 2 "con nháy" L và R trong ÿó L tӯ bên trái và R tӯ bên phҧi, ta cho L chҥy sang phҧi cho tӟi khi gһp phҫn tӱ có khóa • chӕt và cho R chҥy sang trái cho tӟi khi gһp phҫn tӱ có khóa < chӕt. Tҥi chӛ dӯng cӫa L và R nӃu L<R thì hoán vӏ a[L],a[R]. Lһp lҥi quá trình dӏch sang phҧi, sang trái cӫa 2 "con nháy" L và R cho ÿӃn khi L>R. Khi ÿó L sӁ là ÿLӇm phân hoҥch, cө thӇ là a[L] là phҫn tӱÿҫu tiên cӫa mҧng con “bên phҧi”. Giҧi thuұt QuickSort ĈӇ sҳp xӃp mҧng a[i]..a[j] ta tiӃn hành các bѭӟc sau: · Xác ÿӏnh chӕt, · Phân hoҥch mҧng ÿã cho thành hai mҧng con a[i]..a[k-1] và a[k]..a[j]. · Sҳp xӃp mҧng a[i]..a[k-1] (ĈӋ quy). · Sҳp xӃp mҧng a[k]..a[j] (ĈӋ quy). Quá trình ÿӋ quy sӁ dӯng khi không còn tìm thҩy chӕt. Ví dө 2-4: Ta cҫn sҳp mӝt mҧng mà khóa là các sӕ nguyên ÿã ÿѭӧc trình bày trong ví dө 2-1. Hai phҫn tӱÿҫu tiên có khóa khác nhau là 5 và 6, ta chӑn 6 làm chӕt và tiӃn hành phân hoҥch mҧng ban ÿҫu làm hai mҧng con và ÿӋ quy cho hai mҧng con này. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 22 II.3.3- Cài ÿһt giҧi thuұt Hàm FindPivot Ta thiӃt kӃ hàm FindPivot ÿӇ xác ÿӏnh trong dãy a[i]..a[j] xem có hay không hai phҫn tӱ có khóa khác nhau. NӃu không tìm thҩy hai phҫn tӱ có khóa khác nhau thì trҧ vӅ giá trӏ 0 (không tìm thҩy chӕt), ngѭӧc lҥi hàm trҧ vӅ giá trӏ là chӍ sӕ cӫa phҫn tӱ có khóa lӟn hѫn trong hai phҫn tӱ có khóa khác nhau ÿҫu tiên. Khóa lӟn hѫn này sӁ trӣ thành phҫn tӱ chӕt mà ta sӁ xác ÿӏnh trong thӫ tөc QuickSort. ĈӇ tiӋn so sánh ta sӱ dөng biӃn FirstKey ÿӇ lѭu giӳ khóa cӫa phҫn tӱÿҫu tiên trong mҧng a[i]..a[j] (FirstKey chính là a[i].key). Ta sӁ dùng mӝt chӍ sӕ k ÿӇ dò tìm trong mҧng a[i]..a[j], kӇ tӯ vӏ trí i+1 ÿӃn hӃt mҧng, mӝt phҫn Wӱ a[k] mà a[k].key FirstKey. NӃu không tìm thҩy mӝt a[k] nhѭ thӃ thì hoһc là mҧng chӍ gӗm mӝt phҫn tӱ hoһc gӗm nhiӅu phҫn tӱ có khóa bҵng nhau. Trong trѭӡng hӧp ÿó thì không tìm thҩy chӕt và hàm FindPivot sӁ trҧ vӅ 0. Ngѭӧc lҥi ta sӁ phҧi xét xem a[k].key có lӟn hѫn FirstKey hay không, nӃu ÿúng nhѭ thӃ thì chӕt sӁ là khóa cӫa a[k] và hàm FindPivot sӁ trҧ vӅ k, nӃu không thì hàm FindPivot sӁ trҧ vӅ i. Function FindPivot(i,j:integer): integer; var FirstKey : KeyType; k : integer; begin k := i+1; FirstKey := a[i].key; while (k<=j) and (a[k].key = FirstKey) do k:= k+1; if k > j then FindPivot := 0 else if a[k].key > FirstKey then FindPivot := k else FindPivot := i; end; Hàm Partition Hàm Partition nhұn vào ba tham sӕ i, j và Pivot ÿӇ thӵc hiӋn viӋc phân hoҥch theo mҧng a[i]..a[j] theo chӕt Pivot và trҧ vӅ giá trӏ l là chӍ sӕÿҫu tiên cӫa mҧng “bên phҧi”. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 23 Hai con nháy L, R sӁÿѭӧc sӱ dөng ÿӇ thӵc hiӋn viӋc phân hoҥch nhѭÿã trình bày trong phҫn II.3.2. Function Partition(i,j:integer; pivot :KeyType):integer ; var l,r : integer; begin l := i; {Ĉһt con nháy L ӣì bên trái} r := j; {Ĉһt con nháy R ӣì bên phҧi} while l <= r do begin {L tiӃn sang phҧi} while a[l].key < pivot do l := l+1; {R tiӃn sang trái} while a[r].key >= pivot do r := r-1; if l <r then Swap(a[l],a[r]); end; Partition :=l; end; QuickSort Bây giӡ chúng ta trình bày thӫ tөc cuӕi cùng có tên là QuickSort và chú ý rҵng ÿӇ sҳp xӃp Pҧng A các record gӗm n phҫn tӱ cӫa kiӇu Recordtype ta chӍ cҫn gӑi QuickSort(1,n). Ta sӁ sӱ dөng biӃn PivotIndex ÿӇ lѭu giӳ kӃt quҧ trҧ vӅ cӫa hàm FindPivot, nӃu biӃn PivotIndex nhұn ÿѭӧc mӝt giá trӏ khác 0 thì mӟi tiӃn hành phân hoҥch mҧng. BiӃn Pivot sӁÿѭӧc sӱ Gөng ÿӇ lѭu giӳ giá trӏ chӕt và biӃn k ÿӇ lѭu giӳ giá trӏ cӫa ÿLӇm phân hoҥch do hàm Partition trҧ vӅ. Sau khia ÿã phân hoҥch xong ta sӁ gӑi ÿӋ quy QuickSort cho mҧng con “bên trái” a[i]..a[k-1] và mҧng con “bên phҧi” a[k]..a[j]. procedure Quicksort(i,j:integer); var Pivot : KeyType; PivotIndex, k : integer; begin (1) PivotIndex := FindPivot(i,j); (2) if PivotIndex 0 then begin (3) Pivot := a[PivotIndex].key; (4) k := Partition(i,j,Pivot); (5) QuickSort(i,k-1); (6) QuickSort(k,j); end; end; II.3.4- Thӡi gian thӵc hiӋn cӫa QuickSort QuickSort ḽy O(nlogn) thͥi gian ÿ͋ s̷p x͇p n ph̯n t͵ trong tr˱ͥng hͫp t͙t nh̭t và O(n2). trong tr˱ͥng hͫp x̭u nh̭t. Hàm Partition lҩy thӡi gian tӹ lӋ vӟi sӕ phҫn tӱ cӫa mҧng. Nhѭ vұy nӃu mҧng có n phҫn tӱ thì Partition lҩy P(n)= n ÿѫn vӏ thӡi gian. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 24 Gӑi T(n) là thӡi gian thӵc hiӋn cӫa QuickSort thì T(n) phҧi là tәng cӫa P(n) và thӡi gian QuickSort ÿӋ quy cho hai mҧng con. Giҧ sӱ các giá trӏ khóa cӫa mҧng khác nhau. Trong trѭӡng hӧp xҩu nhҩt là ta luôn chӑn phҧi phҫn tӱ có khóa lӟn nhҩt làm chӕt, lúc bҩy giӡ viӋc phân hoҥch bӏ lӋch tӭc là mҧng bên phҧi chӍ gӗm Pӝt phҫn tӱ chӕt, còn mҧng bên trái gӗm n-1 phҫn tӱ còn lҥi. Khi ÿó ta có thӇ thành lұp phѭѫng trình ÿӋ quy nhѭ sau: Giҧi phѭѫng trình này bҵng phѭѫng pháp truy hӗi Ta có T(n) = T(n-1) + T(1) +n = T(n-1) + (n+1) = [T(n-2) + T(1) +(n-1)] + (n+1) = T(n-2) + n + (n+1) = [T(n-3) + T(1) +(n-2)] + n + (n+1) = T(n-3) +(n-1) + n + (n+1) . . . . . . . . . . . . . . . . . = T(n-i) + (n-i+2) + (n-i+3) + ... + n + (n+1) = T(n-i) + Quá trình trên kӃt thúc khi i=n-1, khi ÿó ta có Trong trѭӡng hӧp tӕt nhҩt khi ta chӑn ÿѭӧc chӕt sao cho hai mҧng con có kích thѭӟc bҵng nhau và bҵng n/2. Lúc ÿó ta có phѭѫng trình ÿӋ quy nhѭ sau: Giҧi phѭѫng trình ÿӋ quy này (xem I.4.2) ta ÿѭӧc T(n) = O(nlogn). Ngѭӡi ta cNJng chӭng minh ÿѭӧc rҵng trong trѭӡng hӧp trung bình QuickSort lҩy T(n) = O(nlogn). II.4- HEAPSORT II.4.1- Heap II.4.2- Ý tѭӣng II.4.3- ThiӃt kӃ và cài ÿһt giҧi thuұt II.4.4- Phân tích HeapSort Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 25 II.4.1- Heap Cây sҳp thӭ tӵ bӝ phұn hay còn gӑi là heap là cây nhӏ phân mà giá trӏ tҥi mӛi nút (khác nút lá) ÿӅu không lӟn hѫn giá trӏ cӫa các con cӫa nó. Ta có nhұn xét rҵng nút gӕc a[1] cӫa cây sҳp thӭ tӵ bӝ phұn có giá trӏ nhӓ nhҩt. Ví dө 2-5: Cây sau là mӝt heap. II.4.2- Ý tѭӣng (1) Xem mҧng ban ÿҫu là mӝt cây nhӏ phân. Mӛi nút trên cây lѭu trNJ mӝt phҫn tӱ mҧng, trong ÿó a[1] là nút gӕc và mӛi nút không là nút lá a[i] có con trái là a[2i] và con phҧi là a[2i+1]. Vӟi cách tә chӭc này thì cây nhӏ phân thu ÿѭӧc sӁ có các nút trong là các nút a[1],..,a[n DIV 2]. Tҩt cҧ các nút trong ÿӅu có 2 con, ngoҥi trӯ nút a[n DIV 2] có thӇ chӍ có mӝt con trái (trong trѭӡng hӧp n là mӝt Vӕ chҹn). (2) Sҳp xӃp cây ban ÿҫu thành mӝt heap căn cӭ vào giá trӏ khoá cӫa các nút. (3) Hoán ÿәi a[1] cho cho phҫn tӱ cuӕi cùng. (4) 6ҳp lҥi cây sau khi ÿã bӓÿi phҫn tӱ cuӕi cùng ÿӇ nó trӣ thành mӝt heap mӟi. Lһp lҥi quá trình (3) và (4) cho tӟi khi cây rӛng ta sӁÿѭӧc mҧng sҳp theo thӭ tӵ giҧm. II.4.3- ThiӃt kӃ và cài ÿһt giҧi thuұt Thӫ tөc PushDown Giҧ sӱ a[first],..,a[last] ÿã ÿúng vӏ trí (giá trӏ khoá tҥi mӛi nút nhӓ hѫn hoһc bҵng giá trӏ khoá Wҥi các nút con cӫa nó) ngoҥi trӯ a[first]. PushDown dùng ÿӇÿҭy phҫn tӱ a[first] xuӕng ÿúng vӏ trí cӫa nó trong cây (và có thӇ gây ra viӋc ÿҭy xuӕng các phҫn tӱ khác). Xét a[first], có hai khҧ năng có thӇ xҧy ra: · NӃu a[first] có khoá lӟn hѫn con trái cӫa nó (a[first].key > a[2*first].key) và khoá cӫa con trái không lӟn hѫn khoá cӫa con phҧi (a[2*first].key ” a[2*first+1].key) thì hoán ÿәi a[first] cho con trái a[2*first] cӫa nó, viӋc này có thӇ gây ra tình trҥng con trái sӁ không ÿúng vӏ trí nên phҧi xem xét lҥi con trái. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 26 · Ngѭӧc lҥi, nӃu a[first] có khoá lӟn hѫn khoá cӫa con phҧi cӫa nó (a[first].key > a[2*first+1].key ) và khoá cӫa con phҧi nhӓ hѫn khoá cӫa con trái (a[2*first+1].key < a[2*first].key) thì hoán ÿәi a[first] cho con phҧi a[2*first+1] cӫa nó, viӋc này có thӇ gây ra tình trҥng con phҧi sӁ không ÿúng vӏ trí nên phҧi tiӃp tөc xem xét con phҧi. · NӃu cҧ hai trѭӡng trên ÿӅu không xҭy ra thì a[first] ÿã ÿúng vӏ trí. · Nhѭ trên ta thҩy viӋc ÿҭy a[first] xuӕng có thӇ gây ra viӋc ÿҭy xuӕng mӝt sӕ phҫn tӱ khác, nên tәng quát là ta sӁ xét viӋc ÿҭy xuӕng cӫa mӝt phҫn tӱ a[r] bҩt kǤ, bҳt ÿҫu tӯ a[first]. procedure PushDown(first,last:integer); var r:integer; begin r:= first; {Xét nút a[first] trѭӟc hӃt} while r <= last div 2 do {Trong khi a[r] còn là nút trong} if last = 2*r then begin {nút r chӍ có con trái } if a[r].key > a[last].key then swap(a[r],a[last]); r:=last; end else if (a[r].key>a[2*r].key)and(a[2*r].key ” a[2*r+1].key)then begin swap(a[r],a[2*r]); r := 2*r ; {Xét tiӃp nút con trái } end else if (a[r].key > a[2*r+1].key) and (a[2*r+1].key < a[2*r].key) then begin swap(a[r],a[2*r+1]); r := 2*r+1 ; {Xét tiӃp nút con phҧi } end else r := last; {Nút r ÿã ÿúng vӏ trí } end; Thӫ tөc HeapSort · ViӋc sҳp xӃp cây ban ÿҫu thành mӝt heap ÿѭӧc tiӃn hành bҵng cách sӱ dөng thӫ tөc PushDown ÿӇÿҭy tҩt cҧ các nút trong chѭa ÿúng vӏ trí xuӕng ÿúng vӏ trí cӫa nó, khӣi ÿҫu tӯ nút a[n DIV 2], lҫn ngѭӧc tӟi gӕc. · Lһp lҥi viӋc hoán ÿәi a[1] cho a[i], sҳp xӃp cây a[1]..a[i-1] thành heap, i chҥy tӯ n ÿӃn 2. procedure HeapSort; var i:integer; begin (1) for i := (n div 2) downto 1 do (2) PushDown(i,n); (3) for i := n downto 2 do begin (4) swap(a[1],a[i]); Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 27 (5) pushdown(1,i-1); end; end; Ví dө 2-6: Sҳp xӃp mҧng bao gӗm 10 phҫn tӱ có khoá là các sӕ nguyên nhѭ trong các ví dө trѭӟc: Khoá a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] Ban ÿҫu 5 6 2 2 10 12 9 10 9 3 Mҧng này ÿѭӧc xem nhѭ là mӝt cây nhӏ phân ban ÿҫu nhѭ sau: Trong cây trên, giá trӏ ghi trong các nút là khoá cӫa các phân tӱ mҧng, giá trӏ ghi bên ngoài các nút là chӍ sӕ cӫa các phҫn tӱ mҧng. ViӋc sҳp xӃp cây này thành mӝt heap sӁ bҳt ÿҫu tӯ viӋc ÿҭy xuӕng nút a[5] (vì 5 = 10 DIV 2) Xét nút 5 ta thҩy a[5] chӍ có mӝt con trái và giá trӏ khóa tѭѫng ӭng cӫa nó lӟn hѫn con trái cӫa nó nên ta ÿәi hai nút này cho nhau và do con trái cӫa a[5] là a[10] là mӝt nút lá nên viӋc ÿҭy xuӕng cӫa a[5] kӃt thúc. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 28 Nút 4 và nút 3 ÿã ÿúng vӏ trí nên không phҧi thӵc hiӋn sӵ hoán ÿәi. Tҥi nút 2, giá trӏ khóa cӫa nó lӟn hѫn khoá con trái và khoá cӫa con trái nhӓ hѫn khoá cӫa con phҧi nên ta hóan ÿәi nút 2 cho con trái cӫa nó (nút 4), sau khi hoán ÿәi, ta xét lҥi nút 4, thҩy nó vүn ÿúng vӏ trí nên kӃt thúc viӋc ÿҭy xuӕng cӫa nút 2. Cuӕi cùng ta xét nút 1, ta thҩy giá trӏ khoá cӫa nút 1 lӟn hѫn khoá cӫa con trái và con trái có khoá bҵng khoá cӫa con phҧi nên hóan ÿәi nút 1 cho con trái cӫa nó (nút 2). Sau khi thӵc hiӋn phép hóan ÿәi nút 1 cho nút 2, ta thҩy nút 2 có giá trӏ khoá lӟn hѫn khoá cӫa con phҧi cӫa nó (nút 5) và con phҧi có khoá nhӓ hѫn khoá cӫa con trái nên phҧi thӵc hiӋn phép hoán ÿәi nút 2 cho nút 5. Xét lҥi nút 5 thì nó vүn ÿúng vӏ trí nên ta ÿѭӧc cây mӟi trong hình 2-9. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 29 Cây này là mӝt heap tѭѫng ӭng vӟi mҧng Khoá a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] Heap 2 3 2 6 5 12 9 10 9 10 Tӯ heap ÿã có ӣ trên, hoán ÿәi a[1] cho a[10] ta có a[10] là nút có khóa nhӓ nhҩt, cҳt bӓ nút a[10] ra khӓi cây. Nhѭ vұy phҫn cuӕi mҧng chӍ gӗm mӝt phҫn tӱ a[10] ÿã ÿѭӧc sҳp. Thӵc hiӋn viӋc ÿҭy a[1] xuӕng ÿúng vӏ trí cӫa nó trong cây a[1]..a[9] ta ÿѭӧc cây: Hoán ÿәi a[1] cho a[9] và cҳt a[9] ra khӓi cây. Ta ÿѭӧc phҫn cuӕi mҧng bao gӗm hai phҫn tӱ a[9]..a[10] ÿã ÿѭӧc sҳp. Thӵc hiӋn viӋc ÿҭy a[1] xuӕng ÿúng vӏ trí cӫa nó trong cây a[1]..a[8] ta ÿѭӧc cây Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 30 TiӃp tөc quá trình trên ta sӁÿѭӧc mӝt mҧng có thӭ tӵ giҧm. II.4.4- Phân tích HeapSort Thӡi gian thӵc hiӋn cӫa HeapSort là O(n logn) Trong thӫ tөc PushDown mӛi lҫn lһp, r có ít nhҩt 2 giá trӏ, vì r bҳt ÿҫu bҵng first nên sau i lҫn Oһp, chúng ta có r • first * 2i. Thӫ tөc dӯng khi r > last/2 do vұy khi thӫ tөc dӯng thì ta có first*2i > last/2 hay 2i+1 > last/first. Suy ra i > log(last/first) - 1 tӭc là sӕ lҫn lһp nhiӅu nhҩt cӫa thӫ tөc PushDown là log(last/first). Vì first •1 và last ” n trong mӛi lҫn gӑi PushDown cӫa thӫ tөc HeapSort tҥi dòng (2) hoһc (5) nên sӕ lҫn lһp ” logn, mӛi bѭӟc lһp lҩy mӝt thӡi gian O(1) nên thӡi gian thӵc hiӋn cӫa PushDown là O(logn). Trong thӫ tөc HeapSort dòng lӋnh (1)-(2) lһp n/2 lҫn mà mӛi lҫn lҩy O(logn) nên thӡi gian thӵc hiӋn (1)-(2) là O(n logn). Vòng lһp (3)-(4)-(5) lһp n-1 lҫn, mӛi lҫn lҩy O(logn) nên thӡi gian thӵc hiӋn (3)-(4)-(5) là O(n logn). Tóm lҥi thӡi gian thӵc hiӋn HeapSort là O(n logn) II.5- BINSORT II.5.1- Giҧi thuұt II.5.2- Phân tích Bin Sort II.5.3- Sҳp xӃp tұp giá trӏ có khoá lӟn II.5.1- Giҧi thuұt Nói chung các giҧi thuұt ÿã trình bày ӣ trên ÿӅu có ÿӝ phӭc tҥp là O(n2) hoһc O(nlogn). Tuy nhiên khi kiӇu dӳ liӋu cӫa trѭӡng khoá là mӝt kiӇu ÿһc biӋt , viӋc sҳp xӃp có thӇ chӍ chiӃm O(n) thӡi gian. Sau ÿây ta sӁ xét mӝt sӕ trѭӡng hӧp. Trѭӡng hӧp ÿѫn giҧn: Giҧ sӱ ta phҧi sҳp xӃp mӝt mҧng A gӗm n phҫn tӱ có khoá là các sӕ nguyên có giá trӏ khác nhau và là các giá trӏ tӯ 1 ÿӃn n. Ta sӱ dөng B là mӝt mҧng cùng kiӇu vӟi A và phân phӕi vào phҫn tӱ b[j] mӝt phҫn tӱ a[i] mà a[i].key = j. Khi ÿó mҧng B lѭu trӳ kӃt quҧÿã ÿѭӧc sҳp [Ӄp cӫa mҧng A. Ví dө 2-7: Sҳp xӃp mҧng A gӗm 10 phҫn tӱ có khoá là các sӕ nguyên có giá trӏ là các sӕ 4, 5, Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 31 2, 1, 7, 8, 10, 9, 6 và 3 Ta sӱ dөng mҧng B có cùng kiӇu vӟi A và thӵc hiӋn viӋc phân phӕi a[1] vào b[4] vì a[1].key = 4, a[2] vào b[5] vì a[2].key = 5, a[3] vào b[2] vì a[3].key = 2,... ĈӇ thӵc hiӋn viӋc phân phӕi này ta chӍ cҫn mӝt lӋnh lһp: for i:=1 to n do B[A[i].key] := A[i] Ĉây cNJng là lӋnh chính trong chѭѫng trình sҳp xӃp. LӋnh này lҩy O(n) thӡi gian. Các phҫn tӱ b[j] ÿѭӧc gӑi là các bin và phѭѫng pháp sҳp xӃp này ÿѭӧc gӑi là bin sort. Trѭӡng hӧp tәng quát: Là trѭӡng hӧp có thӇ có nhiӅu phҫn tӱ có chung mӝt giá trӏ khóa, chҷng hҥn ÿӇ sҳp mӝt mҧng A có n phҫn tӱ mà các giá trӏ khóa cӫa chúng là các sӕ nguyên lҩy giá trӏ trong khoҧng 1..m vӟi m ” n. Trong trѭӡng hӧp này ta không thӇ sӱ dөng các phҫn tӱ cӫa mҧng B làm bin ÿѭӧc vì nӃu có hai phҫn tӱ cӫa mҧng A có cùng mӝt khoá thì không thӇ lѭu trӳ trong cùng mӝt bin. ĈӇ giҧi quyӃt sӵÿөng ÿӝ này ta chuҭn bӏ mӝt cҩu trúc có m bin, mӛi bin có thӇ lѭu trӳ nhiӅu Kѫn mӝt phҫn tӱ. Cө thӇ là bin thӭ j sӁ lѭu các phҫn tӱ có khóa là j (1 ” j ” m) sau ÿó ta sӁ nӕi các bin Oҥi vӟi nhau ÿӇÿѭӧc mӝt dãy các phҫn tӱÿѭӧc sҳp. Cách tӕt nhҩt là ta thiӃt kӃ mӛi bin là mӝt danh sách liên kӃt cӫa các phҫn tӱ mà mӛi phҫn tӱ có kiӇu RecordType. Ta sӁ gӑi kiӇu cӫa danh sách này là ListType. Ta có thӇ tҥo kiӇu ListType bҵng cách ghép RecordType vӟi mӝt con trӓÿӇ trӓ tӟi phҫn tӱ kӃ tiӃp. Lҩy B là mӝt mҧng kiӇu Array[KeyType] of ListType. Nhѭ vұy B là mҧng các bin, mӛi bin là Pӝt danh sách. B ÿѭӧc ÿánh chӍ sӕ bӣi KeyType, nhѭ thӃ có ít nhҩt mӝt bin cho mӛi giá trӏ khoá. Ta vүn sӁ phân phӕi phҫn tӱ a[i] vào bin b[j] nӃu j = a[i]key. Dƭ nhiên mӛi bin b[j] có thӇ chӭa nhiӅu phҫn tӱ cӫa mҧng A. Các phҫn tӱ mӟi sӁÿѭӧc ÿѭa vào cuӕi danh sách b[j]. Sau khi tҩt cҧ các phҫn tӱ cӫa mҧng A ÿã ÿѭӧc phân phӕi vào trong các bin, công viӋc cuӕi cùng là ta phҧi nӕi các bin lҥi vӟi nhau, ta sӁÿѭӧc mӝt danh sách có thӭ tӵ. Ta sӁ dùng thӫ tөc concatenate(L1,L2) ÿӇ nӕi hai danh sách L1, L2. Nó thay thӃ danh sách L1 bӣi danh sách nӕi L1L2. ViӋc Qӕi sӁÿѭӧc thӵc hiӋn bҵng cách gҳn con trӓ cӫa phҫn tӱ cuӕi cùng cӫa L1 vào ÿҫu cӫa L2. Ta biӃt rҵng ÿӇÿӃn ÿѭӧc phҫn tӱ cuӕi cùng cӫa danh sách liên kӃt L1 ta phҧi duyӋt qua tҩt cҧ các phҫn tӱ cӫa nó. ĈӇ cho có hiӋu quҧ, ta thêm mӝt con trӓ nӳa, trӓÿӃn phҫn tӱ cuӕi cùng cӫa mӛi danh sách, ÿLӅu này giúp ta ÿi thҷng tӟi phҫn tӱ cuӕi cùng mà không phҧi duyӋt qua toàn bӝ danh sách. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 32 Hình 2-13 minh hӑa viӋc nӕi hai danh sách. Sau khi nӕi thì header và end cӫa danh sách L2 không còn tác dөng nӳa. Ví dө 2-8: Sҳp xӃp mҧng A gӗm 10 phҫn tӱ có khoá là các sӕ nguyên có giá trӏ là các sӕ 2, 4, 1, 5, 4, 2, 1, 4, 1, 5. A a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] Khoá cӫa A 2 4 1 5 4 2 1 4 1 5 Ta thҩy các giá trӏ khoá nҵm trong khoҧng 1..5. Ta tә chӭc mӝt mҧng B gӗm 5 phҫn tӱ, mӛi phҫn tӱ là mӝt con trӓ, trӓÿӃn mӝt danh sách liên kӃt . Chѭѫng trình sӱ dөng cҩu trúc danh sách liên kӃt làm các bin VAR A: array[1..n] of RecordType; Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 33 B: array[keytype] of ListType; {Ta giҧ thiӃt keytype là kiӇu miӅn con 1..m } procedure BinSort; var i:integer; j: KeyType; begin {1}for i:=1 to n do INSERT(A[i], END(B[A[i].key]), B[A[i}.key]); {2}for j:= 2 to m do CONCATENATE(B[1], B[j]); end; II.5.2- Phân tích Bin Sort Bin sort ḽy O(n) thͥi gian ÿ͋ s̷p x͇p m̫ng g͛m n ph̯n t͵. Trѭӟc hӃt thӫ tөc INSERT cҫn mӝt thӡi gian O(1) ÿӇ xen mӝt phҫn tӱ vào trong danh sách. Do cách tә chӭc danh sách có giNJ con trӓÿӃn phҫn tӱ cuӕi cùng nên viӋc nӕi hai danh sách bҵng thӫ tөc CONCATENATE cNJng chӍ mҩt O(1) thӡi gian. Ta thҩy vòng lһp {1} thӵc hiӋn n lҫn, mӛi lҫn tӕn O(1) = 1 nên lҩy O(n) ÿѫn vӏ thӡi gian. Vòng lһp {2} thӵc hiӋn m-1 lҫn, mӛi lҫn O(1) nên tӕn O(m) ÿѫn vӏ thӡi gian. Hai lӋnh {1} và {2} nӕi tiӃp nhau nên thӡi gian thӵc hiӋn cӫa BinSort là T(n) = O(max(n,m)) = O(n) vì m ” n. II.5.3- Sҳp xӃp tұp giá trӏ có khoá lӟn NӃu m sӕ các khoá không lӟn hѫn n sӕ các phҫn tӱ cҫn sҳp xӃp, khi ÿó O(max(n,m)) thӵc sӵ là O(n). NӃu giҧ sӱ m = n2 khi ÿó O(max(n, n2)) là O(n2) nhѭ vұy Bin sort lҩy O(n2) thӡi gian. Tuy nhiên ta vүn có thӇ tәng quát hoá kӻ thuұt bin sort ÿӇ nó vүn lҩy O(n) thӡi gian. Giҧ sӱ ta cҫn sҳp xӃp n phҫn tӱ có các giá trӏ khoá thuӝc 0..n2-1. Ta sӁ sӱ dөng n bin B[0], B[1],...B[n-1] và tiӃn hành viӋc sҳp xӃp trong hai kǤ. KǤ 1: Phân phӕi phҫn tӱ a[i] vào bin B[j] mà j = a[i].key MOD n. KǤ 2: Phân phӕi các phân tӱ trong danh sách kӃt quҧ cӫa kǤ 1 vào các bin. Phҫn tӱ a[i] sӁÿѭӧc phân phӕi vào bin B[j] mà j = a[i].key DIV n. Chú ý rҵng trong cҧ hai kǤ, ta xen các phҫn tӱ mӟi ÿѭӧc phân phӕi vào cuӕi danh sách. Ví dө 2-9: Cҫn sҳp xӃp mҧng gӗm 10 phҫn tӱ có khoá là các sӕ nguyên: 36, 9, 0, 25, 1, 49, 64, 16, 81 và 4. Ta sӱ dөng 10 bin ÿѭӧc ÿánh sӕ tӯ 0 ÿӃn 9. KǤ mӝt ta phân phӕi phҫn tӱ a[i] vào bin có chӍ sӕ a[i].key MOD 10. Nӕi các bin lҥi vӟi nhau ta ÿѭӧc danh sách có khóa là: 0 1 81 64 4 25 36 16 9 49. KǤ hai sӱ dөng kӃt quҧ cӫa kǤ 1 ÿӇ sҳp tiӃp. Phân phӕi phҫn tӱ a[i] vào bin có chӍ sӕ a[i].key DIV 10. Nӕi các bin lҥi vӟi nhau ta ÿѭӧc danh sách có thӭ tӵ. .Ǥ 1 KǤ 2 Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 34 Bin Bin 0 0 0 0 1 4 9 1 1 81 1 16 2 2 25 3 3 36 4 64 4 4 49 5 25 5 6 36 16 6 64 7 7 8 8 81 9 9 49 9 Hình 2-13: S̷p x͇p theo hai kǤ Theo sӵ phân tích giҧi thuұt Bin Sort thì mӛi kǤ lҩy O(n) thӡi gian, hai kǤ này nӕi tiӃp nhau nên thӡi gian tәng cӝng là O(n). Chӭng minh giҧi thuұt ÿúng ĈӇ thҩy tính ÿúng ÿҳn cӫa giҧi thuұt ta xem các các giá trӏ khóa nguyên tӯ 0 ÿӃn n2-1 nhѭ các Vӕ có hai chӳ sӕ trong hӋÿӃm cѫ sӕ n. Xét hai sӕ k = sn + t và l = un + v trong ÿó s, t, u, v là các sӕ 0..n-1. Giҧ sӱ k < l, ta cҫn chӭng minh rҵng sau 2 kǤ sҳp thì k phҧi ÿӭng trѭӟc l. Vì k < l nên s ” u. NӃu s < u thì k ÿӭng trѭӟc l trong danh sách kӃt qӫa vì k ÿѭӧc sҳp vào bin b[s] và l ÿѭӧc sҳp vào bin b[u] mà b[s] ÿӭng trѭӟc b[u]. NӃu s=u thì t<v. Sau kǤ 1 thì k ÿӭng trѭӟc l, vì k ÿѭӧc sҳp vào trong bin b[t] và l trong bin b[v]. ĈӃn kǤ 2 mһc dù cҧ k và l ÿӅu ÿѭӧc sҳp vào trong bin b[s], nhѭng k ÿѭӧc xen vào trѭӟc l nên kӃt quҧ là k ÿӭng trѭӟc l. Chú ý 7ӯ chӭng minh trên ta thҩy ÿӇ sҳp các phҫn tӱ có khóa là các sӕ nguyên (hӋÿӃm cѫ sӕ 10) tӯ 0 ÿӃn 99 ta dùng 10 bin có chӍ sӕ tӯ 0 ÿӃn 9. ĈӇ sҳp các phҫn tӱ có khóa là các sӕ nguyên tӯ 0 ÿӃn 999 ta dùng 100 bin có chӍ sӕ tӯ 0 ÿӃn 99... Bài 1: Sɬp xɼp mɠng g͓m 12 phɤn tͭ có khóa là các s͑ nguyên : 5, 15, 12, 2, 10, 12, 9, 1, 9, 3, 2, 3 Eɮng cách sͭ dͥng: a) Sɬp xɼp ch͍n. b) Sɬp xɼp xen. c) Sɬp xɼp n͕i b͍t. d) QuickSort. e) HeapSort. Bài 2: Có m͙t biɼn thʀ cͧa sɬp xɼp ch͍n nhɉ sau: Trong bɉ͛c thͩ i ta ch͍n m͙t phɤn tͭ có Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 35 khóa nh͏ nhɢt và m͙t phɤn tͭ có khóa l͛n nhɢt trong a[i]...a[n-i+1] và hóan ÿ͕i phɤn tͭ nh͏ nhɢt cho a[i] và phɤn tͭ l͛n nhɢt cho a[n-i+1]. Hãy viɼt thͧ tͥc sɬp xɼp ch͍n theo giɠi thuɪt này và tính th͝i gian thͱc hiʄn. Bài 3: Viɼt thͧ tͥc sɬp xɼp tr͙n (xem giɠi thuɪt thô trong chɉɇng 1). Bài 4: Có m͙t biɼn thʀ cͧa QuickSort nhɉ sau: Ch͍n ch͑t là khóa cͧa phɤn tͭ nh͏ nhɢt trong hai phɤn tͭ có khóa khác nhau ÿɤu tiên. Mɠng con bên trái g͓m các phɤn tͭ có khóa nh͏ hɇn hoɴc bɮng ch͑t, mɠng con bên phɠi g͓m các phɤn tͭ có khóa l͛n hɇn ch͑t. Hãy viɼt lɞi các thͧ tͥc Fɤn thiɼt cho biɼn thʀ này. Bài 5: M͙t biɼn thʀ khác cͧa QuickSort là ch͍n khóa cͧa phɤn tͭÿɤu tiên làm ch͑t. Hãy viɼt lɞi các thͧ tͥc cɤn thiɼt cho biɼn thʀ này. Bài 6: Hãy viɼt lɞi thͧ tͥc PushDown trong HeapSort ÿʀ có thʀ sɬp xɼp theo thͩ tͱ tăng. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 36 1. Mөc tiêu 2. KiӃn thӭc cѫ bҧn cҫn có ÿӇ hӑc chѭѫng này 3. Tài liӋu tham khҧo có liên quan ÿӃn chѭѫng 4. Nӝi dung: III.1 - Giҧi thuұt chia ÿӇ trӏ III.2 - Quy hoҥch ÿӝng III.3 - Kӻ thuұt "tham ăn" III.4 - Kӻ thuұt quay lui III.5 - Kӻ thuұt tìm kiӃm ÿӏa phѭѫng 5. Vҩn ÿӅ nghiên cӭu cӫa trang kӃ tiӃp Nói chung khi thiӃt kӃ mӝt giҧi thuұt chúng ta thѭӡng dӵa vào mӝt sӕ kӻ thuұt nào ÿó. Chѭѫng này sӁ trình bày mӝt sӕ kӻ thuұt quan trӑng ÿӇ thiӃt kӃ giҧi thuұt nhѭ: Chia ÿӇ trӏ (Divide-and- Conquer), quy hoҥch ÿӝng (dynamic programming), kӻ thuұt tham ăn (greedy techniques), quay lui (backtracking) và tìm kiӃm ÿӏa phѭѫng (local search). Các kӻ thuұt này ÿѭӧc áp dөng vào mӝt lӟp Uӝng các bài toán, trong ÿó có nhӳng bài toán nәi tiӃng nhѭ bài toán tìm ÿѭӡng ÿi ngҳn nhҩt cӫa ngѭӡi giao hàng, bài toán cây phӫ tӕi tiӇu... III.1- GIҦI THUҰT CHIA Ĉӆ TRӎ III.1.1- Nӝi dung kӻ thuұt III.1.2- Nhìn nhұn lҥi giҧi thuұt MergeSort và QuickSort III.1.3- Bài toán nhân các sӕ nguyên lӟn III.1.4- XӃp lӏch thi ÿҩu thӇ thao III.1.5- Bài toán con cân bҵng III.1.1- Nӝi dung kӻ thuұt Có thӇ nói rҵng kӻ thuұt quan trӑng nhҩt, ÿѭӧc áp dөng rӝng rãi nhҩt ÿӇ thiӃt kӃ các giҧi thuұt có hiӋu quҧ là kӻ thuұt "chia ÿӇ trӏ" (divide and conquer). Nӝi dung cӫa nó là: ĈӇ giҧi mӝt bài toán kích thѭӟc n, ta chia bài toán ÿã cho thành mӝt sӕ bài toán con có kích thѭóc nhӓ hѫn. Giҧi các bài toán con này rӗi tәng hӧp kӃt quҧ lҥi ÿӇÿѭӧc lӡi giҧi cӫa bài toán ban ÿҫu. Ĉӕi vӟi các bài toán con, chúng ta lҥi sӱ dөng kӻ thuұt chia ÿӇ trӏÿӇ có ÿѭӧc các bài toán kích thѭӟc nhӓ hѫn nӳa. Quá trình trên VӁ dүn ÿӃn nhӳng bài toán mà lӡi giҧi chúng là hiӇn nhiên hoһc GӉ dàng thӵc hiӋn, ta gӑi các bài toán này là bài toán cѫ sӣ. Tóm lҥi kӻ thuұt chia ÿӇ trӏ bao gӗm hai quá trình: Phân tích bài toán ÿã cho thành các bài toán cѫ sӣ và Wәng hӧp kӃt quҧ tӯ bài toán cѫ sӣÿӇ có lӡi giҧi cӫa bài toán ban ÿҫu. Tuy nhiên ÿӕi vӟi Pӝt sӕ bài toán, thì quá trình phân tích ÿã chӭa ÿӵng viӋc tәng hӧp kӃt quҧ do ÿó nӃu chúng ta ÿã giҧi xong các bài toán cѫ sӣ thì bài toán ban ÿҫu cNJng ÿã ÿѭӧc giҧi quyӃt. Ngѭӧc lҥi có nhӳng bài toán mà quá trình phân tích thì ÿѫn giҧn nhѭng viӋc tәng hӧp kӃt quҧ lҥi rҩt khó khăn. Trong các phҫn tiӃp sau ta sӁ trình bày mӝt sӕ ví dөÿӇ thҩy rõ hѫn ÿLӅu này. .ӻ thuұt này sӁ cho chúng ta mӝt giҧi thuұt ÿӋ quy mà viӋc xác ÿӏnh ÿӝ phӭc tҥp cӫa nó sӁ phҧi giҧi mӝt phѭѫng trình ÿӋ quy nhѭ trong chѭѫng I ÿã trình bày. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 37 III.1.2 Nhìn nhұn lҥi giҧi thuұt MergeSort và QuickSort Hai giҧi thuұt sҳp xӃp ÿã ÿѭӧc trình bày trong các chѭѫng trѭӟc (MergeSort trong chѭѫng I và QuickSort trong chѭѫng II) thӵc chҩt là ÿã sӱ dөng kӻ thuұt chia ÿӇ trӏ. 9ӟi MergeSort, ÿӇ sҳp mӝt danh sách L gӗm n phҫn tӱ, chúng ta chia L thành hai danh sách con L1 và L2 mӛi danh sách có n/2 phҫn tӱ. Sҳp xӃp L1, L2 và trӝn hai danh sách ÿã ÿѭӧc sҳp này ÿӇ ÿѭӧc mӝt danh sách có thӭ tӵ. Quá trình phân tích ӣÿây là quá trình chia ÿôi mӝt danh sách, quá trình này sӁ dүn ÿӃn bài toán sҳp xӃp mӝt danh sách có ÿӝ daì bҵng 1, ÿây chính là bài toán cѫ sӣ vì viӋc sҳp [Ӄp danh sách này là “không làm gì cҧ”. ViӋc tәng hӧp các kӃt quҧӣÿây là “trӝün 2 danh sách ÿã ÿѭӧc sҳp ÿӇÿѭӧc mӝt danh sách có thӭ tӵ”. 9ӟi QuickSort, ÿӇ sҳp xӃp mӝt danh sách gӗm n phҫn tӱ, ta tìm mӝt giá trӏ chӕt và phân hoҥch danh sách ÿã cho thành hai danh sách con “bên trái” và “bên phҧi “. Sҳp xӃp “bên trái” và “bên phҧi” thì ta ÿѭӧc danh sách có thӭ tӵ. Quá trình phân chia sӁ dүn ÿӃn các bài toán sҳp xӃp mӝt danh sách chӍ Jӗm mӝt phҫn tӱ hoһc gӗm nhiӅu phҫn tӱ có khoá bҵng nhau, ÿó chính là các bài toán cѫ sӣ, vì bҧn thân chúng ÿã có thӭ tӵ rӗi. Ӣÿây chúng ta cNJng không có viӋc tәng hӧp kӃt quҧ mӝt cách tѭӡng minh, vì viӋc ÿó ÿã ÿѭӧc thӵc hiӋn trong quá trình phân hoҥch. III.1.3- Bài toán nhân các sӕ nguyên lӟn Xét bài toán nhân hai sӕ nguyên n chӳ sӕ X và Y. Theo giҧi thuұt nhân hai sӕ thông thѭӡng thì Fҫn n2 phép nhân và n phép cӝng nên tӕn O(n2) thӡi gian. Áp dөng kӻ thuұt "chia ÿӇ trӏ" vào phép nhân các sӕ nguyên, ta chia mӛi sӕ nguyên X và Y thành các sӕ nguyên có n/2 chӳ sӕ. ĈӇÿѫn giҧn ta giҧ sӱ n là luӻ thӯa cӫa 2 X = A10n/2 + B Y = C10n/2 + D Trong ÿó A, B, C, D là các sӕ nguyên có n/2 chӳ sӕ. Chҷng hҥn vӟi X = 1234 thì A = 12 và B = 34 bӣi vì X = 12 *102 + 34. Tích cӫa X và Y có thӇÿѭӧc viӃt thành: XY = AC10n+(AD + BC)10n/2 + BD (III.1) 9ӟi mӛi sӕ có n/2 chӳ sӕ, chúng ta lҥi tiӃp tөc phân tích theo cách trên, quá trình phân tích sӁ Gүn ÿӃn bài toán cѫ sӣ là nhân các sӕ nguyên chӍ gӗm mӝt chӳ sӕ mà ta dӉ dàng thӵc hiӋn. ViӋc tәng Kӧp kӃt quҧ chính là thӵc hiӋn các phép toán theo công thӭc (III.1). Theo (III.1) thì chúng ta phҧi thӵc hiӋn 4 phép nhân các sӕ nguyên n/2 chӳ sӕ (AC, AD, BC, BD), sau ÿó tәng hӧp kӃt quҧ bҵng 3 phép cӝng các sӕ nguyên n chӳ sӕ và 2 phép nhân vӟi 10n và 10n/2. Các phép cӝng các sӕ nguyên n chӳ sӕ dƭ nhiên chӍ cҫn O(n). Phép nhân vӟi 10n có thӇ thӵc hiӋn mӝt cách ÿѫn giҧn bҵng cách thêm vào n chӳ sӕ 0 và do ÿó cNJng chӍ lҩy O(n). Gӑi T(n) là thӡi gian ÿӇ nhân hai sӕ nguyên, mӛi sӕ có n chӳ sӕ thì tӯ (III.1) ta có: T(1) = 1 T(n) = 4T(n/2) + cn (III.2) Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 38 Giҧi (III.1) ta ÿѭӧc T(n) = O(n2). Nhѭ vұy thì chҷng cҧi tiӃn ÿѭӧc chút nào so vӟi giҧi thuұt nhân hai sӕ bình thѭӡng. ĈӇ cҧi thiӋn tình hình, chúng ta có thӇ viӃt lҥi (III.1) thành dҥng: XY = AC10n + [(A-B)(D-C) + AC + BD] 10n/2+ BD (III.3) Công thӭc (III.3) chӍÿòi hӓi 3 phép nhân cӫa các sӕ nguyên n/2 chӳ sӕ là: AC, BD và (A- B)(D-C), 6 phép cӝng trӯ và 2 phép nhân vӟi 10n. Các phép toán này ÿӅu lҩy O(n) thӡi gian. Tӯ (III.3) ta có phѭѫng trình ÿӋ quy: T(1) = 1 T(n) = 3T(n/2) + cn Giҧi phѭѫng trình ÿӋ quy này ta ÿѭӧc nghiӋm T(n) = O(nlog3) = O(n1.59). Giҧi thuұt này rõ ràng ÿã ÿѭӧc cҧi thiӋn rҩt nhiӅu. Giҧi thuұt thô ÿӇ nhân hai sӕ nguyên (dѭѫng hoһc âm) n chӳ sӕ là: function Mult(x,y:integer; n:integer) : integer; var m1,m2,m3,A,B,C,D: integer; s:integer;{Lѭu trӳ dҩu cӫa tích xy} begin s := sign(x)*sign(y); {Hàm sign có giá trӏ 1 nӃu x dѭѫng và –1 nӃu x âm} x := ABS(x);{Lҩy trӏ tuyӋt ÿӕi cӫa x} y := ABS(y); if n = 1 then mult:=x*y*s else begin A := left( x, n DIV 2); B := right(x, n DIV 2); C := left(y, n DIV 2); D := right(y, n DIV 2); m1 := mult(A,C, n DIV 2); m2 := mult(A-B,D-C, n DIV 2); m3 := mult(B,D, n DIV 2); mult := (s * (m1 * 10n + (m1+m2+m3)* 10 n DIV 2 + m3)); end end; III.1.4- XӃp lӏch thi ÿҩu thӇ thao Kӻ thuұt chia ÿӇ trӏ không nhӳng chӍ có ӭng dөng trong thiӃt kӃ giҧi thuұt mà còn trong nhiӅu Oƭnh vӵc khác cӫa cuӝc sӕng. Chҷng hҥn xét viӋc xӃp lӏch thi ÿҩu thӇ thao theo thӇ thӭc ÿҩu vòng tròn 1 Oѭӧt cho n cҫu thӫ. Mӛi cҫu thӫ phҧi ÿҩu vӟi các cҫu thӫ khác, và mӛi cҫu thӫ chӍÿҩu nhiӅu nhҩt mӝt trұn mӛi ngày. Yêu cҫu là xӃp mӝt lӏch thi ÿҩu sao cho sӕ ngày thi ÿҩu là ít nhҩt. Ta dӉ dàng thҩy rҵng Wәng sӕ trұn ÿҩu cӫa toàn giҧi là n(n-1)/2. Nhѭ vұy nӃu n là mӝt sӕ chҹn thì ta có thӇ sҳp n/2 cһp thi ÿҩu trong mӝt ngày và do ÿó cҫn ít nhҩt n-1 ngày. Ngѭӧc lҥi nӃu n là mӝt sӕ lҿ thì n-1 là mӝt sӕ chҹn nên ta có thӇ sҳp (n-1)/2 cһp thi ÿҩu trong mӝt ngày và do ÿó ta cҫn n ngày. Giҧ sӱ n = 2k thì n là mӝt sӕ chҹnUpload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 39 và do ÿó cҫn tӕi thiӇu n-1 ngày. Lӏch thi ÿҩu là mӝt bҧng n dòng và n-1 cӝt. Các dòng ÿѭӧc ÿánh sӕ tӯ 1 ÿӃn n và các cӝt ÿѭӧc ÿánh sӕ tӯ 1 ÿӃn n-1, trong ÿó dòng i biӇu diӉn cho cҫu thӫ i, cӝt j biӇu diӉn cho ngày thi ÿҩu j và ô(i,j) ghi cҫu thӫ phҧi thi ÿҩu vӟi cҫu thӫ i trong ngày j. ChiӃn lѭӧc chia ÿӇ trӏ xây dӵng lӏch thi ÿҩu nhѭ sau: ĈӇ sҳp lӏch cho n cҫu thӫ, ta sӁ sҳp lӏch cho n/2 cҫu thӫ, ÿӇ sҳp lӏch cho n/2 cҫu thӫ, ta sӁ sҳp lӏch cho n/4 cҫu thӫ... Quá trình này sӁ dүn ÿӃn bài toán cѫ sӣ là sҳp lӏch thi ÿҩu cho 2 cҫu thӫ. Hai cҫu thӫ này sӁ thi ÿҩu mӝt trұn trong mӝt ngày, lӏch thi ÿҩu cho hӑ thұt dӉ sҳp. Khó khăn chính là ӣ chӛ tӯ các lӏch thi ÿҩu cho hai cҫu thӫ, ta tәng hӧp lҥi ÿӇÿѭӧc lӏch thi ÿҩu cӫa 4 cҫu thӫ, 8 cҩu thӫ, ... Xuҩt phát tӯ lӏch thi ÿҩu cho hai cҫu thӫ ta có thӇ xây dӵng lӏch thi ÿҩu cho 4 cҫu thӫ nhѭ sau: /ӏch thi ÿҩu cho 4 cҫu thӫ sӁ là mӝt bҧng 4 dòng, 3 cӝt. Lӏch thi ÿҩu cho 2 cҫu thӫ 1 và 2 trong ngày thӭ 1 chính là lӏch thi ÿҩu cӫa hai cҫu thӫ (bài toán cѫ sӣ). Nhѭ vұy ta có Ô(1,1) = “2” và Ô(2,1) = “1”. 7ѭѫng tӵ ta có lӏch thi ÿҩu cho 2 cҫu thӫ 3 và 4 trong ngày thӭ 1. Nghƭa là Ô(3,1) =”4” và Ô(4,1) = “3”. (Ta cӕ thӇ thҩy rҵng Ô(3,1) = Ô(1,1) + 2 và Ô(4,1) = Ô(2,1) + 2 ). Bây giӡÿӇ hoàn thành lӏch thi ÿҩu cho 4 cҫu thӫ, ta lҩy góc trên bên trái cӫa bҧng lҳp vào cho góc dѭӟi bên phҧi và lҩy góc dѭӟi bên trái lҳp cho góc trên bên phҧi. Lӏch thi ÿҩu cho 8 cҫu thӫ là mӝt bҧng gӗm 8 dòng, 7 cӝt. Góc trên bên trái chính là lӏch thi ÿҩu trong 3 ngày ÿҫu cӫa 4 cҫu thӫ tӯ 1 ÿӃn 4. Các ô cӫa góc dѭӟi bên trái sӁ bҵng các ô tѭѫng ӭng cӫa góc trên bên trái cӝng vӟi 4. Ĉây chính là lӏch thi ÿҩu cho 4 cҫu thӫ 5, 6, 7 và 8 trong 3 ngày ÿҫu. Bây giӡ chúng ta hoàn thành viӋc sҳp lӏch bҵng cách lҩp ÿҫy góc dѭӟi bên phҧi bӣi góc trên bên trái và góc trên bên phҧi bӣi góc dѭӟi bên trái. III.1.5- Bài toán con cân bҵng (Balancing Subproblems) Ĉӕi vӟi kӻ thuұt chia ÿӇ trӏ, nói chung sӁ tӕt hѫn nӃu ta chia bài toán cҫn giҧi thành các bài toán con có kích thѭӟc gҫn bҵng nhau. Ví dө, sҳp xӃp trӝn (MergeSort) phân chia bài toán thành hai bài toán con có cùng kích thѭӟc n/2 và do ÿó thӡi gian cӫa nó chӍ là O(nlogn). Ngѭӧc lҥi trong trѭӡng hӧp [ҩu nhҩt cӫa QuickSort, khi mҧng bӏ phân hoҥch lӋch thì thӡi gian thӵc hiӋn là O(n2). Nguyên tҳc chung là chúng ta tìm cách chia bài toán thành các bài toán con có kích thѭӟc xҩp xӍ bҵng nhau thì hiӋu suҩt sӁ cao hѫn. III.2- QUY HOҤCH ĈӜNG Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 40 III.2.1- Nӝi dung kӻ thuұt III.2.2- Bài toán tính sӕ tә hӧp III.2.1- Nӝi dung kӻ thuұt Nhѭ trong III.1 chúng ta ÿã nói, kӻ thuұt chia ÿӇ trӏ thѭӡng dүn chúng ta tӟi mӝt giҧi thuұt ÿӋ quy. Trong các giҧi thuұt ÿó, có thӇ có mӝt sӕ giҧi thuұt thӡi gian mNJ. Tuy nhiên, thѭӡng chӍ có mӝt sӕ ÿa thӭc các bài toán con, ÿLӅu ÿó có nghƭa là chúïng ta ÿã phҧi giҧi mӝt sӕ bài toán con nào ÿó trong nhiӅu lҫn. ĈӇ tránh viӋc giҧi dѭ thӯa mӝt sӕ bài toán con, chúng ta tҥo ra mӝt bҧng lѭu tҩt cҧ kӃt quҧ Fӫa các bài toán con và khi cҫn chúng ta chӍ cҫn tham khҧo tӟi kӃt quҧÿã ÿѭӧc lѭu trong bҧng mà không cҫn phҧi giҧi lҥi bài toánÿó. Lҩp ÿҫy bҧng kӃt quҧ các bài toán con theo mӝt quy luұt nào ÿó ÿӇ nhұn ÿѭӧc kӃt quҧ cӫa bài toán ban ÿҫu (cNJng ÿã ÿѭӧc lѭu trong mӝt ô nào ÿó cӫa bҧng) ÿѭӧc gӑi là quy hoҥch ÿӝng. III.2.2- Bài toán tính sӕ tә hӧp Mӝt bài toán khá quen thuӝc vӟi chúng ta là tính sӕ tә hӧp chұp k cӫa n theo công thӭc: Ckn = 1 nӃu k=0 hoһc k = n Ckn = Ck-1n-1 + Ckn-1 nӃu 0 < k < n Công thӭc trên ÿã gӧi ý cho chúng ta mӝt giҧi thuұt ÿӋ quy nhѭ sau: function Comb(n,k : integer) : Integer; begin if (k=0) or (k=n) then Comb := 1 else Comb := Comb(n-1, k-1) + Comb(n-1,k); end; Gӑi T(n) là thӡi gian ÿӇ tính sӕ tә hӧp chұp k cӫa n, thì ta có phѭѫng trình ÿӋ quy: T(1) = C1 T(n) = 2T(n-1) + C2 Giҧi phѭѫng trình này ta ÿѭӧc T(n) = O(2n), nhѭ vұy là mӝt giҧi thuұt thӡi gian mNJ, trong khi chӍ có mӝt ÿa thӭc các bài toán con. ĈLӅu ÿó chӭng tӓ rҵng có nhӳng bài toán con ÿѭӧc giҧi nhiӅu lҫn. Chҷng hҥn ÿӇ tính Comb(4,2) ta phҧi tính Comb(3,1) và Comb(3,2). ĈӇ tính Comb(3,1) ta phҧi tính Comb(2,0) và Comb(2,1). ĈӇ tính Comb(3,2) ta phҧi tính Comb(2,1) và Comb(2,2). Nhѭ vұy ÿӇ tính Comb(4,2) ta phҧi tính Comb(2,1) hai lҫn. Hình 3-2 sau minh hoҥ rõ ÿLӅu ÿó. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 41 Áp dөng kӻ thuұt quy hoҥch ÿӝng ÿӇ khҳc phөc tình trҥng trên, ta xây dӵng mӝt bҧng gӗm n+1 dòng (tӯ 0 ÿӃn n) và n+1 cӝt (tӯ 0 ÿӃn n) và ÿLӅn giá trӏ cho O(i,j) theo quy tҳc sau: (Quy tҳc tam giác Pascal): O(0,0) = 1; O(i,0) =1; O(i,i) = 1 vӟi 0 < i ( n; O(i,j) = O(i-1,j-1) + O(i-1,j) vӟi 0 < j < i £ n. Chҷng hҥn vӟi n = 4 ta có bҧng bên. O(n,k) chính là Comb(n,k) và ta có giҧi thuұt nhѭ sau: function Comb(n, k : Integer) : Integer var C: array[0..n, 0..n] of integer; i,j : integer; begin {1} C[0,0] := 1; {2} for i := 1 to n do begin {3} C[i,0] := 1; {4} C[i,i] := 1; {5} for j := 1 to i-1 do C[i,j] := C[i-1,j-1] + C[i-1,j]; end; {6} Comb := C[n,k]; end; Vòng lһp {5} thӵc hiӋn i-1 lҫn, mӛi lҫn O(1). Vòng lһp {2} có i chҥy tӯ 1 ÿӃn n, nên nӃu gӑi T(n) là thӡi gian thӵc hiӋn giҧi thuұt thì ta có: III.3- KӺ THUҰT "THAM ĂN" III.3.1- Bài toán tӕi ѭu tә hӧp III.3.2- Nӝi dung kӻ thuұt tham ăn III.3.3- Bài toán ÿѭӡng ÿi cӫa ngѭӡi giao hàng III.3.4- Bài toán cái ba lô Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 42 III.3.1- Bài toán tӕi ѭu tә hӧp Là mӝt dҥng cӫa bài toán tӕi ѭu, nó có dҥng tәng quát nhѭ sau: · Cho phiӃm hàm xác ÿӏnh trên mӝt tұp hӳu hҥn các phҫn tӱ D. Hàm f(X) ÿѭӧc gӑi là hàm mөc tiêu. · Mӛi phҫn tӱ X D có dҥng X= (x1, x2, .. xn) ÿѭӧc gӑi là mӝt phѭѫng án. · Cҫn tìm mӝt phѭѫng án X D sao cho hàm f(X) ÿҥt min (max). Phѭѫng án X nhѭ thӃÿѭӧc Jӑi là phѭѫng án tӕi ѭu. Ta có thӇ tìm thҩy phѭѫng án tӕi ѭu bҵng phѭѫng pháp “vét cҥn” nghƭa là xét tҩt cҧ các phѭѫng án trong tұp D (hӳu hҥn) ÿӇ xác ÿinh phѭѫng án tӕt nhҩt. Mһc dù tұp hӧp D là hӳu hҥn nhѭng ÿӇ tìm phѭѫng án tӕi ѭu cho mӝt bài toán kích thѭӟc n bҵng phѭѫng pháp “vét cҥn” ta có thӇ cҫn mӝt thӡi gian mNJ. Các phҫn tiӃp theo cӫa chѭѫng này sӁ trình bày mӝt sӕ kӻ thuұt giҧi bài toán tӕi ѭu tә hӧp mà thӡi gian có thӇ chҩp nhұn ÿѭӧc. III.3.2- Nӝi dung kӻ thuұt tham ăn Kӻ thuұt tham ăn thѭӡng ÿѭӧc vұn dөng ÿӇ giҧi bài toán tӕi ѭu tә hӧp bҵng cách xây dӵng mӝt phѭѫng án X. Phѭѫng án X ÿѭӧc xây dӵng bҵng cách lӵa chӑn tӯng thành phҫn xi cӫa X cho ÿӃn khi hoàn chӍnh (ÿӫ n thành phҫn). Vӟi mӛi xi , ta sӁ chӑn xi tӕi ѭu. Vӟi cách này thì có thӇӣ bѭӟc cuӕi cùng ta không còn gì ÿӇ chӑn mà phҧi chҩp nhұn mӝt giá trӏ cuӕi cùng còn lҥi. Áp dөng kӻ thuұt tham ăn sӁ cho mӝt giҧi thuұt thӡi gian ÿa thӭc, tuy nhiên nói chung chúng ta chӍÿҥt ÿѭӧc mӝt phѭѫng án tӕt chӭ không phҧi là tӕi ѭu. Có rҩt nhiӅu bài toán mà ta có thӇ giҧi bҵng kӻ thuұt này, sau ÿây là mӝt sӕ ví dө. III.3.3- Bài toán ÿѭӡng ÿi cӫa ngѭӡi giao hàng Chúng ta sӁ xét mӝt bài toán rҩt nәi tiӃng có tên là bài toán tìm ÿѭӡng ÿi cӫa ngѭӡi giao hàng (TSP - Traveling Salesman Problem): Có mӝt ngѭӡi giao hàng cҫn ÿi giao hàng tҥi n thành phӕ. Xuҩt phát tӯ mӝt thành phӕ nào ÿó, ÿi qua các thành phӕ khác ÿӇ giao hàng và trӣ vӅ thành phӕ ban ÿҫu. Mӛi thành phӕ chӍÿӃn mӝt lҫn, khoҧng cách tӯ mӝt thành phӕÿӃn các thành phӕ khác là xác ÿӏnh ÿѭӧc. Khoҧng cách giӳa hai thành phӕ có thӇ là khoҧng cách ÿӏa lý, có thӇ là cѭӟc phí di chuyӇn hoһc thӡi gian di chuyӇn. Ta gӑi chung là ÿӝ dài. Hãy tìm mӝt chu trình (mӝt ÿѭӡng ÿi khép kín thӓa mãn ÿLӅu kiӋn trên) sao cho tәng ÿӝ dài các cҥnh là nhӓ nhҩt. Hay còn nói là tìm mӝt phѭѫng án có giá nhӓ nhҩt. Bài toán này cNJng ÿѭӧc gӑi là bài toán ngѭӡi du lӏch. Vӟi phѭѫng pháp vét cҥn ta xét tҩt cҧ các chu trình, mӛi chu trình tính tәng ÿӝ dài các cҥnh Fӫa nó rӗi chӑn mӝt chu trình có tәng ÿӝ dài nhӓ nhҩt. Tuy nhiên chúng ta cҫn xét tҩt cҧ là chu trình. Thӵc vұy, do mӛi chu trình ÿӅu ÿi qua tҩt cҧ các ÿӍnh (thành phӕ) nên ta có thӇ cӕÿӏnh mӝt ÿӍnh. 7ӯÿӍnh này ta có n-1 cҥnh tӟi n-1 ÿӍnh khác, nên ta có n-1 cách chӑn cҥnh ÿҫu tiên cӫa chu trình. Sau khi ÿã chӑn ÿѭӧc cҥnh ÿҫu tiên, chúng ta còn n-2 cách chӑn cҥnh thӭ hai, do ÿó ta có (n-1)(n-2) cách Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 43 chӑn hai cҥnh. Cӭ lý luұn nhѭ vұy ta sӁ thҩy có (n-1)! cách chӑn mӝt chu trình. Tuy nhiên vӟi mӛi chu trình ta chӍ quan tâm ÿӃn tәng ÿӝ dài các cҥnh chӭ không quan tâm ÿӃn hѭӟïng ÿi theo chiӅu dѭѫng hay âm vì vұy có tҩt cҧ phѭѫng án. Ĉó là mӝt giҧi thuұt thӡi gian mNJ !!!. .ӻ thuұt tham ăn áp dөng vào ÿây là: 1. Tính ÿӝ dài cӫa tҩt cҧ các cҥnh (có tҩt cҧ Fҥnh). 2. Xét các cҥnh có ÿӝ dài tӯ nhӓÿӃn lӟn ÿӇÿѭa vào chu trình. 3. Mӝt cҥnh sӁÿѭӧc ÿѭa vào chu trình nӃu cҥnh ÿó thӓa mãn hai ÿLӅu kiӋn sau: · Không tҥo thành mӝt chu trình thiӃu (không ÿi qua ÿӫ n ÿӍnh) · Không tҥo thành mӝt ÿӍnh có cҩp • 3 (tӭc là không ÿѭӧc có nhiӅu hѫn hai cҥnh xuҩt phát Wӯ mӝt ÿӍnh, do yêu cҫu cӫa bài toán là mӛi thành phӕ chӍÿѭӧc ÿӃn mӝt lҫn: mӝt lҫn ÿӃn và mӝt lҫn ÿi) 4. Lһp lҥi bѭӟc 3 cho ÿӃn khi xây dӵng ÿѭӧc mӝt chu trình. Vӟi kӻ thuұt này ta chӍ cҫn n(n-1)/2 phép chӑn nên ta có mӝt giҧi thuұt cҫn O(n2) thӡi gian. Ví dө 3-1: Cho bài toán TSP vӟi 6 ÿӍnh ÿѭӧc cho bӣi các tӑa ÿӝ nhѭ sau: Do có 6 ÿӍnh nên có tҩt cҧ 15 cҥnh. Ĉó là các cҥnh: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df và ef. Ĉӝ dài các cҥnh ӣÿây là khoҧng cách Euclide. Trong 15 cҥnh này thì de = 3 là nhӓ nhҩt, nên de ÿѭӧc chӑn vào chu trình. KӃÿӃn là 3 cҥnh ab, bc và ef ÿӅu có ÿӝ dài là 5. Cҧ 3 cҥnh ÿӅu thӓa mãn hai ÿLӅu kiӋn nói trên, nên ÿӅu ÿѭӧc chӑn vào chu trình. Cҥnh có ÿӝ dài nhӓ kӃ tiӃp là ac = 7.08, nhѭng không thӇÿѭa cҥnh này vào chu trình vì nó sӁ tҥo ra chu trình thiӃu (a-b-c-a). Cҥnh df cNJng bӏ loҥi vì lý do tѭѫng tӵ. Cҥûnh be ÿѭӧc xem xét nhѭng rӗi cNJng bӏ loҥi do tҥo ra ÿӍnh b và ÿӍnh e có cҩp 3. Tѭѫng tӵ chúng ta cNJng loҥi bd. cd là cҥnh tiӃp theo ÿѭӧc xét và ÿѭӧc chӑn. Cuӕi cùng ta có chu trình a-b-c-d-e-f-a vӟi tәng ÿӝ dài là 50. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 44 Ĉây chӍ là mӝt phѭѫng án tӕt. Phѭѫng án tӕi ѭu là chu trình a-c-d-e-f-b-a vӟi tәng ÿӝ dài là 48.39. Giҧi thuұt sѫ bӝ nhѭ sau: procedure TSP; begin {E là tұp các cҥnh } {Sҳp xӃp các cҥnh trong E theo thӭ tӵ tăng cӫa ÿӝ dài } Chu_Trinh := F; Gia := 0.0; while E F do begin if cҥnh e có thӇ chӑn then begin Chu_Trinh := Chu_Trinh + e ; Gia := Gia + ÿӝ dài cӫa e; end; E := E-e; end ; end; Mӝt cách tiӃp cұn khác cӫa kӻ thuұt tham ăn vào bài toán này là: 1. Xuҩt phát tӯ mӝt ÿӍnh bҩt kǤ, chӑn mӝt cҥnh có ÿӝ dài nhӓ nhҩt trong tҩt cҧ các cҥnh ÿi ra tӯ ÿӍnh ÿó ÿӇÿӃn ÿӍnh kӃ tiӃp. 2. TӯÿӍnh kӃ tiӃp ta lҥi chӑn mӝt cҥnh có ÿӝ dài nhӓ nhҩt ÿi ra tӯÿӍnh này thoҧ mãn hai ÿLӅu kiӋn nói trên ÿӇÿi ÿӃn dӍnh kӃ tiӃp. 3. Lһp lҥi bѭӟc 2 cho ÿӃn khi ÿi tӟi ÿӍnh n thì quay trӣ vӅÿӍnh xuҩt phát. III.3.4- Bài toán cái ba lô Cho mӝt cái ba lô có thӇÿӵng mӝt trӑng lѭӧng W và n loҥi ÿӗ vұt, mӛi ÿӗ vұt i có mӝt trӑng lѭӧng gi và mӝt giá trӏ vi. Tҩt cҧ các loҥi ÿӗ vұt ÿӅu có sӕ lѭӧng không hҥn chӃ. Tìm Pӝt cách lӵa chӑn các ÿӗ vұt ÿӵng vào ba lô, chӑn các loҥi ÿӗ vұt nào, mӛi loҥi lҩy bao nhiêu sao cho Wәng trӑng lѭӧng không vѭӧt quá W và tәng giá trӏ là lӟn nhҩt. Theo yêu cҫu cӫa bài toán thì ta cҫn nhӳng ÿӗ vұt có giá trӏ cao mà trӑng lѭӧng lҥi nhӓÿӇ sao cho có thӇ mang ÿѭӧc nhiӅu “ÿӗ quý”, sӁ là hӧp lý khi ta quan tâm ÿӃn yӃu tӕ “ÿѫn giá” cӫa tӯng loҥi ÿӗ vұt tӭc là tӹ lӋ giá trӏ/trӑng lѭӧng. Ĉѫn giá càng cao thì ÿӗ càng quý. Tӯÿó ta có kӻ thuұt greedy ápUpload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 45 Gөng cho bài toán này là: 1. Tính ÿѫn giá cho các loҥi ÿӗ vұt. 2. Xét các loҥi ÿӗ vұt theo thӭ tӵÿѫn giá tӯ lӟn ÿӃn nhӓ. 3. Vӟi mӛi ÿӗ vұt ÿѭӧc xét sӁ lҩy mӝt sӕ lѭӧng tӕi ÿa mà trӑng lѭӧng còn lҥi cӫa ba lô cho phép. 4. Xác ÿӏnh trӑng luӧng còn lҥi cӫa ba lô và quay lҥi bѭӟc 3 cho ÿӃn khi không còn có thӇ chӑn ÿѭӧc ÿӗ vұt nào nӳa. Ví dө 3-2: Ta có mӝt ba lô có trӑng lѭӧng làì 37 và 4 loҥi ÿӗ vұt vӟi trӑng lѭӧng và giá trӏ Wѭѫng ӭng ÿѭӧc cho trong bҧng (hình 3-6) Tӯ bҧng ÿã cho ta tính ÿѫn giá cho các loҥi ÿӗ vұt và sҳp xӃp các loҥi ÿӗ vұt này theo thӭ tӵ ÿѫn giá giҧm dҫn ta có bҧng (hình 3-7). Theo ÿó thì thӭ tӵѭu tiên ÿӇ chӑn ÿӗ vұt là là B, A, D và cuӕi cùng là C. Vұt B ÿѭӧc xét ÿҫu tiên và ta chӑn tӕi ÿa 3 cái vì mӛi cái vì trӑng lѭӧng mӛi cái là 10 và ba lô có trӑng lѭӧng 37. Sau khi ÿã chӑn 3 vât loҥi B, trӑng lѭӧng còn lҥi trong ba lô là 37 - 3*10 = 7. Ta xét ÿӃn vұt A, vì A có trӑng lѭӧng 15 mà trӑng lѭӧng còn lҥi cӫa balô chӍ còn 7 nên không thӇ chӑn vұt A. Xét vұt D và ta thҩy có thӇ chӑn 1 vұt D, khi ÿó trӑng lѭӧng còn lҥi cӫa ba lô là 7-4 = 3. Cuӕi cùng ta chӑn ÿѭӧc mӝt vұt C. Nhѭ vұy chúng ta ÿã chӑn 3 cái loҥi B, mӝt cái loҥi D và 1 cái loҥi C. Tәng trӑng lѭѫng là 3*10 + 1*4 + 1*2 = 36 và tәng giá trӏ là 3*25+1*6+1*2 = 83. Chú ý có mӝt sӕ biӃn thӇ cӫa bài toán cái ba lô nhѭ sau: 1. Mӛi ÿӗ vұt i chӍ có mӝt sӕ lѭӧng si. Vӟi bài toán này khi lӵa chӑn vұt i ta không ÿѭӧc lҩy Pӝt sӕ lѭӧng vѭӧt quá si. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 46 2. Mӛi ÿӗ vұt chӍ có mӝt cái. Vӟi bài toán này thì vӟi mӛi ÿӗ vұt ta chӍ có thӇ chӑn hoһc không chӑn. III.4- KӺ THUҰT QUAY LUI III.4.1- Ĉӏnh trӏ cây biӇu thӭc sӕ hӑc III.4.2- Kӻ thuұt cҳt tӍa Alpha-Beta III.4.3- Kӻ thuұt nhánh cұn Kӻ thuұt quay lui (backtracking) nhѭ tên gӑi cӫa nó, là mӝt quá trình phân tích ÿi xuӕng. Tҥi Pӛi bѭӟc phân tích chúng ta chѭa giҧi quyӃt ÿѭӧc vҩn ÿӅ do còn thiӃu cӭ liӋu nên cӭ phҧi phân tích cho tӟi các ÿLӇm dӯng, nѫi chúng ta xác ÿӏnh ÿѭӧc lӡi giҧi cӫa chúng hoһc là xác ÿӏnh ÿѭӧc là không thӇ (hoһc không nên) tiӃp tөc theo hѭӟng này. Tӯ các ÿLӇm dӯng này chúng ta quay ngѭӧc trӣ lҥi theo con ÿѭӡng mà chúng ta ÿã ÿi qua ÿӇ giҧi quyӃt các vҩn ÿӅ còn tӗn ÿӑng và cuӕi cùng ta sӁ giҧi quyӃt ÿѭӧc vҩn ÿӅ ban ÿҫu. Ӣÿây chúng ta sӁ xét 3 kӻ thuұt quay lui: “vét cҥn” là kӻ thuұt phҧi ÿi tӟi tҩt cҧ các ÿLӇm dӯng Uӗi mӟi quay lui. “Cҳt tӍa Alpha-Beta” và “Nhánh-Cұn” là hai kӻ thuұt cho phép chúng ta không cҫn thiӃt phҧi ÿi tӟi tҩt cҧ các ÿLӇm dӯng, mà chӍ cҫn ÿi ÿӃn mӝt sӕÿLӇm nào ÿó và dӵa vào mӝt sӕ suy luұn ÿӇ có thӇ quay lui sӟm. Các kӻ thuұt này sӁÿѭӧc trình bày thông qua mӝt sӕ bài toán cө thӇ sau. III.4.1- Ĉӏnh trӏ cây biӇu thӭc sӕ hӑc Trong các ngôn ngӳ lұp trình ÿӅu có các biӇu thӭc sӕ hӑc, viӋc dӏch các biӇu thӭc này ÿòi hӓi phҧi ÿánh giá (ÿӏnh trӏ) chúng. ĈӇ làm ÿѭӧc ÿLӅu ÿó cҫn phҧi có mӝt biӇu diӉn trung gian cho biӇu thӭc. Mӝt trong các biӇu diӉn trung gian cho biӇu thӭc là cây biӇu thӭc. Cây biӇu thӭc sӕ hӑc là mӝt cây nhӏ phân, trong ÿó các nút lá biӇu diӉn cho các toán hҥng, các nút trong biӇu diӉn cho các toán tӱ. Ví dө 3-3: BiӇu thӭc 5 + 2 * 3 - 4 sӁÿѭӧc biӇu diӉn bӣi cây trong hình 3-8: Trӏ cӫa mӝt nút lá chính là trӏ cӫa toán hҥng mà nút ÿó biӇu diӉn. Trӏ cӫa mӝt nút trong có ÿѭӧc bҵng cách lҩy toán tӱ mà nút ÿó biӇu diӉn áp dөng vào các con cӫa nó. Trӏ cӫa nút gӕc chính là trӏ cӫa biӇu thӭc. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 47 Nhѭ vұy ÿӇÿӏnh trӏ cho nút gӕc, chúng ta phҧi ÿӏnh trӏ cho hai con cӫa nó, ÿӕi vӟi mӛi con ta xem nó có phҧi là nút lá hay không, nӃu không phҧi ta lҥi phҧi xét hai con cӫa nút ÿó. Quá trình cӭ tiӃp Wөc nhѭ vұy cho tӟi khi gһp các nút lá mà giá trӏ cӫa chúng ÿã ÿѭӧc biӃt, quay lui ÿӇÿӏnh trӏ cho các nút cha cӫa các nút lá và cӭ nhѭ thӃ mà ÿӏnh trӏ cho tә tiên cӫa chúng. Ĉó chính là kӻ thuұt quay lui vét Fҥn, vì chúng ta phҧi lҫn ÿӃn tҩt cҧ các nút lá mӟi ÿӏnh trӏÿѭӧc cho các nút trong và do thӃ mӟi ÿӏnh trӏ ÿѭӧc cho nút gӕc. Ví dө 3-4: Vӟi cây biӇu thӭc trong ví dө 3-3. ĈӇÿӏnh trӏ cho nút - chúng ta phҧi ÿӏnh trӏ cho nút + và nút 4. Nút 4 là nút lá nên giá trӏ cӫa nó là 4. ĈӇÿӏnh trӏ cho nút + ta phҧi ÿӏnh trӏ cho nút 5 và nút *. Nút 5 là nút lá nên giá trӏ cӫa nó là 5. ĈӇÿӏnh trӏ cho nút *, ta phҧi ÿӏnh trӏ cho nút 2 và nút 3. Cҧ hai nút này ÿӅu là lá nên giá trӏ cӫa chúng tѭѫng ӭng là 2 và 3. Quay lui lҥi nút *, lҩy toán tӱ * áp dөng cho hai con cӫa nó là 2 và 3 ta ÿѭӧc trӏ cӫa nút * là 6. Quay lui vӅ nút +, lҥi áp dөng toán tӱ + vào hai con cӫa nó là 5 và 6 ÿѭӧc trӏ cӫa nút + là 11. Cuӕi cùng quay vӅ nút -, áp dөng toán tӱ - vào hai con Fӫa nó là 11 và 4 ta ÿѭӧc trӏ cӫa nút - (nút gӕc) là 7. Ĉó chính là trӏ cӫa biӇu thӭc. Trong hình 3-9, mNJi tên nét ÿӭt minh hӑa quá trình ÿi tìm nút lá và mNJi tên nét liӅn minh hӑa quá trình quay lui ÿӇÿӏnh trӏ cho các nút, các sӕ bên phҧi Pӛi nút là trӏ cӫa nút ÿó. Giҧi thuұt sѫ bӝÿӇÿӏnh trӏ mӝt nút bҩt kǤ nhѭ sau: function Eval(n : node): real; begin if n là lá then return (trӏ cӫa toán hҥng trong n) else return (Toán tӱ trong n (Eval (Con trái cӫa n), Eval (Con phҧi cӫa n)) ); end; Muӕn ÿӏnh trӏ cho cây biӇu thӭc T, ta gӑi Eval(ROOT(T)). III.4.2- Kӻ thuұt cҳt tӍa Alpha-Beta Cây trò chѫi Xét mӝt trò chѫi trong ÿó hai ngѭӡi thay phiên nhau ÿi nѭӟc cӫa mình nhѭ Fӡ vua, cӡ tѭӟng, carô,... Trò chѫi có mӝt trҥng thái bҳt ÿҫu và mӛi nѭӟc ÿi sӁ biӃn ÿәi trҥng thái hiӋn hành thành mӝt trҥng thái mӟi. Trò chѫi sӁ kӃt thúc theo mӝt quy ÿӏnh nào ÿó, theo ÿó thì cuӝc chѫi sӁUpload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 48 Gүn ÿӃn mӝt trҥng thái phҧn ánh có mӝt ngѭӡi thҳng cuӝc hoһc mӝt trҥng thái mà cҧ hai ÿҩu thӫ không thӇ phát triӇn ÿѭӧc nѭӟc ÿi cӫa mình, ta gӑi nó là trҥng thái hòa cӡ. Ta tìm cách phân tích xem tӯ mӝt trҥng thái nào ÿó sӁ dүn ÿӃn ÿҩu thӫ nào sӁ thҳng vӟi ÿLӅu kiӋn cҧ hai ÿҩu thӫÿӅu có trình ÿӝ nhѭ nhau. Mӝt trò chѫi nhѭ vұy có thӇÿѭӧc biӇu diӉn bӣi mӝt cây, gӑi là cây trò chѫi. Mӛi mӝt nút cӫa cây biӇu diӉn cho mӝt trҥng thái. Nút gӕc biӇu diӉn cho trҥng thái bҳt ÿҫu cӫa cuӝc chѫi. Mӛi nút lá biӇu diӉn cho mӝt trҥng thái kӃt thúc cӫa trò chѫi (trҥng thái thҳng thua hoһc hòa). NӃu trҥng thái x ÿѭӧc biӇu diӉn bӣi nút n thì các con cӫa n biӇu diӉn cho tҩt cҧ các trҥng thái kӃt quҧ cӫa các nѭӟc ÿi có thӇ xuҩt phát tӯ trҥng thái x. Ví dө 3-5: Xét trò chѫi carô có 9 ô. Hai ngѭӡi thay phiên nhau ÿi X hoһc O. Ngѭӡi nào ÿi ÿѭӧc 3 ô thҷng hàng (ngang, dӑc, xiên) thì thҳng cuӝc. NӃu ÿã hӃt ô ÿi mà chѭa phân thҳng bҥi thì hai ÿҩu thӫ hòa nhau. Mӝt phҫn cӫa trò chѫi này ÿѭӧc biӇu diӉn bӣi cây sau: Trong cây trò chѫi trên, các nút lá ÿѭӧc tô nӅn và viӅn khung ÿôi ÿӇ dӉ phân biӋt vӟi các nút khác. Ta có thӇ gán cho mӛi nút lá mӝt giá trӏÿӇ phҧn ánh trҥng thái thҳng thua hay hòa cӫa các ÿҩu thӫ. Chҷng hҥn ta gán cho nút lá các giá trӏ nhѭ sau: · 1 nӃu tҥi ÿó ngѭӡi ÿi X ÿã thҳng, · -1 nӃu tҥi ÿó ngѭӡi ÿi X ÿã thua và Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 49 · 0 nӃu hai ÿҩu thӫÿã hòa nhau. Nhѭ vұy tӯ mӝt trҥng thái bҩt kǤ, ÿӃn lѭӧt mình, ngѭӡi ÿi X sӁ chӑn cho mình mӝt nѭӟc ÿi sao cho dүn ÿӃn trҥng thái có giá trӏ lӟn nhҩt (trong trѭӡng hӧp này là 1). Ta nói X chӑn nѭӟc ÿi MAX, nút mà tӯÿó X chӑn nѭӟc ÿi cӫa mình ÿѭӧc gӑi là nút MAX. Ngѭӡi ÿi O ÿӃn lѭӧt mình sӁ chӑn mӝt nѭӟc ÿi sao cho dүn ÿӃn trҥng thái có giá trӏ nhӓ nhҩt (trong trѭӡng hӧp này là -1, khi ÿó X sӁ thua và do ÿó O sӁ thҳng). Ta nói O chӑn nѭӟc ÿi MIN, nút mà tӯÿó O chӑn nѭӟc ÿi cӫa mình ÿѭӧc gӑi là nút MIN. Do hai ÿҩu thӫ luân phiên nhau ÿi nѭӟc cӫa mình nên các mӭc trên cây trò chѫi cNJng luân phiên nhau là MAX và MIN. Cây trò chѫi vì thӃ còn có tên là cây MIN-MAX. Ta có thӇÿѭa ra mӝt quy tҳc ÿӏnh trӏ cho các nút trên cây ÿӇ phҧn ánh tình trҥng thҳng thua hay hòa và khҧ năng thҳng cuӝc cӫa hai ÿҩu thӫ. NӃu mӝt nút là nút lá thì trӏ cӫa nó là giá trӏÿã ÿѭӧc gán cho nút ÿó. Ngѭӧc lҥi, nӃu nút là nút MAX thì trӏ cӫa nó bҵng giá trӏ lӟn nhҩt cӫa tҩt cҧ các trӏ cӫa các con cӫa nó. NӃu nút là nút MIN thì trӏ Fӫa nó là giá trӏ nhӓ nhҩt cӫa tҩt cҧ các trӏ cӫa các con cӫa nó. Quy tҳc ÿӏnh trӏ này cNJng gҫn giӕng vӟi quy tҳc ÿӏnh trӏ cho cây biӇu thӭc sӕ hӑc, ÿLӇm khác biӋt ӣÿây là các toán tӱ là các hàm lҩy max hoһc min và mӛi nút có thӇ có nhiӅu con. Do vұy ta có thӇ dùng kӻ thuұt quay lui ÿӇÿӏnh trӏ cho các nút cӫa cây trò chѫi. ĈӇ cài ÿһt ta có mӝt sӕ giҧ thiӃt sau: · Ta có mӝt hàm Payoff nhұn vào mӝt nút lá và cho ta giá trӏ cӫa nút lá ÿó. · Các hҵng ’ và -’ tѭѫng ӭng là các trӏ Payoff lӟn nhҩt và nhӓ nhҩt. · Khai báo kiӇu ModeType = (MIN, MAX) ÿӇ xác ÿӏnh ÿӏnh trӏ cho nút là MIN hay MAX. · Mӝt kiӇu NodeType ÿѭӧc khai báo mӝt cách thích hӧp ÿӇ biӇu diӉn cho mӝt nút trên cây phҧn ánh mӝt trҥng thái cӫa cuӝc chѫi. · Ta có mӝt hàm is_leaf ÿӇ xác ÿӏnh xem mӝt nút có phҧi là nút lá hay không? · Hàm max và min tѭѫng ӭng lҩy giá trӏ lӟn nhҩt và giá trӏ nhӓ nhҩt cӫa hai giá trӏ. Giҧi thuұt vét cҥn ÿӏnh trӏ cây trò chѫi Hàm Search nhұn vào mӝt nút n và kiӇu mode cӫa nút ÿó (MIN hay MAX) trҧ vӅ giá trӏ cӫa nút. NӃu nút n là nút lá thì trҧ vӅ giá trӏÿã ÿѭӧc gán cho nút lá. Ngѭӧc lҥi ta cho n mӝt giá trӏ tҥm value là -’ hoһc ’ tùy thuӝc n là nút MAX hay MIN và xét con cӫa n. Sau khi mӝt con cӫa n có giá trӏ V thì ÿһt lҥi value = max(value,V) nӃu n là nút MAX và value = min(value,V) nӃu n là nút MIN. Khi Wҩt cҧ các con cӫa n ÿã ÿѭӧc xét thì giá trӏ tҥm value cӫa n trӣ thành giá trӏ cӫa nó. function Search(n : NodeType; mode: ModeType): real; var C : NodeType ; { C là mӝt nút con cӫa nút n} Value : real; {Lúc ÿҫu ta cho value mӝt giá trӏ tҥm, sau khi ÿã xét hӃt tҩt cҧ các con cӫa nút n thì value là giáUpload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 50 trӏ cӫa nút n } begin if is_leaf(n) then return ( Payoff(n) ) else begin {Khӣi tҥo giá trӏ tҥm cho n } if mode = MAX then value := -’ else value := ’; {Xét tҩt cҧ các con cӫa n, mӛi lҫn xác ÿӏnh ÿѭӧc giá trӏ cӫa mӝt nút con, ta phҧi ÿһt lҥi giá trӏ Wҥm value. Khi ÿã xét hӃt tҩt cҧ các con thì value là giá trӏ cӫa n} for vӟi mӛi con C cӫa n do if mode = MAX then Value := max(Value, Search(C, MIN) ) else Value := min(Value, Search(C, MAX) ); return (value); end; end; .ӻ thuұt cҳt tӍa Alpha-Beta (Alpha-Beta Pruning) Trong giҧi thuұt vét cҥn ӣ trên, ta thҩy ÿӇÿӏnh trӏ cho mӝt nút nào ÿó, ta phҧi ÿӏnh trӏ cho tҩt cҧ các nút con cháu cӫa nó, và muӕn ÿӏnh trӏ cho nút gӕc ta phҧi ÿӏnh trӏ cho tҩt cҧ các nút trên cây. Sӕ Oѭӧng các nút trên cây trò chѫi tuy hӳu hҥn nhѭng không phҧi là ít. Chҷng hҥn trong cây trò chѫi ca rô nói trên, nӃu ta có bàn cӡ bao gӗm n ô thì có thӇ có tӟi n! nút trên cây (trong trѭӡng hӧp trên là 9!). Ĉӕi vӟi các loҥi cӡ khác nhѭ cӡ vua chҷng hҥn, thì sӕ lѭӧng các nút còn lӟn hѫn nhiӅu. Ta gӑi là mӝt Vӵ bùng nә tә hӧp các nút. Chúng ta cӕ gҳng tìm mӝt cách sao cho khi ÿӏnh trӏ mӝt nút thì không nhҩt thiӃt phҧi ÿӏnh trӏ cho tҩt cҧ các nút con cháu cӫa nó. Trѭӟc hӃt ta có nhұn xét nhѭ sau: NӃu P là mӝt nút MAX và ta ÿang xét mӝt nút con Q cӫa nó (dƭ nhiên Q là nút MIN). Giҧ sӱ Vp là mӝt giá trӏ tҥm cӫa P, Vq là mӝt giá trӏ tҥm cӫa Q và nӃu ta có Vp • Vq thì ta không cҫn xét các con chѭa xét cӫa Q nӳa. Vì nӃu có xét thì giá trӏ cӫa Q cNJng sӁ nhӓ hѫn hoһc bҵng Vq và do ÿó không ҧnh hѭӣng gì ÿӃn Vp. Tѭѫng tӵ nӃu P là nút MIN (tҩt nhiên Q là nút MAX) và Vp ” Vq thì ta cNJng không cҫn xét ÿӃn các con chѭa xét cӫa Q nӳa. ViӋc không xét tiӃp các con chѭa ÿѭӧc xét cӫa nút Q Jӑi là viӋc cҳt tӍa Alpha-Beta các con cӫa nút Q. Trên cѫ sӣ nhұn xét ÿó, ta nêu ra quy tҳc ÿӏnh trӏ cho mӝt nút không phҧi là nút lá trên cây nhѭ sau: 1. Khӣi ÿҫu nút MAX có giá trӏ tҥm là -’ và nút MIN có giá trӏ tҥm là ’. 2. NӃu tҩt cҧ các nút con cӫa mӝt nút ÿã ÿѭӧc xét hoһc bӏ cҳt tӍa thì giá trӏ tҥm cӫa nút ÿó trӣ thành giá trӏ cӫa nó. 3. NӃu mӝt nút MAX n có giá trӏ tҥm là V1 và mӝt nút con cӫa nó có giá trӏ là V2 thì ÿһt giá trӏ Wҥm mӟi cӫa n là max (V1,V2). NӃu n là nút MIN thì ÿһt giá trӏ tҥm mӟi cӫa n là min (V1,V2). 4. Vұn dөng quy tҳc cҳt tӍa Alpha-Beta nói trên ÿӇ hҥn chӃ sӕ lѭӧng nút phҧi xét.Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 51 function cat_tia(Q: NodeType; mode: ModeType; Vp: real): real; var C : NodeType ; { C là mӝt nút con cӫa nút Q} Vq : real; {Vq là giá trӏ tҥm cӫa Q, sau khi tҩt cҧ các con cӫa nút Q ÿã xét hoһc bӏ cҳt tӍa thì Vq là giá trӏ Fӫa nút Q} begin if is_leaf(Q) then return ( Payoff(Q) ) else begin { Khӣi tҥo giá trӏ tҥm cho Q } if mode = MAX then Vq := -’ else Vq := ’; {Xét các con cӫa Q, mӛi lҫn xác ÿӏnh ÿѭӧc giá trӏ cӫa mӝt nút con cӫa Q, ta phҧi ÿһt lҥi giá trӏ Wҥm Vq và so sánh vӟi Vp ÿӇ có thӇ cҳt tӍa hay không} Xét C là con trái nhҩt cӫa Q; while C là con cӫa Q DO if mode = MAX then begin Vq:= max(Vq, Cat_tia(C, MIN, Vq)); if Vp ” Vq then return(Vq); end else begin Vq := min(Vq, Cat_tia(C, MAX, Vq)); if Vp • Vq then return(Vq); end; return (Vq); end; end; Ví dө 3-6: Vұn dөng quy tҳc trên ÿӇÿӏnh trӏ cho nút A trong cây trò chѫi trong ví dө 3-5. A là nút MAX, lúc ÿҫu nó có giá trӏ tҥm là -’, xét B là con cӫa A, B là nút lá nên giá trӏ cӫa nó là giá trӏÿã ÿѭӧc gán 1, giá trӏ tҥm cӫa A bây giӡ là max (-’,1) = 1. Xét con C cӫa A, C là nút MIN, giá trӏ tҥm lúc ÿҫu cӫa C là ’. Xét con E cӫa C, E là nút MAX, giá trӏ tҥm cӫa E là -’. Xét con I cӫa E, I là nút lá nên giá trӏ cӫa nó là 0. Quay lui lҥi E, giá trӏ tҥm cӫa E bây giӡ là max (-’,0) = 0. Vì E chӍ có Pӝt con là I ÿã xét nên giá trӏ tҥm 0 trӣ thành giá trӏ cӫa E. Quay lui lҥi C, giá trӏ tҥm mӟi cӫa C là min ’,0) = 0. A là nút MAX có giá trӏ tҥm là 1, C là con cӫa A, có giá trӏ tҥm là 0, 1>0 nên ta không cҫn xét con F cӫa C nӳa. Nút C có hai con là E và F, trong ÿó E ÿã ÿѭӧc xét, F ÿã bӏ cҳt, vұy giá trӏ tҥm 0 Fӫa C trӣ thành giá trӏ cӫa nó. Sau khi có giá trӏ cӫa C, ta phҧi ÿһt lҥi giá trӏ tҥm cӫa A, nhѭng giá trӏ Wҥm này không thay ÿәi vì max (1,0) = 1. TiӃp tөc xét nút D, D là nút MIN nên giá trӏ tҥm là ’, xét nút con G cӫa D, G là nút MAX nên giá trӏ tҥm cӫa nó là -’, xét nút con J cӫa G. Vì J là nút lá nên có giá trӏ 0. Quay lui lҥi G, giá trӏ tҥm cӫa G bây giӡ là max (-’,0) = 0 và giá trӏ tҥm này trӣ thành giá trӏ cӫa G vì G chӍ có mӝt con J ÿã xét. Quay lui vӅ D, giá trӏ tҥm cӫa D bây giӡ là min (’,0) = 0. Giá trӏ tҥm này cӫa D nhӓ hѫn giá trӏ tҥm cӫa nút A MAX là cha cӫa nó nên ta cҳt tӍa con H chѭa ÿѭӧc xét cӫa D và lúc này D có giá trӏ là 0. Quay lui vӅ A, giá trӏ tҥm cӫa nó vүn không thay ÿәi, nhѭng lúc này cҧ 3 con cӫa A ÿӅu ÿã ÿѭӧc xét nên giá trӏ tҥm 1 trӣ thành giá trӏ cӫa A. KӃt quҧÿѭӧc minh hӑa trong hình sau: Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 52 III.4.3-Kӻ thuұt nhánh cұn Vӟi các bài toán tìm phѭѫng án tӕi ѭu, nӃu chúng ta xét hӃt tҩt cҧ các phѭѫng án thì mҩt rҩt nhiӅu thӡi gian, nhѭng nӃu sӱ dөng phѭѫng pháp tham ăn thì phѭѫng án tìm ÿѭӧc chѭa hҷn ÿã là phѭѫng án tӕi ѭu. Nhánh cұn là kӻ thuұt xây dӵng cây tìm kiӃm phѭѫng án tӕi ѭu, nhѭng không xây Gӵng toàn bӝ cây mà sӱ dөng giá trӏ cұn ÿӇ hҥn chӃ bӟt các nhánh. Cây tìm kiӃm phѭѫng án có nút gӕc biӇu diӉn cho tұp tҩt cҧ các phѭѫng án có thӇ có, mӛi nút lá biӇu diӉn cho mӝt phѭѫng án nào ÿó. Nút n có các nút con tѭѫng ӭng vӟi các khҧ năng có thӇ lӵa chӑn tұp phѭѫng án xuҩt phát tӯ n. Kӻ thuұt này gӑi là phân nhánh. Vӟi mӛi nút trên cây ta sӁ xác ÿӏnh mӝt giá trӏ cұn. Giá trӏ cұn là mӝt giá trӏ gҫn vӟi giá cӫa các phѭѫng án. Vӟi bài toán tìm min ta sӁ xác ÿӏnh Fұn dѭӟi còn vӟi bài toán tìm max ta sӁ xác ÿӏnh Fұn trên. Cұn dѭӟi là giá trӏ nhӓ hѫn hoһc bҵng giá cӫa phѭѫng án, ngѭӧc lҥi cұn trên là giá trӏ lӟn hѫn hoһc bҵng giá cӫa phѭѫng án. ĈӇ dӉ hình dung ta sӁ xét hai bài toán quen thuӝc là bài toán TSP và bài toán cái ba lô. Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 53 Bài toán ÿѭӡng ÿi cӫa ngѭӡi giao hàng Phân nhánh Cây tìm kiӃm phѭѫng án là cây nhӏ phân trong ÿó: · Nút gӕc là nút biӇu diӉn cho cҩu hình bao gӗm tҩt cҧ các phѭѫng án. · Mӛi nút sӁ có hai con, con trái biӇu diӉn cho cҩu hình bao gӗm tҩt cҧ các phѭѫng án chӭa Pӝt cҥnh nào ÿó, con phҧi biӇu diӉn cho cҩu hình bao gӗm tҩt cҧ các phѭѫng án không chӭa cҥnh ÿó (các cҥnh ÿӇ xét phân nhánh ÿѭӧc thành lұp tuân theo mӝt thӭ tӵ nào ÿó, chҷng hҥn thӭ tӵ tӯÿLӇn). · Mӛi nút sӁ kӃ thӯa các thuӝc tính cӫa tә tiên cӫa nó và có thêm mӝt thuӝc tính mӟi (chӭa hay không chӭa mӝt cҥnh nào ÿó). · Nút lá biӇu diӉn cho mӝt cҩu hình chӍ bao gӗm mӝt phѭѫng án. · ĈӇ quá trình phân nhánh mau chóng tӟi nút lá, tҥi mӛi nút ta cҫn có mӝt quyӃt ÿӏnh bә sung dӵa trên nguyên tҳc là mӑi ÿӍnh trong chu trình ÿӅu có cҩp 2 và không tҥo ra mӝt chu trình thiӃu. Ví dө 3-7: Xét bài toán TSP có 5 ÿӍnh vӟi ÿӝ dài các cҥnh ÿѭӧc cho trong hình 3-12. Các cҥnh theo thӭ tӵ tӯÿLӇn ÿӇ xét là: ab, ac, ad, ae, bc, bd, be, cd, ce và de. Nút gӕc A cӫa cây bao gӗm tҩt cҧ các phѭѫng án. Hai con cӫa A là B và C, trong ÿó B bao gӗm tҩtcҧ các phѭѫng án chӭa cҥnh ab, C bao gӗm tҩt Fҧ các phѭѫng án không chӭa ab. Hai con cӫa B là D và E. Nút D bao gӗm tҩt cҧ các phѭѫng án chӭa ac. Vì các phѭѫng án này Yӯa chӭa ab (kӃ thӯa cӫa B) vӯa chӭa ac nên ÿӍnh a ÿã ÿӫ cҩp hai nên D không thӇ chӭa ad và ae. Nút E bao gӗm tҩt cҧ các phѭѫng án không chӭa ac.. Ta ÿѭӧc cây (chѭa ÿҫy ÿӫ ) trong hình 3-13 Upload by Kenhdaihoc.com . Collected by The_Wall (11/10/2005) Giáo trình môn Phân tích Giɠi Thuɪt – ĈɝI +͌C CɣN THɆ ........................................................................Trang 54 Trong ÿó ký hiӋu có nghƭa là không chӭa cҥnh ab. Tính cұn dѭӟi Ĉây là bài toán tìm min nên ta sӱ dөng Fұn dѭӟi. Cұn dѭӟi tҥi mӛi nút là mӝt sӕ nhӓ hѫn hoһc Eҵng giá cӫa tҩt cҧ các phѭѫng án ÿѭӧc biӇu diӉn bӣi nút ÿó. Giá cӫa mӝt phѭѫng án ӣÿây là tәng ÿӝ dài cӫa mӝt chu trình. ĈӇ tính cұn dѭӟi cӫa nút gӕc, mӛi ÿӍnh ta chӑn hai cҥnh có ÿӝ dài nhӓ nhҩt. Cұn dѭӟi cӫa nút Jӕc bҵng tәng ÿӝ dài tҩt cҧ các cҥnh ÿѭӧc chӑn chia cho 2. Ví dө 3-8: Vӟi sӕ liӋu cho trong ví dө 3-7 nói trên, ta tính