Phân tích thiết kế thuật toán (Phần 2)

Nội dung text: Phân tích thiết kế thuật toán (Phần 2)

1. Phân tích thiết kế thuật toán BÀI 4 : PHƯƠNG PHÁP CHIA ĐỂ TRỊ Mã bài : ITPRG3_12.4 Giới thiệu Mặc dù không tồn tại một phương pháp vạn năng nào có thể giúp chúng ta thiết kế được thuật toán giải quyết mọi vấn đề, nhưng các nhà nghiên cứu đã tìm ra một số phương pháp thiết kế cơ bản, các phưong pháp này còn được gọi là các chiến lược thiết kế thuật toán. Mỗi phương pháp này có thể áp dụng để giải quyết một phạm vi khá rộng các bài toán. Trong tài liệu này chúng tôi sẽ trình bày các phương pháp thiết kế thuật toán như : chia để trị (divide and conquer), phương pháp tham lam (greeding method), quay lui (backtracking), quy hoạch động (dynamic programming), nhánh cận (branch and bound). Trong mỗi chiến lược, chúng tôi sẽ trình bày phương pháp chung, sau đó sẽ đưa ra một số ví dụ minh họa. Cần lưu ý rằng, các phương pháp thiết kế thuật toán mà chúng ta xem xét chỉ là các chiến lược có tính định hướng sự tìm tòi thuật toán. Trong bài này chúng ta sẽ xét một phương pháp thường được sử dụng đó là phương pháp chia để trị. Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng: Nắm bắt được ý tưởng của phương pháp chia để trị. Sử dụng phương pháp chia để trị để giải quyết các bài toán tìm kiếm, chọn các phân từ, sắp xếp, nhân ma trận. Áp dụng phương pháp chia để trị để giải quyết một số bài toán trong thực tế. Thấy được lợi thế của phương pháp chia để trị trong việc xây dựng một số thuật toán. .13. Phương pháp tổng quát Ý tưởng chính của phương pháp này là phân bài toán cần giải thành các bài toán con. Các bài toán con lại được tiếp tục phân thành các bài toán con nhỏ hơn, cứ thế tiếp tục cho tới khi chúng ta nhận được các bài toán con hoặc là đã có thuật giải, hoặc là có thể dễ dàng đưa ra thuật giải. Sau đó ta tìm cách kết hợp các nghiệm của các bài toán con để nhận được nghiệm của bài toán con lớn hơn, để cuối cùng nhận được nghiệm của bài toán cần giải. Thông thường các bài toán 110
2. Phân tích thiết kế thuật toán con nhận được trong quá trình phân chia là cùng dạng với bài toán ban đầu, chỉ có cỡ của chúng là nhỏ hơn. Trong các trường hợp như thế, thuật toán tìm ra được có thể biểu diễn một cách tự nhiên bởi thủ tục đệ quy. Sau đây là lược đồ phương pháp chia để trị. procedure DivideConquer(A,x); Tìm nghiệm x của bài toán A begin if A đủ nhỏ then solve(A) else begin Phân A thành các bài toán A1, A2, Am; for i:=1 to m do DivideConquer (A1, x1); Kết hợp các nghiệm x1(i=1, 2, ,m)của bài toán con A1 để nhận được nghiệm x của bài toán A end; end; Trong thủ tục trên, Solve là thuật giải bài toán A trong trường hợp A có cỡ đủ nhỏ. Thuật toán tìm kiếm nhị phân mà chúng ta đã biết là thuật toán được thiết kế dựa trên chiến lược chia để trị. Cho mảng A1 n được sắp xếp theo thứ tự tăng dần, A1 2 An. Với x cho trước, ta cần xác định xem x có chứa trong mảng A1 n hay không, tức là có hay không chỉ số 1 i n, sao cho Ai = x. Phương pháp chia để trị gợi ý ta chia mảng A1 n thành 3 mảng con A1 k-1 , mảng con gồm một thành phần duy nhất Ak và mảng con Ak+1 n, (k là chỉ số nằm giữa 1 và n). Với mảng con chỉ gồm một thành phần ta biết ngay được nó có chứa x hay không. Nếu x = Ak  thì mảng A chứa x và i = k. Nếu x Ak ta chỉ cần tìm kiếm trên mảng con Ak + 1 n. Để tìm kiếm x trên mảng con A1 k - 1 hoặc Ak +1 n ta lại áp dụng cách phân chia như đã làm với mảng A1 n. Thuật toán sắp xếp nhanh (QuickSort) cũng được thiết kế bởi kỹ thuật chia để trị. Sau đây chúng ta sẽ đưa ra một số ví dụ minh họa cho kỹ thuật chia để trị. .14. Tìm max và min Cho mảng A1 n, chúng ta cần tìm thành phần nhỏ nhất và lớn nhất của mảng này. Đây là bài toán rất đơn giản có thể giải bằng các thuật toán khác nhau, trong đó có thuật giải bằng kỹ thuật chia để trị. 111
3. Phân tích thiết kế thuật toán Ý tưởng của thuật toán là đầu tiên ta lấy max, min là thành phần đầu A1] của mảng. Sau đó so sánh max, min với các thành phần A[i] với 2 i n, và cập nhật max, min một cách thích ứng. Thuật toán được mô tả bởi thủ tục sau : Procedure maxmin(A[i n], max, min); Begin max:=a[i]; min:=A[1]; for i:=2 to n do if max A[i] then min := A[i]; End; Thời gian thực hiện thuật toán này được xác định bởi số phép toán so sánh. Từ vòng lặp for, ta thấy số phép toán so sánh cần thực hiện trong trường hợp xấu nhất (trường hợp mảng A[1 n] được sắp theo thứ tự giảm dần) là 2(n-1). Áp dụng kỹ thuật chia để trị, ta chia mảng A[1 n] thành hai mảng con A[1 k] và A[k+1 n] (k=n/2). Nếu tìm được max và min trên các mảng con A[1 k] và A[k+1 n], ta sẽ dễ dàng xác định được max, min trên toàn mảng A[1 n]. Để tìm max, min trên mảng con A[1 k] và A[k+1 n] ta lại tiếp tục chia đôi chúng. Quá trình sẽ dừng lại khi ta nhận được các mảng con chỉ có một hoặc hai phần tử. Trong các trường hợp đơn giản này max, min được xác định dễ dàng. Từ phương pháp đã trình bày trên, ta có thể đưa ra thủ tục đệ qui MaxMin(i, j, fmax, fmin). Thủ tục này cần tìm max và min trên mảng A[i n], ta chỉ cần gọi thủ tục này với i=1, j=n. Procedure MaxMin(i, j, fmax, fmin); {fmax, fmin ghi lại phần tử lớn nhất, nhỏ nhất của mảng A[i j]} Begin if i=j then begin fmax := A[i]; fmin := A[i]; end else if j=i+1 then if A[i] < A[j] then begin fmax := A[j]; fmin := A[i]; end else begin fmax := A[i]; 112
4. Phân tích thiết kế thuật toán fmin := A[j]; end else begin mid := i + j div 2; MaxMin(i, mid, gmax, gmin); MaxMin(mid+1, j hmax, hmin); if gmax 2 Giả sử n = 2, với k là số nguyên dương nào đó. Bằng phương pháp thế, ta tính được T(n) như sau: T(n) = T(2k) = 2T(22k-1) + 2 =22T(2k-2)+22+2 =23T(2k-3)+23+22+2 =2k-1T(2) + =2k-1+2k-2 =n/2+n-2 =3n/2-2 Như vậy với n =2k , thuật toán MaxMin cần 3n/2 – 2 phép so sánh, so với thuật toán trước, nó tiết kiệm được khoảng 25% phép so sánh. Tuy nhiên MaxMin là thuật toán đệ quy, nó tiêu tốn nhiều bộ nhớ hơn thuật toán trước. 113
5. Phân tích thiết kế thuật toán .15. Trao đổi hai phần của một mảng Giả sử T [1 n] là một mảng. Chúng ta muốn trao đổi phần đầu (k phần tử đầu tiên) của mảng với phần phụ còn lại (n-k phần tử còn lại), nhưng không sử dụng mảng phụ. Chẳng hạn, T là mảng a b c d e f g h và k = 3. Sau khi trao đổi ta cần nhận được mảng d e f g h a b c Sử dụng kỹ thuật chia để trị, ta phân bài toán trên thành hai bài toán con như sau: Giả sử k n- k, đầu tiên ta trao đổi k phần tử của phần đầu với k phần tử cuối của phần còn laị. Sau đó trong mảng T[1 n – k], ta chỉ cần trao đổi k phần tử đầu với phần còn lại. Chẳng hạn với mảng T ở trên và k = 3, quá trình diễn ra như sau: a b c d e f g h f g h d e a b c d e h f g a b c d e g f h a b c d e f g h a b c Còn nếu k > n-k, thì ta trao đổi n- k phần tử đầu tiên với n-k phần tử của phần sau. Sau đó trong mảng T[n-k+1 n], ta trao đổi n-k phần tử của phần đầu. Như vậy, ta phân bài toán trao đổi hai phần của mảng thành hai bài toán con. Bài toán con thứ nhất là trao đổi hai mảng con có độ dài bằng nhau. Bài toán con thứ hai cùng dạng với bài toán đã cho, nhưng cỡ của mảng đã nhỏ đi. Bài toán con thứ nhất có thể giải được dễ dàng bằng cách trao đổi từng cặp phần tử tương ứng. Thủ tục sau đây sẽ thực hiện trao đổi hai mảng con có độ dài m bắt đầu từ i và j tương ứng. 114
6. Phân tích thiết kế thuật toán procedure Interchange(i,j,m); begin for p:=0 to m-1 do Swap (T[i + p], T[j + p]) end; Trong thủ tục trên, Swap (x,y) là thủ tục trao đổi giá trị của hai biến x và y. Bài toán con tứ hai cùng dạng với bài toán ban đầu với cỡ của mảng nhỏ đi. Do đó, ta dễ dàng đưa ra thuật toán đệ quy để trao đổi hai phần tử của một mảng. Tuy nhiên, quá trình gọi đệ quy sẽ dừng lại khi ta đạt tới việc trao đổi hai phần có độ dài bằng nhau của một mảng. Do đó, ta có thể đưa ra thuật toán không đệ quy sau đây. procedure Transpose(k); {Trao đổi k p.tử đầu của mảng A[1 n] với n-k p.tử còn lại} begin i:=1; j:=n; while k>=i do if k<(i=j) div 2 then begin interchange(i,i+j-k,k-j+1); j:=i+j-k-1; end else begin Interchange(i,k+1,j-k); i:=i+j-k; end; end; 115
7. Phân tích thiết kế thuật toán BÀI TẬP Dùng kỹ thuật chia để trị để trình bày các thuật toán để : Bài 1 : Tìm kiếm nhị phân trên một dãy có n chữ số : a1, a2, , an. Bài 2 : Sắp xếp theo phương pháp trộn (mergesort). Bài 3 : Sắp xếp theo phương pháp sắp xếp nhanh (quicksort). Bài 4 : Nhân ma trận theo phương pháp Strassen. Bài 5 : a. Vẽ cây tìm kiếm nhị phân được tạo ra từ dãy các số nguyên : 51, 31, 43, 29, 65, 10, 20, 36, 78, 59. b. Vẽ lại hình cây tìm kiếm nhị phân ở câu a sau khi xen thêm các nút 15, 45, 55 c. Vẽ lại hình cây tìm kiếm nhị phân ở câu a sau khi xóa các nút 10, 20, 43, 65, 54 Bài 6 : Viết thủ tục xen, xóa một khóa x trên cây tìm kiếm nhị phân bằng phương pháp không đệ qui. 116
8. Phân tích thiết kế thuật toán BÀI 5 : PHƯƠNG PHÁP THAM LAM Mã bài : ITPRG3_12.5 Giới thiệu Giải quyết các bài toán tối ưu là một trong những vấn đề thường gặp trong các bài toán kinh tế, kỹ thuật, trí tuệ nhân tạo Một trong những giải pháp thuật toán sử dụng hiệu quả cho lớp các bài toán này là phương pháp tham lam (greedy method). Phương pháp này được sử dụng nhiều cho các bài toán điển hình như : lập lịch làm việc theo thời gian, tìm đường đi ngắn nhất, xử lý các vấn đề liên quan đến đồ thị, cây Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng: Nắm bắt được ý tưởng của phương pháp tham lam. Sử dụng phương pháp tham lam để giải quyết các bài toán tìm đường đi tối ưu, lập lịch phân công việc Áp dụng phương pháp tham lam để giải quyết một số bài toán trong thực tế. Thấy được lợi ra lợi thế của phương pháp tham lam trong việc xây dựng một số thuật toán. So sánh cách tiếp cận của phương pháp tham lam với các phương pháp khác. 5.1 Phương pháp tổng quát Phương pháp tham lam (greedy method) là một chiến lược thiết kế thuật toán thường được sử dụng để giải quyết các bài toán tối ưu. Nhiều vấn đề cần giải quyết có thể quy về vấn đề sau đây : Cho trước một tập các đối tượng A, chứa các đối tượng đã cho, đòi hỏi phải chọn ra một tập con S các đối tượng thỏa mãn một số điều kiện nào đó. Bất kỳ một tập con S nào của A thỏa mãn các yêu cầu đặt ra được gọi là nghiệm chấp nhận được của bài toán. Một hàm mục tiêu gắn mỗi nghiệm chấp nhận được với một giá trị nào đó. Một nghiệm chấp nhận được mà tại đó hàm mục tiêu có giá trị lớn nhất (hoặc nhỏ nhất) được gọi là nghiệm tối ưu. Tư tưởng của phương pháp tham lam là như sau : Ta xây dựng tập S dần dần từng bước, bắt đầu từ tập rỗng. Tại mỗi bước, ta sẽ chọn một phần tử “tốt nhất” trong các phần tử còn lại của A để đưa vào S. Việc lựa chọn một phần tử như thế ở mỗi bước được hướng dẫn bởi hàm chọn. 117
9. Phân tích thiết kế thuật toán Phần tử được chọn sẽ bị loại khỏi tập A. Nếu khi thêm phần tử được chọn vào tập S mà S vẫn còn thỏa mãn điều kiện của bài toán thì ta mở rộng S bằng cách thêm vào phần tử được chọn. procedure Greedy(A,S); {A là tập các ứng cử viên, S là nghiệm} begin S  ; while A 0) kể từ một thời điểm nào đó. Công việc i cho ta lợi nhuận pi > 0 nếu nó được hoàn thành trong thời hạn. Một nhà máy thực hiện các công việc này, tại mỗi thời điểm nhà máy chỉ thực hiện được một công việc, mỗi công việc được làm xong trong một đơn vị thời gian. Đương nhiên nhà máy phải chọn các công việc làm sao cho thu được nhiều lợi nhuận nhất. Trong bài toán trên, một tập con j các công việc sao cho nhà máy có thể hoàn thành tất cả các công việc trong thời hạn của chúng là nghiệm chấp nhận được. Giá trị của nghiệm J là tổng nhuận . Nghiệm tối ưu là nghiệm chấp nhận được và có lợi nhuận cao nhất. 118
10. Phân tích thiết kế thuật toán Ví dụ : với n = 4 và thời hạn, lợi nhuận như sau : i 1 2 3 4 pi 100 10 15 27 di 2 1 2 1 Ta có các nghiệm chấp nhận được và giá trị của chúng như sau Nghiệm Dãy sử lý Giá trị {1} 1 100 {2} 2 10 {3} 3 15 {4} 4 27 {1, 2} 2, 1 110 {1, 3} 1, 3 hoặc 3, 1 115 {1, 4} 4, 1 127 {2, 3} 2, 3 25 {3, 4} 4, 3 42 Nghiệm tối ưu là tập các công việc {1, 4}, được hoàn thành đúng hạn theo thứ tự 4 trước rồi đến 1, và cho lợi nhuận 127. Áp dụng chiến lược tham lam, ta sẽ xây dựng J theo từng bước, xuất phát từ J = . Tại mỗi bước ta sẽ chọn công việc cho lợi nhuân lớn nhất trong số các công việc còn lại. Không mất tính tổng quát, ta giả sử rằng các công việc đă được đánh số theo thứ tự lợi nhuận giảm dần p 1 p2 pn . Do đó, ta có thể đưa ra thuật toán tham lam tìm nghiệm của bài toán xử lý công việc trong thời hạn như sau. procedure Jobs; begin J ; for i:= 1 to n do if các công việc trong J{i} là hoàn thành trong thời hạn then J  J {i} 119
11. Phân tích thiết kế thuật toán end; Trong thuật toán trên còn một số vấn đề cần giải quyết là : làm thế nào để kiểm tra tập J các công việc có thể hoàn thành trong thời hạn. Nếu J có k công việc, sẽ có k! thứ tự xử lý (k! hoán vị của k công việc). Việc kiểm tra k! thứ tự xử lý đòi hỏi rất nhiều thời gian. Bổ đề sau đây chỉ ra rằng, ta chỉ cần kiểm tra một thứ tự xử lý, đó là thứ tự các công việc được sắp xếp theo thời hạn tăng dần. Bổ đề : Giả sử J là tập gồm k công việc và  = i1i2 là một hoán vị của các công việc trong J sao cho di1 di2 dik. Khi đó J là nghiệm chấp nhận được nếu và chỉ nếu các công việc trong J được thực hiện theo thứ tự  đều hoàn thành trong thời hạn. Thật vậy, nếu các công việc trong J được thực hiện theo thứ tự  đều đúng thời hạn thì J là chấp nhận được. Do đó, ta chỉ cần chỉ ra rằng, nếu J chấp nhận được thì khi thực hiện các công việc trong J theo thứ tự , tất cả các công việc đều đúng hạn. J là chấp nhận được có nghĩa là tồn ’ ’ tại một cách sắp xếp  = (r1,r2, rk) sao cho drj j, 1 j k. Giả sử  , gọi a là chỉ số nhỏ nhất mà ra ia.Giả sử ia = rb’ rõ ràng là b>a. ’ Trong hoán vị  ta trao đổi ra và rb để nhận được hoán vị mới  . Vì vậy dra drb (do ra =ic với c>a ’ nên dra = dic dia = drb), nên khi thực hiện các công việc theo thứ tự  ,các công việc đều hoàn thành đúng hạn. Tiếp tục cách này, ta sẽ biến đổi ’ thành . Bổ đề được chứng minh. Sau đây ta sẽ chứng minh rằng thuật toán được mô tả bởi thủ tục Jobs luôn luôn cho ta nghiệm tối ưu của bài toán xử lý các công việc trong thời hạn. Thật vậy, giả sử tập I các công việc là nghiệm tối ưu và J là tập các công việc được xác định bởi thủ tục Jobs. Giả sử S1=(i1,i2, ik) là thứ tự xử lý trong thời hạn của các công việc trong I, tức là it là công việc được làm từ thời điểm t-1 tới t. Tương tự ta giả sử S j=(j1,j2, ,jk) là thứ tự xử lý trong ’ thời hạn của các công việc trong J. Giả sử i là một công việc thuộc cả I và J, i=jt. Nếu t<t thì trong , ’ dãy S1 ta hoán vị it’ với it (nếu trong dãy S1 có it ), nếu không có it, thì ta chuyển it tới vị trí t’. Nếu t <t , thì trong dãy Sj ta hoán vị jt’ với jt (nếu trong dãy Sj có jt), nếu không có jt thì ta chuyển jt tới vị trí t. Làm như thế với mọi công việc i vừa thuộc I vừa thuộc J, ta biến đổi hai dãy S 1 và S2 thành hai dãy S’I và S’j sao cho các công việc i I J đứng ở cùng một vị trí trống (không có công việc nào được thực hiện ở thời điểm đó). Cả hai dãy S’I và S’J đều là lịch thực hiện trong thời hạn của các công việc trong I và J tương ứng. Ngoài các vị trí đó cả hai dãy S’I và S’J cùng chứa một công việc, còn các khả năng sau : Ở vị trí nào đó,dãy S’I chứa công việc a, còn dãy S’J trống. Khi đó J  {a} là chấp nhận được. Thuật toán Jobs phải chọn a đưa vào tập J. Vậy khả năng này không xảy ra. Ở vị trí nào đó, dãy S, J chứa b, còn dãy S’I trống. Khi đó I{b} là chấp nhận được và nó cho lợi nhuận cao hơn I. Điều này mâu thuẩn với I là nghiệm tối ưu. 120
12. Phân tích thiết kế thuật toán Chỉ còn khả năng dãy S’I chứa b và a b. Nếu pa>pb thì thuật toán tham lam phải chọn a vì (J \{b}  {a} là chấp nhận được. Nếu pa, pb thì khi thay a trong I bởi b ta nhận được nghiệm chấp nhận được với lợi nhuận cao hơn. Điều này mâu thuẩn với I là nghiệm tối ưu. Như vậy pa=pb. Tóm lại, trong hai dãy S’I và S’J tại mỗi vị trí cả hai chứa cùng một công việc, hoặc chứa hai công việc khác nhau nhưng cho cùng lợi nhuận. Do đó nghiệm tìm được J bởi thuật toán tham lam là nghiệm tối ưu. Sau đây ta đưa ra một cách cài đặt thuật toán Jobs. Giả sử các công việc được đánh số theo thứ tự lợi nhuận giảm dần. Mảng P[ 1 n] lưu lợi nhuận: P[1] P[2] P[n]. Mảng D[0 n] lưu thời hạn, trong đó D[0]=0. Mảng J[0 n], trong đó J[0]=0, và J[r],1 r k, để lưu các công việc đã được chọn bởi thuật toán,các công việc đuợc sắp xếp theo thời gian tăng dần, tức là D[J[1]] D[J[2]] D[J[k]]. Theo bổ đề, công việc i sẽ được chọn và được đưa vào thành phần thứ r +1 của mảng J nếu D[J[r]] D[i] D[J[r +1]], đồng thời D[i]>r và D[J[t]]> t với t = r+1, k Chúng ta có thủ tục sau đây procedure Jobs; begin D[0]:=0; J[0]:=0 k:=1; J[1]:=1; for i:=2 to n do begin r:=k while (D[J[r]]>D[i]) and (D[J[r]]>r) do r:= r-1; if (D[J[r]] r) then begin For I :=k downto r+1 do J[I+1]:=J[I]; J[r+1]:=i; k:=k+1; end; end; end; 5.3 Sơn đồ thị Giả sử G = (V.E) là một đồ thị không định hướng. Chúng ta cần sơn các đỉnh của đồ thị sao cho hai đỉnh kề nhau được sơn bởi hai màu khác nhau và sử dụng số màu ít nhất có thể được. 121
13. Phân tích thiết kế thuật toán Sử dụng chiến lược tham lam, ta có thể đưa ra thuật toán như sau: Dùng một màu để sơn (ví dụ màu đỏ). Chọn một đỉnh chưa sơn và sơn đỉnh đó. Sau đó với mỗi đỉnh chưa sơn, nếu nó không kề với các đỉnh được sơn bởi màu đang sử dụng thì ta sơn nó bởi màu đó. Khi không còn đỉnh nào có thể sơn được bởi màu đó thì ta dùng màu mới (chẳng hạn màu xanh) để sơn và áp dụng cách sơn như trên. Cứ thế tiếp tục cho tới khi ta sơn hết các đỉnh của đồ thị. c a b e d Ví dụ : Sơn đồ thị trong hình trên. Ta sơn đỉnh a bởi màu đỏ, khi đó đỉnh b không được sơn bởi màu đỏ, vì nó kề a đã sơn màu đỏ. Xét tiếp đỉnh c, nó không kề a, ta sơn c màu đỏ. Xét đến đỉnh d, nó không kề a và c, do đó d sơn màu đỏ. Xét tiếp đỉnh e, nó kề đỉnh c đã sơn màu đỏ, do đó không thể sơn e màu đỏ. Còn lại hai đỉnh chưa sơn là b và e, sử dụng màu mới (chẳng hạn màu xanh) để sơn b. Đỉnh e không kề b nên sơn nó màu xanh. Như vậy, ta chỉ cần hai màu, đây là giải pháp tối ưu. Tuy nhiên, thuật toán tham lam đã trình bày chỉ cho ta “nghiệm tốt”. Chẳng hạn, sau khi sơn a màu đỏ, nếu xét đến đỉnh e, ta sơn được e màu đỏ. Các đỉnh còn lại đều kề với a hoặc e, nên không thể sơn màu đỏ. Sơn b màu xanh. Không thể sơn c và d màu xanh. Phải chọn màu mới (vàng) và có thể sơn c và d màu vàng. Trong giải pháp này ta phải sử dụng 3 màu. Giả sử V là tập hợp các đỉnh của đồ thị. Gọi V0 là tập các đỉnh chưa được sơn và V1 là tập các đỉnh được sơn bởi màu mới. Ta mã hóa các màu bởi số nguyên k = 1, 2, 3, Khi đó thuật toán đã đưa ra được mô tả bởi thủ tục sau: procedure Coloring; begin k:=0 V0:=V; while V0  do begin k:=k+1; Chọn x Vo và sơn x bởi màu k; V1:={x}; for mỗi v Vo do if v không kề mọi w V1 then begin 122
14. Phân tích thiết kế thuật toán Sơn v bởi màu k; V1:= V1  {v}; end; V0:=V0-V1; end; end; Chúng ta đã chứng tỏ thuật toán Coloring chỉ cho ta nghiệm tốt, gần đúng với nghiệm tối ưu. Thế thì tại sao ta lại phải quan tâm đến các thuật toán như thế? Đối với bài toán sơn đồ thị và rất nhiều bài toán khác, các thuật toán tìm nghiệm chính xác đòi hỏi thời gian mũ, trong thực tế không sử dụng được khi cỡ bài toán khá lớn. Bài toán người bán hàng (salesperson) mà chúng ta đã xét trong phần trước cũng là bài toán mà thuật toán cho nghiệm tối ưu đều có độ phức tạp mũ. Đối với các bài toán như thế, chúng ta đành phải sử dụng các thuật toán cho nghiệm gần đúng, nhưng thời gian tính toán nhanh. 123
15. Phân tích thiết kế thuật toán BÀI TẬP Bài 1 : Tìm cây trùm tối thiểu cho đồ thị sau : Bài 2 : Tìm đường đi ngắn nhất giữa hai đỉnh bất kỳ của đồ thị trên. Bài 3 : Một chiếc ba lô có thể chứa được một khối lượng w. Có n loại đồ vật được đánh số 1, 2, , n. Mỗi đồ vật loại i có khối lượng ai và có giá trị ci (i=1, 2, , n). Cần sắp xếp các đồ vật vào ba lô để ba lô có giá trị lớn nhất có thể được. 124
16. Phân tích thiết kế thuật toán BÀI 6 : PHƯƠNG PHÁP QUAY LUI Mã bài : ITPRG3_12.6 Giới thiệu Trong kỹ thuật cơ bản thiết kế thuật toán, quay lui (backtracking) là một trong những kỹ thuật quan trọng. Nó được sử dụng trong lớp các bài toán có nhiều nghiệm khác nhau và người sử dụng có thể chọn ra một nghiệm hoặc tất cả các nghiệm của bài toán. Chúng ta sẽ khảo sát ở đây những bài toán điển hình như : bài toán tám hậu, bài toán ngựa đi tuần, tô màu đồ thị Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng: Nắm bắt được tư tưởng của phương pháp quay lui. Sử dụng phương pháp quay lui để giải quyết các bài toán tô màu đồ thị, bài toán tám hậu, bài toán ngựa đi tuần. Áp dụng phương pháp quay lui để giải quyết một số bài toán trong thực tế. Nêu ra lợi thế của phương pháp quay lui trong việc xây dựng một số thuật toán. So sánh cách tiếp cận của phương pháp quay lui so với các phương pháp khác. .16. Phương pháp tổng quát Trong kỹ thuật cơ bản thiết kế thuật toán, quay lui là một trong những kỹ thuật quan trọng nhất. Nó có thể được áp dụng để thiết kế thuật toán tìm ra một nghiệm hoặc tất cả các nghiệm của bài toán. Trong nhiều vấn đề, việc tìm nghiệm có thể quy về việc tìm một vecto hữu hạn (x 1,x2, xn, ) nhưng độ dài vecto có thể không được xác định trước. Vecto này cần phải thỏa mãn một số điều kiện nào đó tùy thuộc vào vấn đề cần giải. Các thành phần xi của vecto được chọn ra từ một tập hữu hạn Ai (i=1,2, n). Ví dụ : Bài toán 8 con hậu. 125
17. Phân tích thiết kế thuật toán Chúng ta cần đặt 8 con hậu vào bàn cờ 8 x 8 sao cho chúng không tấn công nhau, tức là không có cặp con hậu nào nằm cùng hàng, cùng cột, cùng đường chéo. Do các con hậu phải nằm trên các hàng khác nhau, ta sẽ đánh số các con hậu từ 1 đến 8, con hậu i là con hậu nằm dòng thứ i (i = 1, 2, , 8). Gọi là cột mà con hậu thứ i đứng. Như vậy nghiệm của bài toán 8 con hậu là vecto (x1, x2, , x8), trong đó 1 xi 8, tức là xi được chọn từ tập Ai={x1, x2, , x8). Vecto(x1, x2, , x8) là nghiệm nếu xi xj và hai ô (i, x1), (j, xj) không nằm trên cùng một đường chéo. Tư tưởng của phương pháp quay lui là như sau : Ta xây dựng vecto nghiệm dần từng bước, bắt đầu từ vecto không (). Thành phần đầu tiên x1 được chọn ra từ tập S1= A1. Khi đã chọn được các thành phần x1, , xi-1 thì từ các điều kiện của bài toán ta sẽ xác định được tập Si các ứng cử viên có thể chọn làm thành phần xi. Tập Si là tập con của Ai và phụ thuộc vào các thành phần x1, x2, , xi-1 đã chọn. Chọn một phần tử xi từ Si ta mở rộng nghiệm một phần (x1, x2, , xi-1) đến nghiệm một phần tử (x1, x2, , xi). Lặp lại quá trình trên để tiếp tục mở rộng nghiệm một phần tử (x1, x2, , xi-1, xi). Nếu không thể chọn được thành phần xi+1(khi Si+1=) thì ta quay lại chọn một phần tử khác của Si-1 làm xi-1 và cứ thế tiếp tục. Trong quá trình mở rộng nghiệm, ta phải kiểm tra nghiệm một phần có phải là nghiệm của bài toán hay không. Nếu chỉ cần tìm một nghiệm thì gặp nghiệm ta dừng lại. Còn nếu cần tất cả các nghiệm thì quá trình chỉ dừng lại khi tất cả các khả năng chọn các thành phần của vecto nghiệm đã bị vét cạn. Lược đồ tổng quát của thuật toán quay lui có thể biểu diễn bởi thủ tục Backtrack sau procedure Backtrack ; begin S1 :=A1 ; k:=1; while k>0 do begin while Sk  do begin chọn xk Sk; Sk:= Sk-{xk}; if (x1, ,xk) là nghiệm then viết ra nghiệm; k:=k+1; Xác định Sk; end; k:=k-1;{quay lui} end; end; 126
18. Phân tích thiết kế thuật toán Thuật toán quay lui có thể được biểu diễn bởi thủ tục đệ quy RBacktrack. Đó là thủ tục chọn thành phần thứ i của vecto nghiệm. Trong thủ tục này ta sử dụng phép toán thêm thành phần mới vào vecto nghiệm (ký hiệu là +) và phép toán loại thành phần cuối cùng khỏi vecto (ký hiệu là -). (a1, a2, , an-1) + (an) = (a1, a2, , an) (a1, a2, , an) - (an) = (a1, a2, , an-1) procedure RBacktrack(vecto,i); begin Xác định Si; for xi Si do begin vecto:= vecto+(xi); if vecto là nghiệm then viết ra vecto; RBacktrack (vecto, i+1) vecto:=veto-(x); end; end; Khi áp dụng lược đồ tổng quát của thuật toán quay lui cho các bài toán cụ thể, có ba điểm quan trọng cần lưu ý là : Tìm cách biểu diễn nghiệm của bài toán dưới dạng một dãy các đối tượng được chọn dần từng bước (x1, x2, , xi, ). Xác định được tập Si các ứng cử viên được chọn làm thành phần thứ i của vecto nghiệm. Chọn cách thích hợp để biểu diễn Si. Tìm các điều liện để một vecto đã chọn là nghiệm của bài toán. Cây không gian trạng thái Việc tìm kiếm vecto nghiệm (x1, , xi, xi+1, ) bằng phương pháp quay lui có thể quy về việc tìm kiếm trên cây không gian trạng thái. Cây được xây dựng theo từng mức như sau: Các đỉnh con thuộc gốc là các phần tử thuộc Si. Giả sử xi là đỉnh ở mức thứ i. Khi đó các đỉnh con của xi là thành phần thứ i+1 của vecto nghiệm khi ta đã chọn các thành phần x1, ,xi. Ở đây x1, , xi là các đỉnh nằm trên đường đi từ gốc đến xi. Như vậy, mỗi đỉnh của cây không gian trạng thái biểu diễn một nghiệm một phần, đó là vecto mà các thành phần của nó theo thứ tự là các đỉnh nằm trên đường đi từ gốc tới đỉnh đó. Việc tìm kiếm nghiệm theo chiến lược quay lui chẳng qua là tìm kiếm theo độ sâu trên cây không gian trạng thái (hay đi qua cây theo thứ tự preorder). 127
19. Phân tích thiết kế thuật toán .17. Bài toán 8 con hậu Trong bài toán 8 con hậu, nghiệm của bài toán có thể biểu diễn dưới dạng vecto (x1, x2, , x8), trong đó xi là tọa độ của con hậu đứng ở thứ i, xi {1, 2, , 8}. Các con hậu không đứng cùng cột, tức là xi xj với i j. Điều kiện để ô (i, xi) không cùng đường chéo với ô (j,xj) là i-j xi - xj . Do đó, khi ta đã chọn được (x1, , xk-1) thì xk được chọn là cột thỏa mãn các điều kiện : xk xj xk-xi k-i với mọi 1 i k x x x x x x x x Đây là một nghiệm của bài toán 8 con hậu. Trong thủ tục Queen dưới đây, vecto nghiệm được biểu diễn bởi mảng x[1 8]. Với mỗi k, ta lần lượt cho x[k] nhận giá trị từ 1 tới 8 và kiểm tra các điều kiện mà x[k] cần thõa mãn, nếu nó không thõa mãn (biến OK= false) thì tăng x[k] lên 1 đơn vị. procedure Queen; var x: Array[1 8]of integer; i,k:integer; OK: boolean; begin k:=1; x[k]:=0; while k>0 do begin x[k]:=x[k]+1; OK:=false; while(x[k]<=8) and (not OK)do begin i:=1; 128
20. Phân tích thiết kế thuật toán Ok:= true; while(i x[k]) and (abs(x[i]-x[k] 0 do begin I[k]:=I[k] +1; if I[k]<=n then 129
21. Phân tích thiết kế thuật toán begin if S +A[I[k]]<=M then if S+A[I[k]]= M then viết ra mảng I[1 k] else begin S:=S+A[I[k]]; I[k+1]:=I[k]; k:=k+1; end end else begin k:=k-1; S:=S-A[I[k]]; end; end; end; .19. Phương pháp nhánh và cận Phương pháp nhánh và cận là một dạng cải tiến của phương pháp quay lui, được áp dụng để tìm nghiệm của bài toán tối ưu. Giả sử nghiệm của bài toán có thể biểu diễn dưới dạng mọt vecto (a1, a2, , an), mỗi thành phần ai(i = 1, 2, , n) được chọn từ tập Si các đối tượng nào đó. Mỗi nghiệm (a1, , ak) của bài toán được gắn với một đối tượng giá trị cost(a1, , ak) và ta cần tìm nghiệm có giá thấp nhất (nghiệm tối ưu). Giả sử giá của các nghiệm một phần cũng được xác định và là các số thực không âm, đồng thời với nghiệm một phần bất kỳ (a1, , ak-1) và nghiệm mở rộng của nó (a1, ,ak-1,ak) ta luôn có cost(a1, , ak-1) cost (a1, , ak-1, ak). Tư tưởng của phương pháp nhánh và cận là như sau. Trong quá trình mở rộng từng bước nghiệm một phần, khi ta đạt được nghiệm một phần (a1, , ak), nếu biết rằng tất cả các nghiệm mở rộng của nó (a1, , ak, ak+1, ) đều có giá lớn hơn giá của nghiệm tốt nhất đã biết ở thời điểm đó, thì ta không cần mở rộng nghiệm một phần (a1, , ak) nữa. Giả sử cost*(a1, , ak) là cận dưới của giá các nghiệm (a1, , ak, ak+1, ), với (a1, , ak, ak+1, ) là mở rộng của nghiệm một phần (a1, , ak). Gọi giá của nghiệm tốt nhất là lowcost. 130
22. Phân tích thiết kế thuật toán Thực chất của phương pháp nhánh và cận là tìm kiếm theo độ sâu trên cây không gian trạng thái như kỹ thuật quay lui. Chỉ có điều khác là khi đạt tới đỉnh ak mà cost*(a1, , ak-1, ak) lowcost thì ta cắt đi tất cả các nhánh từ ak đi xuống các đỉnh con của nó. Tức là, khi đó ta không đi xuống các đỉnh con của ak nữa mà quay lên cha của nó là ak-1. Dùng làm giá trị ban đầu của lowcost ta có thể lấy lowcost = + hoặc lowcost là giá trị của một nghiệm được tìm thấy bằng phương pháp thực nghiệm nào đó. Thuật toán nhánh và cận có thể được mô tả nởi thủ tục BackBound sau : procedure BackBound; begin lowcost:= ; cost*:= 0; tính S1; k:=1; while k>0 do begin while(Sk<>) and (cost* < lowcost) do begin Chọn ak Sk cost* :=cost*(a1, ,ak); if (a1, ,ak)là nghiệm then if cost(a1, ,ak)< lowcost(a1, ,ak); k:=k+1; tính Sk; end; k:=k-1; cost*:= cost*(a1, ,ak); end; end; Như vậy, với phương pháp nhánh và cận, a không phải duyệt toàn bộ cây không gian trạng thái để tìm ra nghiệm tốt nhất mà bằng cách đánh giá cận dưới cost* của các nghiệm là mở rộng của nghiệm một phần, ta có thể cắt bỏ đi những nhánh không cần thiết, do đó việc tìm ra nghiệm tối ưu sẽ nhanh hơn. Cái khó nhất trong việc áp dụng phương pháp nhánh và cận là xây dựng được hàm đánh giá cận dưới cost*. Hàm này có được xây dựng tốt thì ta cắt bỏ được nhiều nhánh không cần thiết và thuật toán nhận được mới có cải tiến đáng kể so với thuật toán vét cạn. 131
23. Phân tích thiết kế thuật toán .20. Bài toán người bán hàng Chúng ta trở lại với bài toán người bán hàng đã được xét ở phần trước. Bài toán được quy về bài toàn trên đồ thị : Cho G= (V,E) là đồ thị định hướng, tìm chu trình xuất phát từ một đỉnh qua tất cả các đỉnh còn lại với độ dài gắn nhất. Chúng ta đã đưa ra một thuật toán tham lam cho ra nghiệm gần đúng. Sau đây chúng ta sẽ áp dụng kỹ thuật nhánh và cận để giải bài toán này. Giả sử đồ thị có n đỉnh, V={1, 2, , n} và đỉnh xuất phát là 1. Nghiệm một phần là đường đi (a1, a2, , ak), a1=1, ai aj(i j). Các nghiệm là mở rộng của nghiệm một phần (a1, a2, , ak) sẽ là các chu trình có đoạn đầu trùng với (a1, a2, , ak). Sau đây ta sẽ đưa ra một cách đánh giá cận dưới của các chu trình là mở rộng của đường đi (a1, a2, , ak). Chúng ta sẽ trình bày phương pháp đánh giá cận dưới qua một đồ thi cụ thể. Giả sử G là một đồ thị gồm 5 đỉnh với độ dài các cung được cho bởi ma trận sau: 0 14 4 10 20 14 0 7 8 7 4 5 0 7 16 11 7 9 0 2 18 7 17 4 0 Một đường đi xuất phát từ 1, chẳng hạn (1, 4, 3) sẽ có hai nghiệm mở rộng, đó là chu trình (1, 4, 3, 5, 2, 1) có độ dài là 10 + 9 + 16 + 7 + 14 = 56 và chu trình (1, 4, 3, 2, 5, 1) có độ dài 10 + 9 + 5 + 7 + 8 = 49. Giả sử ta cần đánh giá độ dài đường đi từ đỉnh i tới đỉnh j và phải đi qua các đỉnh k thuộc một tập K các đỉnh nào đó, tức là đường đi có dạng (i, , k, , j), k K. Giá của đường đi này được phân thành : giá rời khỏi đỉnh i, giá thăm các đỉnh k, giá đến đỉnh j. Giá thăm đỉnh k lại được phân thành giá đến k và giá rời k. Chẳng hạn, khi rời đỉnh 1 ta phải đi qua một đoạn đường ít nhất là 2, vì 2= min(14/2, 4/2,10/2, 20/2). Khi đến đỉnh 2 ta phải đi qua một đoạn đường ít nhất là 5/2=min(14/2, 5/2, 7/2, 7/2) khi rời đỉnh 2 đọan đường ít nhất phải đi là 7/2=min(14/2, 7/2, 8/2, 7/2). Vậy giá thăm đỉnh 2 tốt nhất là 5/2 + 7/2=6. Bằng cách này ta đánh giá được cận dưới độ dài các đường đi từ i đến jqua các đỉnh k K. Chẳng hạn, trong đồ thị trên, các chu trình xuất phát từ 1 qua các đỉnh 2, 3, 4, 5 rồi trở về 1 có độ dài ít nhất là : 2+4+6+3+3+2=20 Bây giờ, ta đánh giá cận dưới độ dài cácchu trình là mở rộng của đường đi(1,2): 132
24. Phân tích thiết kế thuật toán Độ dài cung (1, 2) là 14 Cận dưới độ dài các đường đi từ 2 tới 1 và qua các đỉnh 3, 4, 5 được tính như sau : Giá rời đỉnh 2 : min(7/2, 8/2, 7/2)=7/2 Giá đến đỉnh 3 : min(7/2, 9/2, 17/2)=7/2 Giá rời đỉnh 3 : min(4/2, 7/2, 16/2)=4/2 Như vậy : giá thăm đỉnh 3 là 11/2 giá thăm đỉnh 4 là 3 giá thăm đỉnh 5 là 3 giá thăm về đỉnh 1 (từ 3 hoặc 4 hoặc 5) là 2. Như vậy cận dưới độ dài các chu trình là mở rộng của đường đi (1, 2) là : 14+7=31 (tức là cost*(1, 2) = 31. Một cách tương tự ta tính được cost*(1,3)=24, cost*(1,4)=29, cost*(1,5)=41. (1) cận 29 (1, 2) (1, 3) (1, 4) (1, 5) cận 31 cận 24 cận 29 cận 41 (1, 3, 2) (1, 3, 4) (1, 3, 5) cận 24 cận 30,5 cận 40,5 (1,3,2,4)= (1,3,2,5)= (1,3,2,4,5,1)=37 (1,3,2,5,4,1)=31 Hình trên biểu diễn một phần cây không gian trạng thái. Mỗi đỉnh biểu diễn một nghiệm một phần và cận dưới của nó. 133
25. Phân tích thiết kế thuật toán Khi mở rộng các nghiệm một phần tới thời điểm nhận được các nghiệm một phần được biểu diễn bởi hình trên, ta đã được nghiệm tốt nhất ở thời điểm đó là chu trình (1, 3, 2, 5, 4, 1) có độ dài là 31. Tức là tới thời điểm đó lowcost = 31 và do đó không cần mở rộng các nghiêm một phần (1, 2), (1, 5) và (1, 3, 5) vì cận dưới của chúng 31. 134
26. Phân tích thiết kế thuật toán BÀI TẬP Dùng kỹ thuật quay lui để trình bày các thuật toán để : Bài 1 : Bài toán ngựa đi tuần : giả sử chúng ta có số ngựa là N, số nhóm luân phiên đi tuần là M và số ngựa mỗi nhóm phải là K. Viết giải thuật phân nhóm ngựa đi tuần sao cho thời gian giữa hai lần đi tuần liên tiếp của một con ngựa bất kỳ là lớn nhất có thể. Bài 2 : Bài toán tô màu đồ thị : Giả sử G = (V.E) là một đồ thị không định hướng. Chúng ta cần sơn các đỉnh của đồ thị sao cho hai đỉnh kề nhau được sơn bởi hai màu khác nhau và sử dụng số màu ít nhất có thể được. Bài 3 : Thăm các đỉnh của đồ thị sau : 135
27. Phân tích thiết kế thuật toán BÀI 7 : QUY HOẠCH ĐỘNG Mã bài : ITPRG3_12.7 Giới thiệu Quy hoạch động (dynamic programming) là một phương pháp có ý tưởng giống như phương pháp chia để trị. Nó cho phép chúng ta phân rã một bài toán lớn thành những bài toán nhỏ hơn và tìm nghiệm những bài toán nhỏ này trước, sau đó tìm ngược lại nghiệm của bài toán lớn. Điểm khác nhau cơ bản giữa hai phương pháp này phương pháp chia để trị phân rã và giải quyết bài toán từ trên xuống (top-down) còn quy hoạch động giải quyết bài toán theo kiểu từ dưới lên (down-top). Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng: Nắm bắt được ý tưởng của phương pháp quy hoạch động. Sử dụng phương pháp quy hoạch động để giải quyết các bài toán sắp xếp các đồ vật vào ba lô, tìm dãy con chung của hai dãy số, tìm đường đi ngắn nhất Áp dụng phương pháp quy hoạch động để giải quyết một số bài toán trong thực tế. Nêu ra lợi thế của phương pháp quy hoạch động trong việc xây dựng một số thuật toán. So sánh cách tiếp cận của phương pháp quy hoạch động so với các phương pháp khác. .21. Phương pháp tổng quát Trong nhiều trường hợp, để giải một bài toán đã cho ta đưa về giải một số bài toán con rồi kết hợp nghiệm của bài toán con ta nhận được nghiệm của bài toán cần giải. Để giải các bài toán con này ta lại đưa về việc giải các bài toán con nhỏ hơn. Quá trình trên sẽ tiếp tục cho tới khi nhận được các bài toán con có thể giải được dễ dàng. Đó là kỹ thuật chia để trị mà ta đã xét. Chia để trị là kỹ thuật từ trên xuống (top-down), nó giải các bài toán con nhận được trong quá trình chia nhỏ một cách độc lập. Tuy nhiên, trong quá trình phân chia như thế, thông thường ta gặp rất nhiều lần cùng một bài toán con. Do đó, nếu giải quyết bài toán bằng kỹ thuật top-down chúng ta phải tính lại nhiều lần cùng một bài toán. Thuật toán nhận được sẽ kém hiệu quả. Ví dụ: Tính các hệ số nhị thức 136
28. Phân tích thiết kế thuật toán Số tổ hợp chập k của n, ký hiệu là hoặc là số các cách chọn k phần tử khác nhau từ một tập n phần tử. Các số tổ hợp còn được gọi là hệ số nhị thức. Các hệ số nhị thức có rất nhiều ứng dụng trong toán học và thường được sử dụng để phân tích và đánh giá các thuật toán. Công thức sau đây cho phép ta tính được thông qua và =1 nếu i =0 hoặc i=j = + nếu 0<i<j Chúng ta có thể tính các hệ số nhị thức một cách trực tiếp bởi hàm đệ quy sau : function Coef(k, n :integer) :integer ; begin if(k=0)or(k=n) then coef:=0 else coef:= coef(k,n-1) + coef(k-1,n-1); end; Khi đó, để tính coef(k, n), rất nhièu giá trị coef(i, j) với i<k, j<n được tính lặp lại nhiều lần. Chẳng hạn, để tính ceof(3, 5) ta phải tính lặp lại hai lần coef(2, 3), 3 lần coef(1, 2) Thời gian sẽ rất lớn, thực tế là không chấp nhận được khi các giá trị đầu vào lớn. Một cách tiếp cận khác để tính là ta tính các với i<k, j<n xuất phát từ trường hợp đơn giản nhất =1 với j n. Trong quá trình tính ta sẽ sử dụng một bảng để lưu các giá trị đã tính. Bằng cách đó ta sẽ tránh được việc tính lại nhiều lần cùng một giá trị nào đó. Cụ thể ở đây ta sử sụng mảng C[0 k, 0 n], trong đó C[i, j] (0 i k, 0 j n) lưu và tính C[i, j] lần lượt theo hàng. Thực tế, vì i j, ta chỉ cần tính các giá trị của tam giác nằm trên đường chéo chính. Vì vậy = + , mỗi phần tử C[i, j] ở hàng i cột j, là tổng của hai phần tử ở bên trái nó, phần tử C[i, j–1] và phần tử nằm trên phần tử này là C[i –1, j –1]. Sau đây là bảng lưu các giá trị , 0 i k=3 và 0 j n =5 j = 0 1 2 3 4 5 i = 0 1 1 1 1 1 1 137
29. Phân tích thiết kế thuật toán 1 1 2 3 4 5 2 1 3 6 10 3 1 4 10 Chúng ta dễ dàng viết được thủ tục tính , với 0 i k và 0 j n và i j, bằng phương pháp này: begin for j:= 0 to n do C[0,j]:=1 for i:= 1 to k do begin C[i,j]:= 1; for j:= i +1 to n do C[i,j]:= C[i,j –1] +C[i –1,j –1]; end; end; Quy hoạch động là lỹ thuật từ dưới lên (bottom–up). Chúng ta xuất phát từ những trường hợp riêng đơn giản nhất của bài toán, thường là thấy ngay nghiệm của chúng. Sau đó kết hợp nghiệm của chúng thì ta được nghiệm của bài toán con có cỡ lớn hơn. Rồi lại kết hợp nghiệm của các bài toán con này để nhận nghiệm của bài toán lớn hơn nữa và cứ thế tiếp tục cho đến khi nhận được nghiệm của bài toán đã cho. Tư tưởng cơ bản của bài toán quy hoạch động là quá trình “đi từ dưới lên”, ta sử dụng một bảng để lưu giữ lời giải của cả bài toán con đã giải. Khi giải một bài toán con cần đến bài toán con cỡ nhỏ hơn, ta chỉ cần tìm ở trong bảng mà không cần giải lại . Chính vì thế mà thuật toán được thiết kế bằng quy hoạch động sẽ rất có hiệu quả. Để giải một bài toán quy hoạch động, chúng ta cần tiến hành những công việc sau : Tìm nghiệm của các bài toán con (các trường hợp riêng) đơn giản nhất. Tìm ra các công thức (hoặc quy tắc) xây dựng nghiệm của bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ hơn. Tạo ra một bảng để lưu giữ các nghiệm của bài toán con. Sau đó tính nghiệm của các bài toán con theo các công thức đã tìm ra và lưu vào bảng. Từ bảng đã làm đầy tìm cách xây dựng nghiệm của bài toán. Sau đây chúng ta sẽ đưa ra một số ví dụ minh họa. 138
30. Phân tích thiết kế thuật toán .22. Bài toán sắp xếp các đồ vật vào ba lô Một chiếc ba lô có thể chứa được một khối lượng w. Có n loại đồ vật được đánh số 1, 2, , n. Mỗi đồ vật loại i có khối lượng ai và có giá trị ci (i=1, 2, , n). Cần sắp xếp các đồ vật vào ba lô để ba lô có giá trị lớn nhất có thể được. Giả sử rằng mỗi loại có đủ nhiều để xếp. Phát biểu bài toán : Cho trước w, ai, ci (i=1, 2, , n) là các số nguyên dương. Cần tìm x=(x1, x2, , xn), trong đó xi là số nguyên không âm sao cho: w (1) và đạt max (2) Xét trường hợp riêng đơn giản nhất : chỉ có một loại đồ vật (n=1). Trường hợp này ta tìm được ngay lời giải : xếp đồ vật vào ba lô cho tới khi nào không xếp được nữa thì thôi, tức là x 1 = w div a1. Gọi f(k, v) là giá rtị lớn nhất của ba lô chứa được khối lượng v và chỉ xếp k loại đồ vật 1, 2, , k ; với i k n, 1 v w. Ta tìm được công thức để tính f(k, v). Với k = 1, 1 v w, ta có : x1 = v div a1 và f(1, v) = x1c1. Giả sử đã tính được f(s, u), với 1 s < và 1 u v, ta cần tính f(k, v) với 1 v w. Gọi yk = v div ak, ta có: f(k, v) = max {f (k-1, u) + xkck} (3) Trong đó, max được lấy với tất cả xk = 0, 1, , yk và u = v - xkak Giá trị lớn nhất của ba lô sẽ là f(n, w). Chúng ta sẽ sử dụng mảng A[1 n, 1 w] để lưu các kết quả trung gian. A[ k,v] (1 k n, 1 v w) là bản ghi gồm hai trường, một trường chứa f(f, v) và một trường chứa x k, trong đó xk là giá trị mà trong (3) biểu thức f(k-1, u) + xkck đạt max. Từ công thức (3), suy ra rằng các giá trị của bảng A có thể tính dược dễ dàng lần lượt theo dòng 1, 2, , n. Vấn đề đặt ra bây giờ là từ bảng A đã làm đầy, làm thế nào để xác định được x =(x1, x2, , xn) và f(n, w). 139
31. Phân tích thiết kế thuật toán Ô A[n, w] chứa f(n, w) và xn. Tính v = w – xnan. Tìm đến ô A[n –1, v] ta biết được xn-1. Tiếp tục quá trình đó, ta tìm được xn-2, , x2, x1. .23. Bài toán tìm đường đi ngắn nhất từ một đỉnh Cho đồ thị G với tập đỉnh V và tập các cạnh E (đồ thị có hướng hoặc vô hướng). Mỗi cạnh của đồ thị được gán một nhãn, đó là một giá trị không âm, nhãn này còn được gọi là giá của cạnh. Cho trước một đỉnh xác định v, gọi là đỉnh nguồn. Bài toán đặt ra là tìm đường đi ngắn nhất từ đỉnh v đến các đỉnh còn lại của G. Tức là tìm đường đi từ v đến các đỉnh còn lại với tổng các giá của các cạnh trên đường đi là nhỏ nhất. Nếu như đồ thị có hướng thì đường đi này là đường đi có hướng. Ta có thể giải bài toán bằng cách xác định một tập hợp S chứa các đỉnh mà khoảng cách ngắn nhất từ nó đến đỉnh nguồn v đã biết. Khởi đầu S = {V}. Sau đó tại mỗi bước ta sẽ thêm vào S các đỉnh mà khoảng cách từ nó đến v là ngắn nhất. Với giả thiết rằng mỗi cung có một giá trị không âm thì ta luôn luôn tìm được một đường đi ngắn nhất như vậy mà chỉ đi qua các đỉnh đã tồn tại trong S. Ðể dễ dàng chi tiết hóa thuật toán , giả sử G có n đỉnh và nhãn trên mỗi cung được lưu trong mảng C, tức là C[i, j] bằng giá (có thể xem là độ dài) của cung (i, j). Nếu i và j không có cung nối thì ta cho C[i, j] =Ġ. Ta sẽ dùng một mảng D có n phần tử để lưu độ dài của đường đi ngắn nhất từ v đến mỗi đỉnh của đồ thị. Khởi đầu thì giá trị này chính là độ dài cạnh (v, i), tức D[i] = C[v, i]. Tại mỗi bước của thuật toán thì D[i] sẽ lưu độ dài đường đi ngắn nhất từ đỉnh v đến đỉnh i, đường đi này chỉ đi qua các đỉnh đã có trong S. Ðể cài đặt thuật toán dễ dàng, ta giả sử các đỉnh của đồ thị được đánh số từ 1 đến n và đỉnh nguồn là đỉnh 1. Dưới đây là thuật toán Dijkstra để giải bài toán trên : Procedure Dijkstra ; Begin S := [1] ; { S chỉ chứa đỉnh nguồn } For i:=2 to n do D[i] := C[1, i] ; { Khởi đầu các giá trị cho D } For i:=1 to n - 1 do Begin Lấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ; Thêm w vào S ; For mỗi đỉnh u thuộc V - S do D[u] := Min (D[u], D[w] + C[w, u]) ; 140
32. Phân tích thiết kế thuật toán End; End; Nếu muốn lưu trữ lại các đỉnh trên đường đi ngắn nhất để có thể xây dựng lại đường đi này từ đỉnh nguồn đến các đỉnh khác, ta dùng một mảng P. Mảng này sẽ lưu P[u] = w với đỉnh u là đỉnh trước của đỉnh w trên đường đi ngắn nhất. Lúc khởi đầu ta cho P[u] = 1, với mọi u<>1. Thuật toán Dijkstra ở trên sẽ được viết lại như sau : Procedure Dijkstra ; Begin S := [1] ; { S chỉ chứa đỉnh nguồn } For i:=2 to n do Begin D[i] := C[1, i] ; { Khởi đầu các giá trị cho D } P[i] := 1 ; { Khởi đầu các giá trị cho P } End ; For i:=1 to n - 1 do Begin Lấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ; Thêm w vào S ; For mỗi đỉnh u thuộc V - S do If (D[w] + C[w, u] < D [u]) then Begin D[u] := D[w] + C[w, u] ; P[u] := w ; End ; End; End; Ví dụ : áp dụng thuật toán Dijkstra đã được trình bày ở trên cho đồ thị hình sau 141
33. Phân tích thiết kế thuật toán .24. Dãy con chung của hai dãy số Cho hai dãy số nguyên a = (a1, , am) và b = (b1, , bn). Chúng ta cần tìm dãy số nguyên c = (c1, , ck) sao cho c là dãy con của a và b và c có độ dài lớn nhất có thể được. Ví dụ : Nếu a = (3, 5, 1, 3, 5, 5, 3) và b = (1, 5, 3, 5, 3, 1) thì dãy con chung dài nhất là c = (5 , 3, 5, 3), hoặc c = (1, 3, 5, 3), hoặc c = (1, 5, 5, 3). Trường hợp đơn giản, khi một trong hai dãy a và b rỗng (m =0 hoặc n=0), ta thấy dãy con dài nhất là dãy rỗng. Ta xét các đoạn đầu của hai dãy a và b có độ dài i và j tương ứng (a 1, a2, ,ai) và b(b1, b2, ,bj) với i v m, 0 j n. Gọi L(i, j) là độ dài lớn nhất của dãy con chung của hai dãy (a1, a2, , ai) và (b1, b2, , bj). Như vậy, L(m, n) sẽ là độ dài lớn nhất của dãy con chung của a và b. Bây giờ ta tìm cách tính L(i, j) thông qua L(s, t) với s i, t j. Dễ dàng thấy sự đúng đắn của công thức sau: 142
34. Phân tích thiết kế thuật toán Nếu i=0 hoặc j=0 thì L(i, j) =0 Nếu i>0 và j>0 và ai bj thì L(i, j)= max {L(i,j-1), L(i-1,j)} Nếu i>0 và j>0 và ai =bj thì L(i, j) = 1 + L(i-1, j-1) Chúng ta sẽ lưu các giá trị L(i, j) vào mảng L[0 m, 0 n]. Từ công thức (2) và (3) ta thấy rằng, nếu biết L[i, j-1], L[i-1, j] và L[i-1, j-1] ta tính ngay được L[i, j], do đó ta có thể tính được các phần tử của mảng L[0 m, 0 n] từ góc trên bên trái lần lượt theo các đường chéo song song. 0 1 2 n 0 1 2 m Bây giờ từ mảng L đã được làm đầy, ta xây dựng dãy con chung dài nhất là k = L[m, n]. Ta xác định các thành phần của c = (c1, , ck-1,ck) lần lượt từ bên phải. Trong bảng L ta đi từ ô L[m, n]. Giả sử ta đang ở ô L[i, j] và ta đang cần xác định c l (1 l k). Nếu ai = bi thì ta lấy cl = ai, giảm l đi một và đi lên ô L[i-1, j-1]. Còn nếu ai bj thì hoặc L[i, j] = L[i, j-1] hoặc L[i, j] = L[i-1, j]. Trong trường hợp L[i, j] = L[i, j-1], ta đi tới ô L[i, j-1]. Còn nếu L[i, j] = L[i-1, j] thì ta đi lên ô L[i-1, j]. Tiếp tục quá trình trên ta xác định được tất cả các thành phần của dãy con dài nhất c. Bài toán này và bài toán chiếc ba lô thuộc lớp tối ưu. Quy hoạch động là phương pháp hay được sử dụng để giải các bài toán tối ưu. Đương nhiên không phải bài toán tối ưu nào cũng có thể giải bằng quy hoạch động mà chỉ có thể sử dụng kỹ thuật quy hoạch động cho các bài toán thõa mãn nguyên lý tối ưu. Có thể phát biểu nguyên lý tối ưu một cách đơn giản như sau: nghiệm tối ưu của một bài toán con bất kỳ (của bài toán) là một sự kết hợp các nghiệm tối ưu của các bài toán con của nó. .25. Bài toán người bán hàng Chúng ta trở lại bài toán người bán hàng đã xét ở các phần trước. Ta đã đưa ra một thuật toán được thiết kế dựa trên kỹ thuật tham lam cho bài tóan này. Thuật toán này chỉ cho nghiệm gần đúng. Ta cũng đã đưa ra một thuật toán theo phương pháp nhánh và cận cho bài toán này. Trong mục này ta đã áp dụng phương pháp quy hoạch động để giải bài toán này. Giả sử G = (V, E) là đồ thị định hướng với V ={1, 2, , n} và dộ dài các cung là C[i, j] > 0 nếu (i, j) E và C[i, j] = nếu (i, j) E. Không mất tính tổng quát, ta giả sử đường đi của người bán hàng là đường đi xuất phát từ đỉnh 1 qua tất cả các đỉnh con lại đúng một lần rồi lại trở về đỉnh 1. 143
35. Phân tích thiết kế thuật toán Bất kỳ đường đi nào của người bán hàng có thể phân thành cung (1,k) với k V – {1} và đường đi từ đỉnh k đến đỉnh 1 qua mỗi đỉnh thuộc V- {1, k} đúng một lần. Dễ dàng thấy rằng, nếu đường đi của người bán hàng là ngắn nhất thì đường đi từ k tới 1 qua các đỉnh thuộc V – {1, k} phải ngắn nhất. Do đó nguyên lý tối ưu được thỏa mãn. Gọi d(i, S) là độ dài đường đi ngắn nhất từ đỉnh i tới đỉnh 1 qua mọi đỉnh k S đúng một lần. Ta có công thức sau : d(i, S) = (C[i, k] + d(k, S - {k}) (1) Nghiệm tối ưu cần tìm là d(1, V - {1}) và d(1, V - {1}) = (C[1, k] + d(k, V - {1, k}) (2) Như vậy chúng ta sẽ tính được d(1, V - {1}) nếu ta biết được d(k, V - {1} với mọi k = 2, , n. Rõ ràng là d(i, ) = C[i, 1] với 2 i n. Sử dụng (1) ta tính được d(i, S) với tất cả S chỉ chứa 1 đỉnh. Từ đó ta tính được d(i, S) với S chỉ chứa 2 đỉnh. Tiếp tục ta tính được d(i, S) với S chứa 3 đỉnh, 4 đỉnh, cho tới khi ta tính được các d(k, V - {1, k}) với k = 2, , n. Từ dó, theo (2) ta tính được độ dài đường đi ngắn nhất của người bán hàng. Ví dụ : Xét đồ thị định hướng có 4 đỉnh và độ dài các cung được cho bởi ma trận C như sau 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0 Ta có : d(2, ) = C[2, 1] = 5 d(3, ) = C[3, 1] = 6 d(4, ) = C[4, 1] = 8 Sử dụng (2) ta tính được : d(2, {3}) = C[2, 3] + d(3, ) = 15 d(2, {4}) = 18 d(3, {2}) = 18 144
36. Phân tích thiết kế thuật toán d(3, {4}) = 20 d(4, {2}) = 13 d(4, {3}) = 15 Tiếp theo ta tính được d(i, S) với i 1, và S gồm hai đỉnh khác 1 và i. d(2, {3, 4}) = min {C[2, 3] + d(3, {4}), C[2, 4] + d(4, {3})} = 25 d(3, {2, 4}) = min {C[3, 2] + d(2, {4}), C[3, 4] + d(4, {2})} = 25 d(4, {2, 4}) = min {C[4, 2] + d(2, {3}), C[4, 3] + d(3, {2}) } = 23 Cuối cùng ta có : d(1, {2, 3, 4}) = min{C[1, 2]+d(2, {3, 4}+C[1, 3]+d(3, {2, 4})+C[1,4]+d(4, {2, 3})} = min {35,40,43} = 35 Như vậy, đường đi ngắn nhất của người bán hàng có độ dài 35. Đường đi ngắn nhất này có thể xây dựng được bằng cách với mỗi d(i, S) ta lưu lại đỉnh j mà tại đó vế phải của (1) đạt min. Gọi J(i, S) là đỉnh j này. Chẳng hạn, từ các kết quả tính toán trên ta có : J(1, {2, 3, 4}) = 2 J(2, {3,4}) = 4 J(4, {3}) = 3 Do đó đường đi ngắn nhất là (1, 2, 4, 3, 1). Chúng ta thử đánh giá thời gian thực hiện thuật toán này. Gọi N là số các d(i, S) cần phải tính. Trước hết có n-1 khả năng chọn i (i chạy từ 1 tới n). với mỗi i số các tập S có k phần tử, S không chứa 1 và i, là . Do đó : N = = (n-1)2n-2 Mặt khác để tính d(i, S) với S gồm k phần tử, theo công thức (1) ta phải thực hiện k-1 phép so sánh để tìm min. Do đó thuật toán đòi hỏi thời gian n22n. So sánh với phương pháp vét cạn n! đường đi để tìm ra đường đi nhắn nhất, thuật toán này tốt hơn. 145
37. Phân tích thiết kế thuật toán BÀI 7(tiếp theo): NÉN DỮ LIỆU MÃ BÀI ITPRG3_12.7 7.6 Phương pháp nén dữ liệu I. Giới thiệu chung 1. Nguyên tắc của nén dữ liệu Thông thường, hầu hết các tập tinh trong máy tính có rất nhiều thông tin dư thừa, việc thực hiện nén tập tin thực chất là mã hoá lại các tập tin để loại bỏ các thông tin dư thừa. Nhìn chung không thể có phương phát nén tổng quát nào cho kết quả tốt đối với tất cả các loại tập tin vì nếu không ta sẽ áp dụng n lần phương pháp nén này để đạt được một tập tin nhỏ tuỳ ý! Kỹ thuật nén tập tin thường được áp dụng cho các tập tin văn bản (Trong đó có một số kí tự nào đó có xác suất xuất hiện nhiều hơn các kí tự khác), các tập tin ảnh bitmap (Mà có thể có những mảng lớn đồng nhất), các tập tin dùng để biểu diễn âm thanh dưới dạng số hoá và các tín hiệu tương tự (analog signal) khác (Các tín hiệu này có thể có các mẫu được lặp lại nhiều lần). Ðối với các tập tin nhị phân như tập tin chương trình thì sau khi nén cũng không tiết kiệm được nhiều. Ngoài ra, trong một số trường hợp để nâng cao hệ số nén người ta có thể bỏ bớt một số thông tin của tập tin (Ví dụ như kỹ thật nén ảnh JPEG). 2. Tầm quan trọng của nén dữ liệu trong truyền tin nối tiếp Trong kỹ thuật truyền tin nối tiếp, do các bit dữ liệu được truyền đi nối tiếp, lại bị giới hạn về dãi thông của kênh truyền và giới hạn về các chuẩn ghép nối nên tốc độ truyền tin tương đối chậm. Ðể tăng tốc độ truyền ta có thể dùng nhiều phương pháp như sử dụng kỹ thuật điều chế pha nhiều mức, điều chế QAM, TCM Nén dữ liệu trước khi truyền đi cũng là một trong các phương pháp nhằm tăng tốc độ truyền dữ liệu. Trong các modem hiện đại, việc thực hiện nén dữ liệu trước khi truyền đi có thể được thực hiện ngay trong modem theo các giao thức V42bis, MNP5. Phương pháp này đòi hỏi hai modem phải có cùng một giao thức nén dữ liệu, điều này nhiều khi khó thoã mãn. Có một phương pháp khác là thực hiện nén các tập tin ngay tại các máy vi tính trước khi truyền đi, tại các máy tính nhận, các tập tin lại được giải nén để phục hồi lại dạng ban đầu. Phương pháp này có ưu điểm là bên phát và bên thu chỉ cần có chung phần mềm nén và giải nén, ngoài ra còn có thể áp dụng được để truyền dữ liệu qua các modem không hỗ trợ nén dữ liệu hoặc truyền dữ liệu trực tiếp qua cổng COM của máy tính. Nhược điểm của phương pháp này là các máy vi tính phải tốn thêm thời gian nén và giải nén, nhưng do sự phát triển nhanh chóng của các bộ vi xử lý mà thời gian thực hiện nén và giải nén được giảm nhỏ hơn rất nhiều thời gian để truyền dữ liệu. Ví dụ, khi truyền một tập tin có kích thước là 100Kbyte với dạng thức của một SDU là: 8 bits dữ liệu, 2 bit STOP và 1 bit START, không dùng bit chẵn lẻ, tốc độ truyền là 9600bits/giây thì mất khoảng 120 giây, trong khi một máy vi tính với bộ vi xử lí 80386 có thể thực hiện nén tập tin trên xuống còn 50Kbyte chỉ mất chưa đến 10 giây II. Một số phương pháp nén dữ liệu 1. Phương pháp mã hoá độ dài loạt (Run-Length Encoding) Loại dư thừa đơn giản nhất trong một tập tin là các đường chạy dài gồm các kí tự lặp lại, điều này thường thấy trong các tập tin đồ hoạ bitmap, các vùng dữ liệu hằng của các tập tin chương trình, một số tập tin văn bản 146
38. Phân tích thiết kế thuật toán Ví dụ, xét chuỗi sau: AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD Chuỗi này có thể được mã hoá một cách cô đọng hơn bằng cách thay thế chuỗi kí tự lặp lại bằng một thể hiện duy nhất của kí tự lặp lại cùng với một biến đếm số lần kí tự đó được lặp lại. Ta muốn nói rằng chuỗi này gồm bốn chữ A theo sau bởi ba chữ B rồi lại theo sau bởi hai chữ A, rồi lại theo sau bởi năm chữ B Việc nén một chuỗi theo phương pháp này được gọi là mã hoá độ dài loạt. Khi có những loạt dài, việc tiết kiệm có thể là đáng kể. Có nhiều cách để thực hiện ý tưởng này, tuỳ thuộc vào các đặc trưng của ứng dụng (các loạt chạy có khuynh hướng tương đối dài hay không ? Có bao nhiêu bit được dùng để mã hoá các kí tự đang được mã ?). Nếu ta biết rằng chuỗi của chúng ta chỉ chứa các chữ cái, thì ta có thể mã hoá biến đếm một cách đơn giản bằng cách xen kẻ các con số với các chữ cái. Vì vậy chuỗi kí tự trên được mã hoá lại như sau: 4A3BAA5B8CDABCB3A4B3CD Ở ÐÂY "4A" có nghĩa là "bốn chữ A" Chú ý là không đáng để mã hoá các loạt chạy có độ dài 1 hoặc 2 vì cần đến hai kí tự để mã hoá. Ðối với các tập tin nhị phân một phiên bản được tinh chế của phương pháp này được dùng để thu được sự tiết kiệm ÐÁNG KỂ. Ý tưởng ở đây là lưu lại các độ dài loạt, tận dụng sự kiện các loạt chạy thay đổi giữa 0 và 1 để tránh phải lưu chính các số 0 và 1 đó. Ðiều này giả định rằng có một vài loạt chạy ngắn (Ta tiết kiệm các bit trên một loạt chạy chỉ khi độ dài của đường chạy là lớn hơn số bit cần để biễu diễn chính nó trong dạng nhị phân), nhưng khó có phương pháp mã hoá độ dài loạt nào hoạt động thật tốt trừ phi hầu hết các loạt chạy đều dài. Việc mã hoá độ dài loạt cần đến các biễu diễn riêng biệt cho tập tin và cho bản đã được mã hoá của nó, vì vậy nó không thể dùng cho mọi tập tin, điều này có thể hoàn toàn bất lợi, ví dụ, phương pháp nén tập tin kí tự đã được đề nghị ở trên sẽ không dùng được đối với các chuỗi kí tự có chứa số. Nếu những kí tự khác được sử dụng để mã hoá các số đếm, thì nó sẽ không làm việc với các chuỗi chứa các kí tự đó. Giả sử ta phải mã hoá bất kì kí tự nào từ một bảng chữ cái cố định bằng cách chỉ dùng các kí tự từ bảng chữ cái đó. Ðể minh hoạ, giả sử ta phải mã hoá bất kì một chuỗi nào từ một chữ cái đó, ta sẽ giả định rằng ta chỉ có 26 chữ cái trong bảng chữ cái (và cả khoảng trống) để làm việc. Ðể có thể dùng vài chữ cái để biểu diễn các số và các kí tự khác biểu diễn các phần tử của chuỗi sẽ được mã hoá, ta phải chọn một kí tự được gọi là kí tự "Escape". Mỗi một sự xuất hiện của kí tự đó báo hiệu rằng hai chữ cái tiếp theo sẽ tạo thành một cặp (số đếm, kí tự) với các số đếm được biểu diễn bằng cách dùng kí tự thứ i của bảng chữ cái để biểu diễn số i. Vì vậy, chuỗi ví dụ của chúng ta sẽ được biểu diễn như sau với Q được xem là các kí tự "Escape" QDABBBAABQHCDABCBAAAQDBCCCD Tổ hợp của kí tự "Escape", số đếm và một kí tự lặp lại được gọi là một dãy Escape. Chú ý rằng không đáng để mã hoá các đường chạy có chiều dài ít hơn bốn kí tự, vì ít nhất là cần đến ba kí tự để mã hoá bất kì một loạt chạy nào. Trong trường hợp bản thân kí tự "Escape" xuất hiện trong dãy kí tự cần mã hoá ta sử dụng một dãy "Escape" với số đếm là 0 (kí tự space) để biểu diễn kí tự "Escape". Như vậy trong trường hợp kí tự "Escape" xuất hiện nhiều thì có thể làm cho tập tin nén phình to hơn trước. Các loạt chạy dài có thể được cắt ra để mã hoá bằng nhiều dãy Escape, ví dụ, một loạt chạy gồm 51 chữ A sẽ được mã hoá như QZAQYA bằng cách dùng trên. 147
39. Phân tích thiết kế thuật toán Phương pháp mã hoá độ dài loạt thường được áp dụng cho các tập tin đồ hoạ bitmap vì ở đó thường có các mảng lớn cùng màu được biểu diễn dưới dạng bitmap là các chuỗi bit có đường chạy dài. Trên thực tế, nó được dùng trong các tập tin .PCX, .RLE. 2. Phương pháp mã hoá Huffman Các tập tin của máy tính được lưu dưới dạng các kí tự có chiều dài không đổi là 8 bits. Trong nhiều tập tin, xác suất xuất hiện các kí tự này là nhiều hơn các kí tự khác, từ đó ta thấy ngay rằng nếu chỉ dùng một vài bit để biểu diễn cho các kí tự có xác suất xuất hiện lớn và dùng nhiều bit hơn để biểu diễn cho các kí tự có xác suất xuất hiện nhỏ thì có thể tiết kiệm được độ dài tập tin một cách đáng kể. Ví dụ, để mã hoá một chuỗi như sau: "ABRACADABRA" Nếu mã hoá chuỗi trên trong dạng mã nhị phân 5 bit ta sẽ có dãy bit sau: 0000100010100100000100011000010010000001000101001000001 Ðể giải mã thông điệp này, chỉ đơn giản là đọc ra 5 bits ở từng thời điểm và chuyển đổi nó tương ứng với việc mã hoá nhị phân đã được định nghĩa ở trên. Trong mã chuẩn này, chữ D xuất hiện chỉ một lần sẽ cần số lượng bit giống chữ A xuất hiện nhiều lần. Ta có thể gán các chuỗi bit ngắn nhất cho các kí tự được dùng phổ biến nhất, giả sử ta gán: A là 0, B là 1, R là 01, C là 10 và D là 11 thì chuỗi trên được biễu diễn như sau: 0 1 01 0 10 0 11 0 1 01 0 Ví dụ này chỉ dùng 15 bits so với 55 bits như ở trên, nhưng nó không thực sự là một mã vì phải lệ thuộc vào khoảng trống để phân cách các kí tự. Nếu không có dấu phân cách thì ta không thể giải mã được thông điệp này. Ta cũng có thể chọn các từ mã sao cho thông điệp có thể được giải mã mà không cần dấu phân cách, ví dụ như: A là 11, B là 00, C là 010, D là 10 và R là 011, các từ mã này gọi là các từ mã có tính prefix (Không có từ mã nào là tiền tố của từ mã khác). Với các từ mã này ta có thể mã hoá thông điệp trên như sau: 1100011110101110110001111 Với chuỗi đã mã hoá này ta hoàn toàn có thể giải mã được mà không cần dấu phân cách. Nhưng bằng cách nào để tìm ra bảng mã một cách tốt nhất ? Vào năm 1952, D.Huffman đã phát minh ra một cách tổng quát để tìm ra bảng mã này một cách tốt nhất. - Bước đầu tiên trong việc xây dựng mã Huffman là đếm số lần xuất hiện của mỗi kí tự trong tập tin sẽ được mã hoá. - Bước tiếp theo là xây dựng một cây nhị phân với các tần số được chứa trong các nút. Hai nút có tấn số bé nhất được tìm thấy và một nút mới được tạo ra với hai nút con là các nút đó với giá trị tần số của nút mới bằng tổng tần suất của hai nút con. Tiếp theo hai nút mới với tần số nhỏ nhất lại được tìm thấy và một nút mới nữa lại được tao ra theo cách trên. Lặp lại như vậy cho đến khi tất cả các nút được tổ hợp thành một cây duy nhất. - Sau khi có cây nhị phân, bảng mã Huffman được phát sinh bằng cách thay thế các tần số ở nút đáy bằng các kí tự tương ứng. Ưu điểm của phương pháp mã hoá Huffman là đạt được hệ số nén cao (Hệ số nén tuỳ thuộc vào cấu trúc của các tập tin). Nhược điểm của phương pháp này là bên nhận muốn giải mã được thông điệp thì phải có một bảng mã giống như bảng mã ở bên gửi, do đó khi nén các tập tin bé hệ số nén không được cao. 3. Phương pháp nén LZW 148
40. Phân tích thiết kế thuật toán Phương pháp nén LZW được phát minh bởi Lempel - Zip và Welch. Nó hoạt động đựa trên một ý tưởng rất đơn giản là người mã hoá và người giải mã cùng xây dựng bản mã. Nguyên tắc hoạt động của nó như sau: - Một xâu kí tự là một tập hợp từ hai kí tự trở lên. - Nhớ tất cả các xâu kí tự đã gặp và gán cho nó một dấu hiệu (token) riêng. - Nếu lần sau gặp lại xâu kí tự đó, xâu kí tự sẽ được thay thế bằng dấu hiệu của nó. Phần quan trọng nhất của phương pháp nén này là phải tạo một mảng rất lớn dùng để lưu giữ các xâu kí tự đã gặp (Mảng này được gọi là "Từ điển"). Khi các byte dữ liệu cần nén được đem đến, chúng liền được giữ lại trong một bộ đệm chứa (Accumulator) và đem so sánh với các chuỗi đã có trong "từ điển". Nếu chuỗi dữ liệu trong bộ đệm chứa không có trong "từ điển" thì nó được bổ sung thêm vào "từ điển" và chỉ số của chuỗi ở trong "từ điển" chính là dấu hiệu của chuỗi. Nếu chuỗi trong bộ đệm chứa đã có trong "từ điển" thì dấu hiệu của chuỗi được đem ra thay cho chuỗi ở dòng dữ liệu ra. Có bốn qui tắc để thực hiên việc nén dữ liệu theo thuật toán LZW là: qui tắc 1: 256 dấu hiệu đầu tiên được dành cho các kí tự đơn (0 - 0ffh). qui tắc 2: Cố gắng so sánh với "từ điển" khi trong bộ đệm chứa đã có nhiều hơn hai kí tự. qui tắc 3: Các kí tự ở đầu vào (Nhận từ tập tin sẽ được nén) được bổ sung vào bộ đệm chứa đến khi chuỗi kí tự trong bộ đệm chứa không có trong "từ điển". qui tắc 4: Khi bộ đệm chứa có một chuỗi mà trong "từ điển" không có thì chuỗi trong bộ đệm chứa được đem vào "từ điển". Kí tự cuối cùng của chuỗi kí tự trong bộ đệm chứa phải ở lại trong bộ đệm chứa để tiếp tục tạo thành chuỗi mới. Ví dụ: Các bước để mã hoá chuỗi "!BAN!BA!BAA!BAR!" như sau (Bảng 4. 1): - bước 1: Kí tự thứ nhất ‘!’ được cất vào bộ đệm chứa để chuẩn bị tạo nên một chuỗi. - bước 2: Kí tự thứ hai ‘B’ nối thêm vào sau kí tự !. Vì trong "từ điển" chưa có chuỗi "!B" nên chuỗi này được thêm vào "từ điển" và được gán dấu hiệu là 100h (Vì từ 000h đến 0ffh được dành riêng cho các kí tự đơn: Qui tắc 1). ‘!’ được gửi ra còn ‘B’ phải ở lại trong bộ đệm chứa. 149
41. Phân tích thiết kế thuật toán bước 3: Kí tự thứ ba ‘A’ thêm vào sau ‘B’. Chuỗi "BA" cũng chưa có trong "từ điển" nên nó được thêm vào "từ điển" và gán dấu hiệu là 101h. ‘A’ ở lại trong bộ đệm chứa còn ‘B’ được gửi ra. - bước 4: Kí tự thứ tư ‘N’ thêm vào sau ‘A’ tạo thành chuỗi "AN" cũng chưa có trong "từ 150
42. Phân tích thiết kế thuật toán điển" nên được thêm vào "từ điển" và có dâu hiệu là 102h. ‘N’ ở lại trong bộ đệm chứa còn ‘A’ được gửi ra. - bước 5: Kí tự thứ năm ‘!’ thêm vào sau ‘N’ để tạo thành chuỗi "N!", "N!" được thêm vào "từ điển" với dấu hiệu là 103h. ‘!’ ở lại còn ‘N’ được gửi ra. - bước 6: Kí tự thứ sáu ‘B’ thêm vào sau ‘!’. Lần này thì chuỗi "B!" đã có trong "từ điển" nên không có kí tự nào được gửi ra. "B!" tiếp tục ở lại trong "từ điển" để tạo ra chuỗi mới. - bước 7: Kí tự thứ bảy ‘A’ thêm vào sau ‘B’ để tạo thành chuỗi "B!A", do "B!A" không có trong "từ điển" nên nó được thêm vào "từ điển" và gán dấu hiệu là 104h đồng thời dấu hiệu 100h được gửi ra thay cho "B!" (Qui tắc 4). A tiếp tục ở lại trong bộ đệm chứa để tạo thành chuỗi mới. Các bước trên cứ thế tiếp tục cho đến khi hết tập tin cần nén. Việc giảm kích thước chỉ thực sự bắt đầu tại bước 7 khi mà một dấu hiệu 12 bits là được gửi ra thay cho hai byte "B!". Trong thuật toán nén này, phần lớn thời gian khi bắt đầu nén chủ yếu mất vào việc tạo "từ điển". Khi "từ điển" đủ lớn, xác suất gặp chuỗi ở bộ đệm chứa trong "từ điển" tăng lên và càng nén được nhiều hơn. Một điều cần chú ý ở đây là mỗi một dấu hiệu, ta phải lưu một chuỗi trong "từ điển" để so sánh. Vì dấu hiệu được biểu diễn bằng một số 12 bits nên "từ điển" sẽ có 4096 lối vào, khi tăng số bit dể biễu diễn dấu hiệu lên thì hiệu quả nén sẽ tốt hơn nhưng lại bị giới hạn bởi bộ nhớ của máy tính. Vì dụ, khi dùng 16 bits để biểu diễn một dấu hiệu thì "từ điển" phải có đến 65536 lối vào, nếu mỗi lối vào có khoảng 20 kí tự thì "từ điển" phải lớn khoảng 1,2 MB. Với một từ điển có dung lượng như vậy rất khó có thể thực hiện trên các máy tính PC hoạt động dưới hệ điều hành DOS vì giới hạn của một đoạn (Segment) là 64KB. Ưu điểm của phương pháp nén LZW là bên nhận có thể tự xây dựng bảng mã mà không cần bên gửi phải gửi kèm theo bản tin nén. 3. Chọn phương pháp nén Qua ba phương pháp nén được dùng phổ biến trên, ta thấy rằng, thuật toán nén độ dài loạt (Runlength) không thể áp dụng cho mhiều loại tập tin được, ví dụ như tập tin chương trình, tập tin cơ sở dữ liệu vì ở đó các loạt chạy là rất ngắn, do đó nếu áp dụng thuật toán này không những không làm bé tập tin mà còn làm phình to chúng. Hai thuật toán còn lại (Huffman và LZW) đều có thể áp dụng được để nén nhiều loại tập tin trên các máy vi tính. Thuật toán Huffman có ưu điểm là hệ số nén tương đối cao, phương pháp thực hiện tương đối đơn giản, đòi hỏi ít bộ nhớ, có thể xây dựng dựa trên các mảng bé hơn 64KB. Nhược điểm của nó là phải chứa cả bảng mã vào tập tin nén thì phía nhận mới có thể giải mã được do đó hiệu suất nén chỉ cao khi ta thực hiện nén các tập tin lớn. Thuật toán nén LZW có các ưu điểm là hệ số nén tương đối cao, trong tập tin nén không cần phải chứa bảng mã. Nhược điểm của thuật toán này là tốn nhiều bộ nhớ, khó thực hiện dựa trên các mảng đơn giản (bé hơn 64KB). 151
43. Phân tích thiết kế thuật toán Từ các ưu và nhược điểm trên, ta chọn phương pháp nén Huffman vì tính đơn giản của nó hệ số nén lại cao. Nhược điểm của phương pháp nén này có thể khắc phục bằng cách thực hiện nén một lần nhiều tập tin chuẩn bị truyền, làm như vậy coi như chúng ta đang thực hiện nén một tập tin lớn. 7.7 Kỹ thuật nén dùng mã Huffman Dẫn nhập Mã tiền tố (prefix-free binary code) Để mã hóa các kí hiệu (kí tự, chữ số, ) ta thay chúng bằng các xâu nhị phân, được gọi là từ mã của kí hiệu đó. Chẳng hạn bộ mã ASCII, mã hóa cho 256 kí hiệu là biểu diễn nhị phân của các số từ 0 đến 255, mỗi từ mã gồm 8 bít. Trong ASCII từ mã của kí tự "a" là 1100001, của kí tự "A" là 1000001. Trong cách mã hóa này các từ mã của tất cả 256 kí hiệu có độ dài bằng nhau (mỗi từ mã 8 bít). Nó được gọi là mã hóa với độ dài không đổi. Khi mã hóa một tài liệu có thể không sử dụng đến tất cả 256 kí hiệu. Hơn nữa trong tài liệu chữ cái "a" chỉ có thể xuất hiện 1000000 lần còn chữ cái "A" có thể chỉ xuất hiện 2, 3 lần. Như vậy ta có thể không cần dùng đủ 8 bít để mã hóa cho một ký hiệu, hơn nữa độ dài (số bít) dành cho mỗi kí hiệu có thể khác nhau, kí hiệu nào xuất hiện nhiều lần thì nên dùng số bít ít, ký hiệu nào xuất hiện ít thì có thể mã hóa bằng từ mã dài hơn. Như vậy ta có việc mã hóa với độ dài thay đổi. Tuy nhiên, nếu mã hóa với độ dài thay đổi, khi giải mã ta làm thế nào phân biệt được xâu bít nào là mã hóa của ký hiệu nào. Một trong các giải pháp là dùng các dấu phẩy (",") hoặc một kí hiệu quy ước nào đó để tách từ mã của các kí tự đứng cạnh nhau. Nhưng như thế số các dấu phẩy sẽ chiếm một không gian đáng kể trong bản mã. Một cách giải quyết khác dẫn đến khái niệm mã tiền tố Mã tiền tố là bộ các từ mã của một tập hợp các kí hiệu sao cho từ mã của mỗi ký hiệu không là tiền tố (phần đầu) của từ mã một ký hiệu khác trong bộ mã ấy. Đương nhiên mã hóa với độ dài không đổi là mã tiền tố. Ví dụ: Giả sử mã hóa từ "ARRAY", tập các ký hiệu cần mã hóa gồm 3 chữ cái "A","R","Y". Nếu mã hóa bằng các từ mã có độ dài bằng nhau ta dùng ít nhất 2 bit cho một chữ cái chẳng hạn "A"=00, "R"=01, "Y"=10. Khi đó mã hóa của cả từ là 0001010010. Để giải mã ta đọc hai bit một và đối chiếu với bảng mã. Nếu mã hóa "A"=0, "R"=01, "Y"=11 thì bộ từ mã này không là mã tiền tố ví từ mã của "A" là tiền tố của từ mã của "R". Để mã hóa cả từ ARRAY phải đặt dấu ngăn cách vào giữa các từ mã 0,01,01,0,11 Nếu mã hóa "A"=0, "R"=10, "Y"=11 thì bộ mã này là mã tiền tố. Với bộ mã tiền tố này khi mã hóa xâu "ARRAY" ta có 01010011. Biểu diễn mã tiền tố trên cây nhị phân Nếu có một cây nhị phân n lá ta có thể tạo một bộ mã tiền tố cho n ký hiệu bằng cách đặt mỗi ký hiệu vào một lá. Từ mã của mỗi kí hiệu được được tạo ra khi đi từ gốc tới lá chứa ký hiệu đó, nếu đi qua cạnh trái thì ta thêm số 0, đi qua cạnh phải thì thêm số 1. Ví dụ: Cây 3 lá sau đây biểu diễn bộ mã của A,R,Y trong ví dụ trên * 0/ \1 A * 0/ \1 R Y Từ mã của "A" là 0, của "R" là 10, của "Y" là 11. Mã tiền tố tối ưu Từ ví dụ trên thấy mã hóa của xâu "ARRAY" bằng mã độ dài cố định mất 10 bít, bằng mã tiền tố đã đưa ra mất 8 bít, tiết kiệm được 20%. Bài toán đặt ra là bộ mã tiền tố đã tối ưu chưa.OK Bài toán 152
44. Phân tích thiết kế thuật toán Cho tập A các ký hiệu và trọng số (tần suất)của chúng. Tìm một bộ mã tiền tố với tổng độ dài mã hóa là nhỏ nhất. Dữ liệu Input Bảng n chữ cái . Tập các trọng số (tần suất xuất hiện) tương ứng , i.e. . Output Bộ mã , là tập hợp các từ mã (codeword) (nhị phân), trong đó ci là từ mã của . Yêu cầu Đặt là trọng số của bộ mã C. Điều kiện là: với mọi bộ mã . Ví dụ Trong ví dụ sau, với các tần số như trên mã 1 sẽ tốn không gian hơn mã 2. Ký tự a b c d e Input tần suất 0.10 0.15 0.30 0.16 0.29 1,00 Từ mã 000 001 010 011 110 Mã 1 Độ dài từ mã (bits) 3 3 3 3 3 3,00 Từ mã 000 001 10 01 11 Mã 2 Độ dài từ mã (bits) 3 3 2 2 2 2,25 Giải thuật Giải thuật tham lam Trong giải thuật tham lam giải bài toán xây dựng cây mã tiền tố tối ưu của Huffman, ở mỗi bước ta chọn hai chữ cái có tần số thấp nhất để mã hóa bằng từ mã dài nhất. Giả sử có tập A gồm n ký hiệu và hàm trọng số tương ứng W(i),i = 1 n. Khởi tạo: Tạo một rừng gồm n cây, mỗi cây chỉ có một nút gốc, mỗi nút gốc tương ứng với một kí tự và có trọng số là tần số/tần suát của kí tự đó W(i). Lăp: o Mỗi bước sau thực hiện cho đến khi rừng chỉ còn một cây: o Chọn hai cây có trong số ở gốc nhỏ nhất hợp thành một cây bằng cách thêm một gốc mới nối với hai gốc đã chọn. Trọng số của gốc mới bằng tổng trọng số của hai gốc tạo thành nó. Như vậy ở mỗi bước số cây bớt đi một. Khi rừng chỉ còn một cây thì cây đó biểu diễn mã tiền tố tối ưu với các ký tự đặt ở các lá tương ứng. Ví dụ Cho bảng tần suất của 5 chữ cái A,B,C,D,E như sau tương ứng là 0.10; 0.15; 0.30; 0.16; 0.29 A B C D E 0.10 0.15 0.30 0.16 0.29 Quá trình xây dựng cây Huffman diễn ra như sau 153
45. Phân tích thiết kế thuật toán Như vậy bộ mã tối ưu tương ứng là A B C D E 010 011 11 00 10 Hàng đợi có ưu tiên Trong mỗi bước của thuật toán xây dựng cây Huffman, ta luôn phải chọn ra hai gốc có trọng số nhỏ nhất. Để làm việc này ta sắp xếp các gốc vào một hàng đợi ưu tiên theo tiêu chuẩn trọng số nhỏ nhất. Một trong các cấu trúc dữ liệu thuận lợi cho tiêu chuẩn này là cấu trúc Heap (với phần tử có trọng số nhỏ nhất nằm trên đỉnh của Heap). .26. Giả mã Trong đoạn giả mã này ta dựa trên một mảng các ký hiệu A[1 n] có tần suất tương ứng là W[1 n] .26.1 Tạo hàng đợi bằng đống (heap) Ta tạo một đống trên cơ sở sắp xếp lại các chỉ số của A và W. Ta lưu trữ đống dưới dạng mảng, kí hiệu nó là Heap[1 n]. Trước hết đưa chỉ số của các chữ cái theo thứ tự ban đầu vào mảng Heap[1 n] với Heap[i]=i . với mọi i=1 n. Procedure DownHeap(List W,Int k,Count) { Int i:=k, v:=W(Heap(k)), j While 2*i W(Heap(j)) then j:=j+1 if W(Heap(j))< v then Heap(i):=Heap(j) else break i:=j } } Heap(j):=Heap(k) Procedure MakeHeap(List W,n) { Int k 154
46. Phân tích thiết kế thuật toán For k:=int(n/2) downto 1 { DownHeap (W,k,n) } Xây dựng cây Huffman Ta sẽ lưu trữ cấu trúc của cây mã Huffman vào một mảng. Cây Huffman gồm n lá mỗi lá chứa chỉ số của chữ cái tương ứng. Mỗi lần ghép 2 cây thành một ta phải thêm một đỉnh, như vậy cây biểu diễn mã Huffman gồm 2.n-1 đỉnh. Ta kí hiệu cây này là Huff[1 2n-1]. Vì mỗi gốc mới bổ sung đều có trọng số nên ta mở rộng mảng W[1 n] các trọng số thành mảng W' [1 2n+1]. Gọi m là số đỉnh của cây sẽ xây dựng. lúc đầu ta có n lá, đỉnh bổ sung lần đầu sẽ là n+1, lần thứ 2 là n+2, Khi lấy ra hai kí tự có tần số nhỏ nhất chẳng hạn kí tự thứ i làm con trái và kí tự thứ j làm con phải của đỉnh mới bổ sung có chỉ số m ta đặt Huff[i]=-m, Huff[j]=m. Procedure MakeTreeHuffman(List W,Int n) { List Heap,Huff Int i,j,count:=n,m:=n MakeHeap(W) While Count >1 { i:=Heap(1) Heap(1):= Heap(count) Count:=Count-1 DownHeap(W,1,Count) j:=Heap(1) m:=m+1 Huff(i):=-m Huff(j):=m W(m):=W(i)+W(j) Heap(1):=m DownHeap(W,1,Count) } Return Huff } .26.2 Xây dựng bộ mã Sau khi cấu trúc của cây Huffman được lưu vào mảng Huff ta dễ dàng xây dựng mảng Code[1 n] cho bộ mã nhị phân tiền tố tối ưu của các kí tự A[1 n] Procedure CodingHuffman(List Huff, n){ Int k:=1,j While k 0 then Code(k)="1"+Code(k) else Code(k)="0"+Code(k) j:=Huff(j) } k:=k+1 } Return Code 155
47. Phân tích thiết kế thuật toán } 7.8 Kỹ thuật nén Lampel - Ziv Thực ra thì không phải cứ dữ liệu multimedia là người ta dùng phương pháp nén có hao hụt, ví dụ như định dạng ảnh GIF lại dùng giải thuật nén LZW để nén nhưng như đã nói ở trên LZW là nén bảo toàn nên cũng dùng “từ điển” để nén (thực tế người ta gọi là bảng màu và tối đa của ảnh GIF bạn có thể lập bảng chưa 256 màu). Giải thuật Lempel-Ziv-Welch (LZW) và kỹ thuật mã hóa kiểu Huffman phân tích và quan sát các đoạn lặp lại. Nếu LZW hoặc Huffman thấy có đoạn 010101, chúng đủ thông minh đánh dấu các đoạn như vậy và thay bằng một ký tự, bằng cách đó dữ liệu được nén lại. Do những giới hạn đó, người ta đã đưa ra định dạng mới trong nén ảnh đó là JPEG (viết tắt của Joint Photographic Expert Group - tổ chức sáng lập ra chuẩn này). Trên thực tế JPEG có cả hai định dạng là lossless compression và lossy compression nhưng hầu như không ai chấp nhận định dạng lossless compression cả do chất lượng ảnh thì quả là giữ nguyên được thật nhưng dung lượng thì không hề giảm. Trong khi đó dạng lossy compression của JPEG lại cho ta được kết quả tuyệt vời, tỉ số nén dao động từ 1:1 (lossless compression) cho tới 100:1 (tối đa), tất nhiên để có được tỉ số nén càng cao chúng ta càng phải hy sinh chất lượng của ảnh. Thường thì theo những người có kinh nghiệm, tỉ sô nén 10:1 là đem lại kết quả hoàn mỹ nhất. Nén theo chuẩn JPEG là một tiến trình nhiều bước. Trước hết là bước qui tắc hóa (regularizing stage) để làm cho ảnh có nhiều đoạn giống nhau hơn thực tế. Ảnh màu được chuyển sang dạng YUV hoặc CIELAB, trong đó thông tin về độ sáng (luminance) được tách rời với thông tin về độ màu (chrominance). Một yếu tố được tính tới là mắt người ta nhạy cảm với những thay đổi nhỏ về độ sáng hơn là những thay đổi về màu sắc, đặc biệt ở đầu xanh của phổ màu. Ngoài ra cách làm này còn khai thác thực tế là ảnh thường có nhiều vùng lớn tại đó các điểm kế nhau rất giống nhau về kênh màu. Bước tiếp theo là lấy mẫu cho các kênh màu. Ðây là 1 trong 2 công đoạn làm mất thông tin và chỉ thực hiện khi bạn chọn xác lập high compression/low quality (tỉ lệ nén cao/chất lượng thấp) của JPEG. Lấy mẫu (subsampling) nghĩa là loại bỏ có hệ thống các thông tin màu sắc đối với các hàng hoặc cột điểm ở tỉ lệ cho trước. Nếu bạn thực hiện cứ hai hàng loại bỏ một hàng và hai cột loại bỏ một cột, bạn giảm được dữ liệu màu đi 75%. Khi giải nén ảnh, giá trị của các điểm loại bỏ trước đó được ngoại suy từ những gì còn lại. Bước tiếp là sắp xếp lại dữ liệu bằng hàm toán học gọi là DCT (Discrete Cosine Transform). Làm việc với các khối điểm 8x8 pixel, hàm DCT phân tích các tần số vùng theo cả chiều ngang lẫn chiều dọc. Công đoạn này được gọi là lượng tử hóa (quantization) - cách gọi kỹ thuật của bước làm giảm số bit cần thiết để biểu diễn mổi giá trị tần suất. Các giá trị này được nén trung thực trước hết bằng RLE sau đó mã hóa theo kỹ thuật Huffman. Ðây là công đoạn của JPEG cho phép đạt tỉ số nén rất cao. 156
48. Phân tích thiết kế thuật toán Quá trình giải nén (decompression) là quá trình ngược lại. Dữ liệu được giải mã bằng thuật toán Huffman, các giá trị kết quả được nhân lên, hàm DCT ngược được áp dụng, các vùng luminance và chrominance được chuyển trở lại RGB để trơ lại ảnh bitmap (Ảnh được lưu theo dạng ánh xạ bit). Cũng tương tự như JPEG, giải thật nén tương tự được áp dụng cho định dạng MPEG (Layer 1,2,3 và 4) giúp giảm kích thước các laọi phim ảnh (MPEG Layer 1,2 và 4) và âm thanh (MPEG Layer 3). Sau đây là ví dụ về mã giải của quá trình nén theo gải thuật Huffman: WHILE (there are more characters) { code=HuffCode[character].code ; get huffman code size=HuffCode[character].size ; get code size i=size WHILE(i) {sendbit(code) ; send MSB of code I<<1 ; select next bit i ; increment # bits sent } ENDWHILE } ENDWHILE Còn đây là mã giả cho quá trình giải nén của thuật Huffman : TreeNode=RootNode Repeat Until at a leaf { TreeNode=Tree.right ; assume right child branch if (inputbit==0) TreeNode=Tree.left ; if 0, traverse left child branch } Output(TreeNode); Flowchart của giải thuật nén LZW 157
49. Phân tích thiết kế thuật toán 158
50. Phân tích thiết kế thuật toán Resource : Sample Chapte : Data compression : www.dspguide.com/datacomp.htm Data compression : Theory of Data Compression : Lossless Data Compression : Define : Compression : 159
51. Phân tích thiết kế thuật toán BÀI 8: LỚP BÀI TOÁN NP ĐẦY ĐỦ MÃ BÀI ITPRG3_12.8 8.1 Các khái niệm cơ bản Năm 1971, Stephen Cook chứng minh rằng có các vấn đề trong lớp NP mà tất cả các vấn đề khác trong NP có thể chuyển giản (reduced) về được trong thời gian đa thức. Phép chuyển giản này có thể được mô tả đại khái như sau: nếu vấn đề A có thể chuyển giản được về vấn đề B trong thời gian đa thức, thì nếu ta giải được B trong thời gian đa thức ta sẽ giải được A trong thời gian đa thức. Theo nghĩa thời gian đa thức thì vấn đề B khó hơn hoặc bằng A. Vì thế, các vấn đề mà Cook đề cập là các vấn đề khó nhất trong lớp NP. Các vấn đề này gọi là các vấn đề NP-đầy đủ. Cook chứng minh rằng sat, 3-sat, và subgraph isomorphism là NP-đầy đủ . Có ba khả năng trả lời câu hỏi P chọi NP: (a) P = NP, (b) P chọi NP không quyết định được, nghĩa là độc lập với hệ thống, (c) P = NP hoặc P khác NP tùy theo ta chọn hệ tiên đề nào (tương tự như continuum hypothesis), và (d) P khác NP. Nếu (a) đúng thì cả chục nghìn vấn đề NP-đầy đủ có giải thuật đa thức để giải, mật mã khóa công cộng (public key cryptography) là vô vọng, vân vân. Các giao thức (protocol) bảo mật trên Internet hiện nay đều ít nhiều dựa vào mật mã khóa công cộng, nếu P = NP thì các giao dịch tiền tệ trên Internet đều cực kỳ bất ổn. Nếu P = NP thì hàng nghìn hàng vạn các nhà khoa học, toán học, kỹ sư máy tính trong hơn năm chục năm qua đã bỏ qua một ý tưởng căn bản nào đó có thể giải một trong số cả chục nghìn bài toán NP-đầy đủ. Chuyện này quá hy hữu. Vì thế, khả năng (a) rất khó xảy ra. Các khả năng (b) và (c) liên quan đến trạng thái logic của vấn đề (thay vì tính thuật toán của nó). Scott Aaronson có một bài báo tổng quan rất hay, thảo luận các khả năng này. Kết luận chung là các khả năng này rất khó xảy ra. Một tham khảo thú vị là nghiên cứu của Razborov và Rudich năm 1993, trong đó các tác giả đưa bằng chứng cho thấy: “có lẽ lý do mà chứng minh P != NP rất khó là tại vì P != NP !!!” Như vậy, khả năng cuối cùng là P != NP, và đa số khoa học gia đều tin vào khả năng này. Thế ta phải làm gì nếu P thật sự khác NP? Ta thử liệt kê vài hướng đi hiện nay: Có lẽ mô hình máy Turing không phải là mô hình tính toán mạnh nhất. Điều này có nghĩa là ta phải thiết kế các máy tính theo kiểu khác, dựa trên một nguyên tắc hoàn toàn khác với nguyên tắc thiết kế hiện tại (với bộ vi xử lý, bộ nhớ, bus, thiết bị ngoại vi, vân vân). Đã có vài đề cử, trong đó quan trọng nhất là tính toán lượng tử (quantum computing, và tính toán sinh học (biological computing) . Công trình đột phá của Peter Shor cho thấy ta có thể phân tích một số nguyên ra thừa số (factorization) trong thời gian đa thức với một máy tính lượng tử. Bài toán này là một trong số rất ít các bài toán trong NP mà ta không biết là nó ở trong P hay là NP-đầy đủ. Ngoài bài 160
52. Phân tích thiết kế thuật toán báo của Peter Shor, thật sự vẫn chưa có bằng chứng nào ủng hộ khả năng là ta có thể giải các bài toán NP-đầy đủ trong thời gian đa thức với máy tính lượng tử. Tình hình với máy tính sinh học còn tệ hơn. Trong hướng đi thứ hai, ta chấp nhận rằng các bài toán NP-đầy đủ không thể giải được nhanh bằng các máy tính vật lý (bất kể mô hình vật lý nào). Đến đây thì có vài nhánh nghiên cứu khác: Tìm cách hiệu quả nhất (dù là trong thời gian không đa thức) để giải các bài toán này. Các nghiên cứu về quy hoạch nguyên (integer programming) là một ví dụ tốt. Trong thời gian đa thức, tìm lời giải càng gần tối ưu càng tốt. Đây là hướng đi của các giải thuất xấp xỉ (approximation algorithms), một hướng rất quan trọng trong khoa học máy tính hiện đại. Một hướng khác cũng quan trọng không kém là dùng các giải thuật ngẫu nhiên hóa (randomized algorithms). Ta có thể tìm lời giải tối ưu trong thời gian kỳ vọng là đa thức (expected polynomial time), hoặc tìm lời giải với giá kỳ vọng (expected cost) gần tối ưu trong thời gian đa thức. Tất cả các khả năng và hướng đi trên đưa chúng ta đến các phương trời mới của khoa học máy tính, toán học và vật lý, là các bước tiến quan trọng cho quá trình tìm hiểu vũ trụ và các quy luật hoạt động của tự nhiên (trong đó tính toán là một quá trình căn bản). Giới thiệu bài toán Bài toán xếp lịch có một lịch sử phát triển dài, trải qua nhiều sự thay đổi lớn. Kể từ những thế hệ đầu tiên của máy tính,người ta đã nghĩ đến việc sử dụng máy tính để trợ giúp người xếp lịch. Ban đầu đó chỉ là những công cụ trợ giúp cho việc phân công những công việc điều hành phối hợp. Sau này mới thực sự được phát triển thành những công cụ xếp lịch cụ thể. Bài toán xếp lịch được chia thành những lớp bài toán cụ thể sau: - Xếp thời khoá biểu. Thường được sử dụng trong các trường Phổ thông, Đại học. - Xếp lịch thi. Được quan tâm mỗi khi kì thi tuyển sinh Đại học hoặc thi học kì ở các trường Đại học và Cao đẳng. - Xếp lịch công tác cán bộ. Được sử dụng chủ yếu ở các cơ quan, tổ chức lớn. Tuy nhiên trong bài báo này chúng ta chỉ quan tâm đến bài toán xếp lịch thi trong các trường Đại 161
53. Phân tích thiết kế thuật toán học. Phát biểu bài toán Bài toán được phát biểu như sau: Vào cuối mỗi một học kì, các trường đại học phải tổ chức một đợt thi cho từng khoa hoặc cả trường. Trường có một nhiều phòng thi, các phòng có kích cỡ khác nhau (khả năng chứa thí sinh). Mỗi lớp có thể được chia thành nhiều nhóm thi, mỗi nhóm thi thi trong một phòng, mỗi phòng có thể có nhiều nhóm cùng thi. Và tổng số lượng thí sinh của các nhóm phải nhỏ hơn hoặc bằng kích cỡ của phòng. Kì thi được chia thành các đợt thi. Mỗi nhóm sẽ thi một môn trong một đợt thi. Yêu cầu chặt chẽ: có một số môn thi không được thi cùng đợt với môn thi khác, các nhóm của cùng một lớp (nếu có thể) phải thi trong cùng một đợt. Ta có thể chia bài toán trên thành 2 bài toán đơn giản hơn: - Phân bổ các nhóm thi vào các đợt thi sao cho chúng không xung đột nhau (không vi phạm ràng buộc). Xây dựng một đồ thị G, với mỗi đỉnh là một nhóm, nối cạnh giữa hai đỉnh mà nhóm của chúng có ràng buộc với nhau, tìm cách tô màu và sắc số p của đồ thị G. Số p là giới hạn dưới của số các đợt thi. Các đỉnh được tô cùng màu có nhóm tương ứng được xếp vào một đợt thi. - Tìm cách xếp các nhóm trong một đợt thi (đã tìm được ở trên) vào các phòng thi của trường. Bài toán tô màu đồ thị và sắc số đồ thị Cho trước một số nguyên dương P, ta nói rằng đồ thị G có P sắc có nghĩa là: chỉ bằng P màu khác nhau ta có thể tô màu tất cả các đỉnh sao cho 2 đỉnh liền kề bất kỳ có màu khác nhau. Khi số p nhỏ nhất thì ta gọi P là sắc số của đồ thị và việc tìm cách tô P màu lên đồ thị chính là bài toán tô màu đồ thị. 162
54. Phân tích thiết kế thuật toán Ví dụ: Việc tô màu bản đồ hành chính, ta phải tô màu các nước sao cho: mỗi Quốc gia được tô một màu, hai nước có liền kề (có chung biên giới) không được tô cùng một màu. Ta thiết lập một đồ thị G, có tập các đỉnh là tập tất cả các quốc gia trên bản đồ. Hai nước liền kề nhau thì có cạnh nối hai đỉnh tương ứng với nhau. Ta tiến hành tìm sắc số của đồ thị này. Đây là trường hợp riêng của bài toán tô màu đồ thị. Khi đồ thị chỉ là đồ thị phẳng. Người ta đã chứng minh được rằng: chỉ cần nhiều nhất là 4 màu để tô đồ thị này. Từ lâu người ta đã chứng minh bài toán tô màu đồ thị thuộc lớp NP - đầy đủ. Tuy nhiên nếu dùng một chiến thuật thuật hợp lý thì kết quả thu được cũng có thể chấp nhận được. Thuật toán tìm sắc số của đồ thị (Thuật toán 1): Giả sử chúng ta có một đồ thị chứa các đỉnh x và y. G: xy là một đồ thị thu được từ đồ thị G bằng cách thay thế hai đỉnh x và y bằng một đỉnh, đỉnh đó có cạnh nối tới tất cả các đỉnh kề với đỉnh x, y hoặc cả x lẫn y. Hay là hai đỉnh x và y đã được nhập với nhau. Đồ thị G - {x} là một đồ thị thu được từ đồ thị G bằng cách loại bỏ đỉnh x cùng với tất cả các cạnh nối tới đỉnh x đó. Một đồ thị trống là đồ thị không chứa một đỉnh hay một cạnh nào. Hai đỉnh gọi là kề nhau nếu có cạnh nối với nhau. Với một đỉnh x bất kỳ, ta xây dựng một tập các bộ 3 như sau: Code: (x, z(1,1), y1) (x, z(1,2), y1) (x, z(1,m1), y1) (x, z(i,1), yi) (x, z(i,2), yi) (x, z(i,mi), yi) 163
55. Phân tích thiết kế thuật toán (x, z(n,mn), yn) Trong đó đỉnh thứ nhất kề với đỉnh thứ hai, đỉnh thứ 2 kề với đỉnh thứ 3. Và không tồn tại một bộ 3 nào mà: đỉnh thứ nhất kề hoặc trùng với đỉnh thứ 3. Từ tập các bộ 3 đó, ta tìm các đỉnh yi sao cho có: mi = max(m1, m2, , mn) và đặt yi = x. Nếu có nhiều đỉnh y đạt max ta chọn đỉnh đầu tiên. Ta có thể hình dung: Chọn một đỉnh trong số những đỉnh không kề với đỉnh x, kề với đỉnh (đỉnh trung gian) kề với đỉnh x, có số đỉnh trung gian là lớn nhất. Các bước của thuật toán (đồ thị G là dữ liệu vào): Bước 1: Đặt j = 1, H=G. Bước 2: Đặt vj là đỉnh có bậc cao nhất trong H. Bước 3: Từ vj xây dựng tất cả các bộ 3 như trên và tìm đỉnh x. Nếu không tìm được x, trong trường hợp không tìm được bộ 3 nào, chọn một đỉnh có bậc lớn nhất không kề với vj. Bước 4: Nhập x vào vj và quay lại bước 3 cho tới khi không chọn được một đỉnh nào nữa thì quay lại bước 2 với : H=H-{vj}, j=j+1. Bước 5: Khi không còn một đỉnh nào còn lại trong H, dựng lại và tô màu i cho tất cả các đỉnh được nhập vào vi với (1 =< i =< j). Khi đó j là sắc số của đồ thị G. Cài đặt: Dữ liệu: Mảng hai chiều M chứa ma trận thể hiện đồ thị n đỉnh. Mảng 1 chiều n phần tử: Color đánh dấu màu của đỉnh i là Color[i]. Mảng 1 chiều n phần tử: Merged, Merged[i]=true nếu đỉnh i đã bị nhập vào 1 đỉnh khác. Sắc số của đồ thị: Cromatic. 164
56. Phân tích thiết kế thuật toán Một số thủ tục và hàm sử dụng trong chương trình: Procedure Input; Nhập ma trận thể hiện đồ thị G từ file. Procedure Output; Xuất mảng Color[i] là màu của đỉnh i ra file. Function Degree(x:byte):byte; Tính bậc của đỉnh x, bậc của đỉnh x là số đỉnh chưa bị nhập vào đỉnh khác (hay Merge[i]=false) có cạnh nối với x (M[x,i]=true). Function MaxDegree:byte; Trả lại đỉnh chưa được tô màu (Color[i]=0) và có bậc lớn nhất (Degree(i) * Max). Function NumIntermediate(x,y:byte):byte; Trả về số đỉnh trung gian giữa hai đỉnh x và y (Đỉnh i là trung gian của x và y (i y; Merged[i]=false; M[x,i]=true và M[i,y]=True) Function MaxIntermediate(x:byte):byte; Trả về đỉnh có số đỉnh trung gian với đỉnh x là lớn nhất. NumIntermediate(x,I) * Max. Function Merge(i,x:byte); Nhập đỉnh I vào đỉnh x. Tìm tất cả các đỉnh chưa nhập vào đỉnh nào có cạnh nối với đỉnh i (Merged[j]=false; M[i,j]=true), nối đỉnh đó với đỉnh x (M[j,x]:=true;M[x,j]:=true), xoá cạnh nối giữa đỉnh đó với đỉnh i (M[i,j]:=0;M[j,i]=0). Function NonMaxDegree(x:byte):byte; Tương tự như hàm MaxDegree, tìm đỉnh khác đỉnh x (i<>x), không có cạnh nối với x (M[i,x]=false) có bậc lớn nhất (Degree(i) * Max). Chương trình chính: Code: Procedure main; var ncol,m,i,mx:byte; Begin input; ncol:=0;{Đặt màu ban đầu bằng 0} 165
57. Phân tích thiết kế thuật toán m:=MaxDegree;{m là đỉnh có bậc lớn nhất} while(m 0) do begin Merge(mx,m);{Nhập mx vào m} color[mx]:=ncol; {Tô màu cho đỉnh mx, mx có cùng màu với đỉnh m} mx:=MaxIntermediate(m); if (mx=0) then mx:=Non_MaxDegree(m); {Tiếp tục tìm đỉnh mx như trên cho đến khi không còn tìm được nữa} end; m:=MaxDegree;{m là đỉnh có bậc lớn nhất trong đồ thị còn lại, nếu m=0 thì đồ thị đã rỗng và việc tô màu đã hoàn thành} end; Cromatic:=ncol;{Đặt sắc số của đồ thị là ncol} Ouput; End; 166
58. Phân tích thiết kế thuật toán Thuật toán trên không phải là một thuật toán tốt trong mọi trường hợp, nhưng nó cố gắng để tìm một giải pháp có thể chấp nhận được để tìm sắc số cho đồ thị. Ứng dụng thuật toán tô màu đồ thị Thuật toán xếp các nhóm thi vào các phòng thi (Thuật toán 2): Sắp xếp các nhóm thi tăng dần theo số lượng thí sinh trong nhóm e1, e2, , en. Kí hiệu |ei| là số lượng của nhóm ei. Tương tự sắp xếp các phòng theo thứ tự tăng dần theo kích cỡ R1, R2, , Rn. Kí hiệu |Ri| là độ lớn của phòng thi Ri. Bước 1: Đặt i=1 , j=1, D1=phi. Bước 2: Nếu |ei| =< |Rj| thì thêm ei vào Rj. Ngược lại đặt j=j+1, lặp lại Bước 2. Bước 3: Đặt k = j. Bước 4: Nếu ³ |Rk|, tìm tập các nhóm trong Rk sao cho tổng số số lượng của các nhóm lớn nhất, nhưng chứa được trong Rk hay. Nếu k=m đặt Di+1 = Di hợp {các nhóm còn lại} Ngược lại đặt chúng vào Rk+1, k = k+1, Di+1 = Di và lặp lại bước 4. Bước 5: Đặt i = i+1. Nếu i =< n, lặp lại bước 2. Thuật toán bắt đầu xếp lần lượt từ nhóm nhỏ nhất trong danh sách vào các phòng. Thuật toán đặt mỗi nhóm vào phòng nhỏ nhất có thể chứa nó. Nếu số lượng thí sinh trong phòng đó lớn hơn khả năng chứa của phòng, thuật toán sẽ đẩy một số ít thí sinh nhất lên phòng có kích thước lớn hơn. Nếu số phòng đã hết trong khi số nhóm vẫn còn, thì số nhóm đó sẽ được đặt trong tập DUD (tập 167
59. Phân tích thiết kế thuật toán Di ở vòng lặp cuối cùng), tập DUD chứa những nhóm không thể xếp vào các phòng trong đợt thi này. Cài đặt: Cấu trúc dữ liệu Mảng 1 chiều chứa kích thước của n nhóm đã được sắp xếp tăng dần: E, E[i] là số thí sinh trong nhóm i. Mảng 1 chiều chứa sức chứa của m phòng đã được sắp xếp tăng dần: R, R[i] là sức chứa của phòng i. Mảng 1 chiều xác định nhóm thuộc phòng: p, p[i] là chỉ số phòng mà nhóm i thuộc. P[i]=DUD=m+1 nếu phòng đó không được xếp vào một phòng nào cả. Các thủ tục và hàm sử dụng trong chương trình: procedure input; Nhập hai mảng E vả R, khởi tạo tất cả các phòng đều chưa được xếp (p[i]=0). Chú ý: phòng chưa được xếp khác với phòng không được xếp (p[i]=DUD) procedure output; Xuất mảng p thể hiện nhóm nào đã được xếp vào phòng nào. [code] procedure PushUp(k:byte; sum:integer);{Đẩy nhóm lên phòng có kích thước lớn hơn} var i:byte; Begin for i:=1 to n do if (p[i]=k) and (sum-e[i]<=r[k]) then {Tìm một nhóm thuộc phòng k sao cho nếu loại nhóm đó đi thì phòng đó chứa đủ số nhóm còn lại} begin if (k<m) then{Nếu chưa phải là phòng cuối cùng} p[i]:=k+1{đẩy nhóm lên phòng cao hơn} else p[i]:=DUD;{Không xếp phòng cho nhóm này, đẩy nhóm này vào tập DUD} break; end; End; [code] {Chú ý: ở đây ta chỉ xét việc đẩy 1 phòng ra, nếu muốn bạn có thể cài đặt đẩy số nhiều nhóm ra hơn sao cho tổng số thí sinh được đẩy ra là nhỏ nhất, càng ít thí sinh bị đẩy ra thì càng tốt} 168
60. Phân tích thiết kế thuật toán function SumK(k:byte):integer; Tính tổng số thí sinh trong phòng k. Chương trình chính: Code: procedure main; var i,j,k,t:byte; sum:integer; Begin Input; for i:=1 to n do {Bắt đầu từ nhóm có số thí sinh nhỏ nhất} begin for j:=1 to m do if (e[i] r[k]) do {Nếu số thí sinh lớn hơn khả năng chứa của phòng k} begin PushUp(k,sum);{Đẩy một số nhóm lên phòng có sức chứa lớn hơn} inc(k); sum:=SumK(k);{Làm tương tự đối với phòng trên} 169
61. Phân tích thiết kế thuật toán end; end; Ouput; end; Lập lịch thi theo hai thuật toán trên Hai thuật toán trên đã được xây dựng xong. Thuật toán thứ nhất dùng để phân chia các nhóm thành những tập hợp độc lập với nhau. Thuật toán thứ hai sẽ xếp các tập đó vào các phòng thích hợp. Ta có thể sử dụng cả hai thuật toán để được một công cụ xếp lịch thi tương đối tốt. Cho một số phòng thi, cho các nhóm thi và các ràng buộc của chúng được thể hiện trên đồ thị G. Mỗi nhóm là một đỉnh của đồ thị, hai đỉnh có cạnh nối với nhau nếu hai nhóm tương ứng xung đột nhau. Đồ thị G là dữ liệu vào. Bước 1: Đặt p = 1. Bước 2: Dùng thuật toán 1 để tìm ra một tập các nhóm không xung đột với nhau, tập I. Bước 3: Từ tập I, sử dụng thuật toán 2 để đặt mỗi nhóm trong I vào phòng thích hợp. Những nhóm chưa được xếp (nằm trong DUD) sẽ được xếp trong đợt thi sau. Bước 4: Đặt p = p+1. Bước 5: Xoá tất cả các đỉnh (và các cạnh nối đến chúng) trong I trừ các đỉnh có nhóm tương ứng nằm trong DUD, ta có đồ thị G’. Nếu G’ là một đồ thị rỗng, việc xếp thời khoá biểu hoàn thành. Bước 6: Bắt đầu với từ đỉnh được nhập bởi nhiều đỉnh mà nhóm tương ứng có trong DUD. Nếu DUD rỗng chọn đỉnh có bậc lớn nhất. Sử dụng thuật toán 1 để tạo tập I mới có từ đồ thị G’. Đặt G = G’, Quay lại bước 3. Thuật toán trên là tổng hợp của hai thuật toán đã trình bày trước. Cài đặt thuật toán này không quá khó khăn. Bạn có thể tự mình cài đặt được. Bài toán xếp lịch, cụ thể là bài toán xếp lịch thi tuy đã được chứng minh là thuộc lớp bài toán NP- đầy đủ (NP-complete), nhưng nếu biết sử dụng một một chiến thuật thuật toán hợp lý cùng với sự phát triển như vũ bão của công nghệ máy tính bài toán trên cũng phần nào đã được giải quyết. 8.2 Lý thuyết Cook 170
62. Phân tích thiết kế thuật toán Vấn đề P chống lại NP Với quyển từ điển trong tay, liệu bạn thấy tra nghĩa của từ “thằn lắn” dễ hơn, hay tìm một từ phổ thông để diễn tả “loài bò sát có bốn chân, da có vảy ánh kim, thường ở bờ bụi” dễ hơn? Câu trả lời hầu như chắc chắn là tra nghĩa thì dễ hơn tìm từ. Những các nhà toán học lại không chắc chắn như thế. Nhà toán học Canada Stephen Cook là người đầu tiên, vào năm 1971, đặt ra câu hỏi này một cách “toán học”. Sử dụng ngôn ngữ lôgic của tin học, ông đã định nghĩa một cách chính xác tập hợp những vấn đề mà người ta thẩm tra kết quả dễ hơn (gọi là tập hợp P), và tập hợp những vấn đề mà người ta dễ tìm ra hơn (gọi là tập hợp NP). Liệu hai tập hợp này có trùng nhau không? Các nhà lôgic học khẳng định P # NP. Như mọi người, họ tin rằng có những vấn đề rất khó tìm ra lời giải, nhưng lại dễ thẩm tra kết quả. Nó giống như việc tìm ra số chia của 13717421 là việc rất phức tạp, nhưng rất dễ kiểm tra rằng 3607 x 3808 = 13717421. Đó chính là nền tảng của phần lớn các loại mật mã: rất khó giải mã, nhưng lại dễ kiểm tra mã có đúng không. Tuy nhiên, cũng lại chưa có ai chứng minh được điều đó. “Nếu P=NP, mọi giả thuyết của chúng ta đến nay là sai” – Stephen Cook báo trước. “Một mặt, điều này sẽ giải quyết được rất nhiều vấn đề tin học ứng dụng trong công nghiệp; nhưng mặt khác lại sẽ phá hủy sự bảo mật của toàn bộ các giao dịch tài chính thực hiện qua Internet”. Mọi ngân hàng đều hoảng sợ trước vấn đề lôgic nhỏ bé và cơ bản này 171
63. Phân tích thiết kế thuật toán BÀI TẬP Bài 1 : Hãy viết một chương trình trong đó cài đặt đồ thị vô hướng bằng cấu trúc ma trận kề rồi viết các hàm/ thủ tục sau : Nhập tọa độ n đỉnh của đồ thị. Giả sử đồ thị là đầy đủ, nghĩa là giữa 2 đỉnh bất kỳ đều có cạnh nối và giả sử giá của mỗi cạnh là độ dài đoạn thẳng nối giữa 2 cạnh. Hãy tìm : Ðường đi ngắn nhất từ một đỉnh cho trước (Dijkstra). Ðường đi ngắn nhất giữa các cặp đỉnh (Floyd). Cây bao trùm tối tiểu (Prim và Kruskal). Thể hiện đồ thị trên màn hình đồ họa, các cạnh thuộc cây bao trùm tối thiểu được vẽ bằng một màu khác với các cạnh còn lại của đồ thị. Bài 2 : Bài toán người du lịch. Lập lịch cho một người đi du lịch đến các điểm du lịch định trước trong một thời gian xác định trước. Bài 3 : Tối ưu cây tìm kiếm nhị phân. 172
64. Phân tích thiết kế thuật toán CÁC BÀI THỰC HÀNH Bài thực hành số 1 CÀI ÐẶT DANH SÁCH BẰNG MẢNG Viết chương trình quản lý dòng văn bản. Yêu cầu chi tiết: 1. Viết phần khai báo để cài đặt một dòng văn bản (nội dung của văn bản là các ký tự, chiều dài tối đa của 1 dòng là 80 ký tự). 2. Viết thủ tục khởi tạo dòng rỗng 3. Thiết kế hàm kiểm tra dòng rỗng. 4. Thiết kế hàm kiểm tra dòng đầy. 5. Viết thủ tục nhập một dòng văn bản. 6. Viết thủ tục hiển thị dòng văn bản ra màn hình. 7. Viết thủ tục xen một ký tự x vào vị trí thứ p nào đó trong dòng văn bản D. 8. Viết thủ tục xóa một ký tự tại vị trí thứ p nào đó ra khỏi dòng văn bản D. 9. Thiết kế hàm copy một dòng văn bản để có một dòng văn bản mới. Copy k ký tự từ dòng D sang dòng D1 bắt đầu từ vị trí p trong dòng D (Không sử dụng hàm chuẩn của Pascal). 10. Viết hàm tìm vị trí của phần tử đầu tiên trong dòng văn bản có nội dung là x. 11. Viết thủ tục thay thế tất cả các ký tự c trong dòng văn bản D bằng ký tự c1. 12. Thiết kế hàm hoặc thủ tục lấy nội dung của phần tử thứ p trong dòng. 13. Viết thủ tục xóa tất cả các ký tự c trong dòng văn bản D. 14. Viết thủ tục cắt các khoảng trắng dư (các khoảng trắng không cần thiết) giữa 2 ký tự trong một dòng. 15. Thiết kế hàm kiểm tra dòng văn bản D1 có phải là dòng con của dòng văn bản D hay không. 173
65. Phân tích thiết kế thuật toán Viết chương trình nhập một dòng văn bản từ bàn phím, cắt tất cả các khoảng trống không cần thiết trong dòng này. Thay thế ký tự đầu dòng bằng ký tự hoa. Chép dòng văn bản này sang dòng mới để khi thao tác thì dòng văn bản cũ không bị mất đi. Trên dòng văn bản mới ta thực hiện các thao tác sau đây: 1. Xen một ký tự mới vào dòng. 2. Xóa một ký tự ra khỏi dòng. 3. Thay thế tất cả các ký tự nào đó trong dòng bằng ký tự mới. 4. Xóa tất cả các ký tự c trong dòng (c được nhập từ bàn phím). Nhập một dòng văn bản mới và kiểm tra xem dòng văn bản này có phải là dòng con của dòng văn bản đang lưu trữ hay không? 174