Bài giảng môn học Phân tích và thiết kế thuật toán - Đại Học Phương Đông

Tuy nhiên Greedy1 không cho lời giải tối ưu. Ví dụ sau

Ta thấy rằng thuật toán sẽ lựa chọn dạ tiệc 1, trong khi phương án tối ưu của bài toán là (Dạ tiệc 2, Dạ tiệc 3)

39/129

Greedy2: Ta chọn đoạn có độ dài ngắn nhất bổ xung vào S. Tuy nhiên thuật toán tham lam này cũng không cho kết quả tối ưu. Sau đây là phản ví dụ

Khi đó thuật toán sẽ lựa chọn (dạ tiệc 1) trong khi lời giải tối ưu của thuật toán là (dạ tiệc 2, dạ tiệc 3).

Greedy3:Xắp xếp các đoạn thẳng theo thứ tự không giảm của mút phải. Bắt đầu từ tập S là tập rỗng ta lần lượt xét các đoạn trong danh sách theo thứ tự đã sắp xếp và bổ xung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. (Dạ tiệc nào kết thúc sớm sẽ được xét trước).

Mệnhđề1: Thuật toán Greedy3 cho lời giải tối ưu của bài toán về các đoạn thẳng không giao nhau.

ChứngMinh: Giả sử Greedy3 không cho lời giải đúng. Phải tìm bộ dữ liệu C sao cho thuật toán không cho lời giải tối u. Giả sử G3(C) là lời giải tìm được bởi Greedy3. Gọi O là lời giải tối ưu có số đoạn thẳng chung với G3(C) là lớn nhất. Gọi X là đoạn thẳng đầu tiên có trong G3(C) nhưng không có trong O. Đoạn này là tồn tại, vì nếu trái lại thì G3(C) ≡ O ( mâu thuẫn vì đã giả thiết G3(C) ≠ O ) hay G3(C) Є O ( Cũng mâu thuẫn vì khi đó thuật toán phải chọn đoạn thẳng X) (O cũng được sắp xếp giống G3(C)).

Gọi Y là đoạn đầu tiên kể từ bên trái của O không có mắt trong G3(C). Đoạn Y cũng phải tồn tại (Chứng minh tương tự như trên).

Khi đó mút phải của đoạn X phải ở bên trái (nhỏ hơn) mút phải của đoạn Y, vì nếu trái lại thuật toán sẽ chọn Y thay vì X.

Xét

Rõ ràng

40/129

• O’ gồm các đoạn thẳng không giao với nhau, bởi vì X không giao với bất kì đoạn nào ở bên trái nó trong O’ ( do G3(C) là chấp nhận được ) cũng như không giao với bất cứ đoạn nào ở bên phải nó trong O’ (Do mút phải của X nhỏ

hơn mút phải của Y và Y không giao với bất cứ đoạn nào ở bên phải Y trong O’).

• Do O’ có cùng lực lượng với O nên O’ cũng là tối ưu • Tuy nhiên ta thấy rằng O’ giống với G3(C) hơn là O => mâu thuẫn với giả

thiết.

Bài toán cái túi

Bài toán: cho n đồ vật, trong lượng tương ứng của từng đồ vật là wi, và giá trị là ci(),

Ta chất đồ vật vào túi có trọng lượng b, sao cho tổng trọng lượng không vượt quá b và đạt giá trị lớn nhất.

Đề xuất thuật toán t h am lam

Greedy1: Sắp xếp theo thứ tự không tăng của giá trị. Xét các đồ vật theo thứ tự đã xếp, lần lượt chất các đồ vật đang xét vào túi nếu dung lượng còn lại trong túi đủ chứa nó. Thuật toán tham lam này không cho lời giải tối ưu. Sau đây là phản ví dụ:

Tham số của bài toán là n = 3; b = 19.

Đồ vật 1 2 3

Giá trị 20 16 8 -> giátrị lớnnhưngtrọnglượngcũngrấtlớn

Trọng lượng 14 6 10

Thuật toán sẽ lựa chọn đồ vật 1 với tổng giá trị là 20, trong khi lời giải tối ưu của bài toán là lựa chọn (đồ vật 2, đồ vật 3 ) với tổng giá trị là 24.

Greedy2: Sắp xếp đồ vật không giảm của trọng lượng. Lần lượt chất các đồ vật vào túi theo thứ tự đã sắp xếp. Thuật toán tham lam này cũng không cho kết quả tối ưu. Sau đây là phản ví dụ

41/129

Tham số của bài toán là n = 3; b = 11

Đồ vật 1 2 3

Giá trị 10 16 28 ->Đồvậtnhẹnhưnggiá tiềncũngrấtnhẹ

Trọng lượng 5 6 10

Thuật toán sẽ lựa chọn (đồ vật 1, đồ vật 2) với tổng giá trị là 26, trong khi lời giải tối ưu của bài toán là (đồ vật 3) với tổng giá trị là 28.

Greedy3: Sắp xếp các đồ vật theo thứ tự không tăng của giá trị một đơn vị trọng 1lượng (ci/wi). Lần lượt xét

Tuy nhiên Greedy3 không cho lời giải tối ưu. Sau đây là phản ví dụ của bài toán

Tham số của bài toán : n= 2; b≥ 2.

Khi đó thuật toán chỉ lựa chọn được đồ vật 1 với tổng giá trị là 10, trong khi lời giải tối ưu của bài toán lựa chọn đồ vật 2 với tổng giá trị là 10b-1 ( ≥ 10.2-1 = 19 > 10).

Greedy4:Gọi Ij là lời giải thu được theo thuật toán Greedyj (j = 1, 2, 3). Gọi

Định lý : Lời giải I4 thoả mãn bất đẳng thức

42/129

Trong đó f* là giá trị tối u của bài toán.

Phương pháp “chia để trị”

Sơ đồ chung của phương pháp

Bài toán ví dụ

Giả sử ta có thuật toán α để giải bài toán kích thước dữ liệu với thời gian bị chặn bởi cn2. Xét thuật toánβđểgiải chính bài toán đó bằng cách

• Bước 1 : Chia bài toán cần giải ra thành 3 bài toán con với kích thước n/2 • Bước 2 : Giải 3 bài toán con bằng thuật toán α • Bước3 : Tổng hợplời giải của 3 bài toán con để thu được lời giải của bài toán

Giả sử bước 3 đượcthực hiện với thời gian d.n

Gọi Tm(n) : thời gian của thuật toánα

Tp(n): thời gian của thuật toán β

Khi đó Tm(n) = cn2

Tp(n) =3 Tm(n) +dn= cn2 + dn

Nên nếu dn

Tuy nhiên ta thấy thuật toán β mới chỉ thay đổi được nhân tử hằng số chưa thay đổiđược bậc nhưng cũng hiệu quả khi n lớn. Do đó, nếu ta tiếp tục chia bài toán con nhỏ nữa tới n0≤ 4 d/c ta sẽ thu được một thuật toán hiệu quả hơn.

Xét thuật toán sau :

ProcedureGamma(n)(* n kích thước bài toán*) Begin

If n ≤ n0 Then

Giải bài toán bằng thuật toán α

43/129

Else

Begin

End

End;

1. Chia bài toán thành ba bài toán con kích thước n/2 2. Giải mỗi bài toán con bằng thuật toán Gamma 3. Tổng hợp lời giải của các bài toán con

Gọi T (n) là thời gian tính của thuật toán trên, và thời gian tổng hợp lời giải của các bài toán con là? (n) thì

Theo định lý thợ ta có

Thuật toán thu được có thời gian tính là tốt hơn cả thuật toánαvà thuật toánβ .Hiệu quả thu được trong thuật toán?có được là nhờ ta đã triệt để khai thác hiệu quả việcsử dụng thuật toán β .

Để có được mô tả chi tiết thuật toán chiađể trị chúng ta cần phải xác định :

1. Kích thước tới hạn n0 (Bài toán có kích thước nhỏ hơn n0 sẽ không cần chia

nhỏ)

2. Kích thước của mỗi bài toán con trong cách chia 3. Số lượng các bài toán con như vậy 4. Thuật toán tổng hợp lời giải của các bài toán con

Các phần xác định trong 2 và 3 phụ thuộc vào 4. Chia như thế nào để khi tổng hợp có hiệu quả (thường là tuyến tính)

Sơ đồ thuật toán tổng quát

Procedure D_and_C(n) Begin

If n ( n0 Then

44/129

Giải bài toán một cách trực tiếp

Else

1. Chia bài toán thành r bài toán con kích thước n/k 2. For (Mỗi bài toán trong r bài toán con) Do D_and_C(n)

End;

1. Tổng hợp lời giải của r bài toán con đểthu được lời giải của bài toán gốc

Thuật toán tìm kiếm nhị phân

Bài toán : Cho mảng x[1..n] được sắp xếp theo thứ tự không giảm và y. Tìm i sao cho x[i] = y. (Giả thiết i tồn tại).

Phân tích giải thuật:

Số y cho trước

• Hoặc là bằng phần tử nằm ở vị trí giữa mảng x • Hoặc là nằm ở nửa bên trái (y < phần tử ở giữa mảng x ) • Hoặc là nằm ở nửa bên phải (y < phần tử ở giữa mảng x ) Từ nhận xét đó ta có

giải thuật sau

Function Bsearch(x[1..n],Start,Finish) Begin

Middle := (Start + Finish)/2;

If (y = x[Middle]) then return middle

Else

If ( y < x[Middle] then return Bsearch(x,Start,Middle-1) Else

End;

Return Bsearch (x,Middle+1,Finish)

Phân tích hiệu quả thuật toán : T(n)

45/129

Theo định lý thợ ta có

Phép nhân các số nguyên lớn

Xét lại vấn đề nhân các số nguyên lớn. Nhớ lại rằng thuật toán cổ điển mà phần lớn chúng ta đều được học ở trường đòi hỏi thời gian tính là Ρ(n2) để nhân các số nguyên m có n chữ số. Chúng ta cũng quen với thuật toán này đến mức có thể còn chẳng bao giờ thắc mắc về tính tối ưu của nó. Liệu chúng ta có thể làm được tốt hơn không? . Một thuật toán được bàn đến gọi là kỹ thuật Chia để trị bao gồm việc rút gọn phép nhân hai số nguyên n chữ số xuống thành bốn phép nhân hai số nguyên n/2 chữ số.

-Việc nhân 2 số nguyên có 1 chữ số có thể thực hiện một cách trực tiếp (neo đệ qui), thời gian thực hiện làO(1)

46/129

-Chia : n >1 thì tích củahai số nguyên có n chữ số có thể biểu diễn qua tích 4 số nguyên có n/2 chữ số,thời gian thực hiện là 4. T ( n /2) ( trong đó T(n) là thời gian thực hiện nhân hai số nguyên cón chữ số ).

-Tổng hợp : Cộng và dịch phải, khi đóthời gian thực hiện sẽ là?( n ) Khi đó ta có thời gian thực hiệnthuật toán là

Theo định lý thợ ta có độ phức tạp của thuật toán là Tn = (On2) .Như vậy thuật toán thu được cũng không gặt hái được bất kỳ cải thiện nào so với thuật toán nhân cổ điển mặc dù chúng ta đã khôn ngoan hơn. Để vượt được thuậttoán cổ điển và như vậy mới hoàn toàn thấy rõ được công dụng của phép Chia để trị, chúng ta phải tìm cách rút gọn phép nhân nguyên thuỷ không phải về bốn mà làbaphép nhân hai nửa.

Chúng ta minh hoạ quá trình này bằng việc nhân 981 với 1234. Trước tiên chúng ta điền thêm vào toán hạng ngắn hơn một số không vô nghĩa để làm cho haitoán hạng có cùng độ dài, vậy là 981 trở thành 0981. Sau đó tách từng toán hạngthành hai nửa: 0981 cho ra w = 09 và x = 81, còn 1234 thành y = 12 và z= 34.Lưu ý rằng 981 = 102w + x và 1234 = 102y + z. Do đó, tíchcần tìm có thể tính được là 981 x 1234 =(102w + x)( 102y + z) = 104wy + 102(wz + xy) +xz = 1080000 + 127800 + 2754 =1210554

Thủ tục trên đến bốn phép nhân hai nửa:wy, wz, xy và xz.

Để ý điểm mấu chốt ở đây là thực ra thì không cần tính cả wz lẫn xy, mà là tổng của hai số hạng này. Liệu có thể thu được wz + xy với chi phí của một phép nhân mà thôi hay không? Điều này có vẻ nhưkhông thể được cho đến khi chúngta nhớ ra rằngmình cũng cần những giá trị wy và xz để đưa vào công thức trên. Lưu ý về điểmnày, hãy xét tích:

r = (w + x)(y+z) = wy +(wz + xy) + xz

Chỉ sau một phép nhân, chúng ta thu đượctổng của tất cả ba số hạng cần thiết để tính được tích mình mong muốn. Điều này gợi ý một cách tiến hành như sau:

p = wy = 09 * 12 =108

q = xz = 81 * 34 =2754

r = (w + x)(y+z) = 90 *46 = 4140

và cuối cùng

47/129

981 x 1234 =104p + 102(r – p – q) + q = 1080000 + 127800 + 2754 =1210554.

Như vậy tích của 981 và 1234 có thể rútgọn về ba phép nhân của hai số có hai chữ số

(09 12, 81 34 và 90 46) cùng với một số nào đó phép dịch chuyển (nhân với luỹ thừa của 10),phép cộng và phép trừ.

Chắc chắn là số các phép cộng – coi phéptrừ như là phép cộng – có nhiều hơn so với thuật toán Chia để trị nguyên thuỷ ởphần trước. Vậy thì có đáng để thực hiện bốn phép cộng nhiều hơn để tiết kiệmmột phép nhân hay không? Câu trả lời là không nếu chúng ta đang nhân số nhỏ như những số trong ví dụ này. Tuy nhiên sẽ là đáng giá nếu các số cần được nhân vớinhau đủ lớn và chúng càng lớn thì lại càng đáng làm như vậy. Khi các số hạng đủlớn, thời gian cần cho các phép cộng và dịch chuyển trở thành bỏ qua được so vớithời gian cần cho chỉ một phép nhân. Như vậy là có lý do để kỳ vọng rằng rút gọn bốn phép nhân về còn ba sẽ giúp chúng ta cắt giảm được 25% thời gian tính toán đòi hỏi cho việc nhân các số lớn. Như chúng ta sẽ thấy, sự tiết kiệm của mình sẽtốt hơn một cách đáng kể.

Để giúp chúng ta hiểu thấu đượcnhững gì mình đạt được, hãy giả thiết rằng có một cài đặt của thuật toán nhân cổđiển đòi hỏi thời gian h(n) = cn2để nhân hai số có n chữ số, với hằng số c phụ thuộc vàocài đặt đó. (ở đây đã có sự đơn giản hoá vì trên thực tế thì thời gian đòi hỏicòn có dạng phức tạp hơn, chẳng hạn như cn2+ bn + a). Tương tự, chog(n) là thời gian mà thuật toán Chia để trị cần để nhân haisố n chữ số,không tính thời gian cần thiết để thực hiện ba phép nhân hai nửa. Nói cách khác,g(n) là thời gian cần thiết cho các phép cộng, dịch chuyển và các phép tính phụthêm khác. Dễ dàng cài đặt các phép tính này sao cho g(n)∈Ρ(n).Hãy tạm thời bỏ qua điều gì sẽ xảy ra nếu n lẻ và nếu các số hạng không có cùngđộ dài.

Nếu từng trong số ba phép nhân hai nửađược thực hiện bằng thuật toán cổ điển, thời gian cần thiết để nhân hai số có nchữ số là: 3h(n/2) + g(n) =3c(n/2)2+ g(n) = cn2+ g(n)= h(n) +g(n).

Vì h(n) rất nhỏ xo với Ρ(n2)và g(n) rất nhỏ xo với Ρ(n),số hạng g(n) là bỏ qua được so với h(n)khi n đủ lớn, có nghĩa là chúng ta tăng được tốc độ lên khoảng 25% so với thuậttoán cổ điển như đã mong đợi. Mặc dù sự cải thiện này là không thể xem thường được nhưng chúng ta vẫn không làm được thay đổi bậc của thời gian cần thiết:thuật toán mới vẫn cần thời gian tính bậc hai.

48/129

Để có thể làm được tốt hơn thế, chúng tatrở lại với câu hỏi đặt ra ở đoạn mở đầu: các bài toán con cần được giải như thế nào? Nếu chúng nhỏ thôi thì thuật toán cổ điển có vẫn còn là cách làm tốt nhất. Tuy nhiên, khi những bài toán con cũng đủ lớn, chẳng lẽ sử dụng thuật toánmới của chúng ta một cách đệ quy cũng không hơn gì hay sao? Ý tưởng này tương tựnhư hưởng lợi nhuận từ một tài khoản ngân hàng có gộp vốn lẫnlãi! Nếu chúng talàm như vậy sẽ thu được một thuật toán có thể nhân hai số n chữ số trong mộtthời gian t(n) = 3t(n/2) + g(n) khi nchẵn và đủ lớn. Điều này cũng giống như phép

truy toán (đệ quy) ; giải ra tathu được t(n)∈O(nlg3) | n là luỹ thừa của 2. Chúng ta cần phải bằng lòng với lờighi chú tiệm cận có điều kiện vì chưa đề cập đến câu hỏi là nhân các số có độdài là lẻ như thế nào.

Vì lg3 = 1.585 nhỏ hơn 2, thuật toán này có thể nhân hai số nguyên lớn nhanh hơn rất nhiều so với thuật toán nhân cổ điểnvà n càng lớn thì sự cải thiện này càng đáng giá. Mộ cài đặt tốt có thể khôngsử dụng cơ số 10, mà sử dụng cơ số lớn nhất để với cơ số đó phần cứng cho phép nhân trực tiếp hai “chữ số” với nhau.

Một nhân tố quan trọng trong hiệu suất thực tế của cách tiếp cận phép nhân này và của bất kỳthuật toán Chia để trị nào là biết khi nào cần dừng việc phân chia các bài toánvà thay vào đó sử dụng thuật toán cổ điển. Mặc dù cách tiếp cận Chia để trị trởnên có ích khi bài toán cần giải đủ lớn, trên thực tế nó có thể chậm hơn so vớithuật toán cổ điển đối với những bài toán quá nhỏ. Do đó thuật toánChia để trị phải tránh việc thực hiện đệ quy khi kích thước của các bài toán con không phù hợp nữa. Chúng ta sẽ trở lại vấn đề này ở phần sau.

Để đơn giản, một số vấn đề quan trọng đến nay đã bị bỏ qua. Làm thế nào để chúng ta giải quyết được những số có độ dài lẻ?Mặc dù cả hai nửa của số nhân và số bị nhân đều có kích thước n/2, có thể xảy ratrường hợp tổng của chúng bị tràn và có kích thước vượt quá 1. Do đó sẽ không hoàn toàn chính xác khi nói rằng r = (w+x)(y+z) bao hàm phép nhân hai nửa. Điềunày ảnh hưởng tới việc phân tích thời gian chạy như thế nào? Làm thế nào để nhânhai số có kích thước khác nhau? Còn những phép tính số học nào khác với phépnhân mà ta có thể xử lý hiệu quả hơn so với dùng thuật toán cổ điển?

Những số có độ dài lẻ được nhân dễ dàng bằng cách tách chúng càng gần ở giữa càng tốt: một số có n chữ số được táchthành một số có |n/2| chữ số và một số có |n/2| chữ số. Câu hỏi thứ hai còn khắtkhe hơn. Xét nhân 5678 với 6789. Thuật toán của chúng ta tách các số hạng thànhw = 56, x = 78, y = 67 và z = 89. Ba phép nhân hai nửa cần thực hiện là:

p = wy = 56.67

q = xz = 78.89 và

r = (w+x)(y+z) =134.156

Phép nhân thứ ba bao gồm những số 3 chữ số, do vậy nó không thực sự là một nửa so với phép nhân nguyên thuỷ của các sốcó 4 chữ số. Tuy nhiên kích thước của w+x và

y+z không thể vượt quá 1 +|n/2|.

49/129

Để đơn giản hoá việc phân tích, cho t(n)là thời gian mà thuật toán này thực hiện trong tìn huống xấu nhất để nhân haisố có kích thước tối đa là n (thay vì chính xác bằng n).

Theo định nghĩa thì t(n) là một hàm không giảm.Khi n đủ lớn thuật toán của chúng ta rút gọn phép nhân hai số có kích thước tối đa n đó về ba phép nhân nhỏ hơn p = wy, q = xz và r = (w+x)(y+z) với kích thước tối đa tương ứng là |n/2|, |n/2| và 1 + |n/2|, thêm vào đó là những thao tác đơn giản chiếmthời gian là O(n). Do đó ở đây tồn tại hằng số dương c saocho: t(n) = t(|n/2|) +t(|n/2|) + t(1+|n/2|) + cn với mọi n đủ lớn. Điều này chính xác là phép đệ quy mà chúng ta đã nghiên cứu cho kết quả giờ đây đã trở nên quen thuộc là t(n)∈O( nlg 3). Do vậy luôn luôn có thể nhân các số n chữ số với thờigian O(nlg3). Phân tích tình huống tồi nhất của thuật toán này chỉ rarằng trên thực tế t(n) Ρ(nlg3),nhưng điều này không được quan tâm lắm vì còn có những thuật toán nhân nhanh hơn.

Quay lại với câu hỏi nhân các số có kích thước khác nhau, giả sử u và v là những số nguyên có kích thước tương ứng là mvà n. Nếu m và n nằm trong khoảng đến hai lần của nhau, tốt nhất là điền vào sốhạng nhỏ hơn những số 0 vô nghĩa để làm cho nó có cùng độ dài như số hạng kia,như chúng ta đã làm khi nhân 981 với 1234. Tuy nhiên cách tiếp cận này khôngđược khuyến khích khi một số hạng lớn hơn số hạng kia rất nhiều. Thậm chí nó có thể tồi hơn là dùng thuật toán nhân cổđiển! Không làm mất đi tính tổng quát, giả sử rằng m≥n.Thuật toán Chia để trị sử dụng điền số và thuật toán cổ điển có thời gian tươngứng là Ρ(nlg3) và Ρ(mn) để tính các tích u và v. Xét thấy rằng hằng số Nn của biểu thức trước có vẻ lớnhơn của biểu thức sau, chúng ta thấy rằng Chia để trị sử dụng điền số là chậmhơn thuật toán cổ điển khi m = nlg(3/2)và như vậy trường hợp đặc biệt khi m = n.Mặc dù vậy rất dễ dàng kết hợp cảhai thuật toán để thu được một thuật toán thực sự tốt hơn. ý tưởng là cắt lát sốhạng dài hơn v thành những đoạn có kích thước m và sử dụng thuật toán Chia đểtrị để nhân u với từng đoạn của v sao cho thuật toán Chia để trị được dùng đểnhân những cặp số hạng có cùng kích thước. Tích cuối cùng của u và v sau đó thuđược dễ dàng bằng các phép cộng và dịch chuyển đơn giản. Thời gian chạy tổngcộng chủ yếu được dùng để thực hiện |n/m| phép nhân các số m chữ số. Vì mỗi phépnhân nhỏ hơn này chiếm thời gian Ρ(mlg3) và vì |n/m|∈Ρ(n/m) ,thời gian chạy tổng cộng để nhân một số n chữ số với một số m chữ số làΡ(nmlg(3/2))khi m = n.

Sau đây là mô hình cải tiến thuật toán nhân số nguyên lớn

Cải tiến để còn lại 3 phép nhân :

Từ đó ta đưa ra thuật toán nhân số nguyên lớn là

Function Karatsuba(x,y,n); Begin

50/129

If n = 1 then Return x[0]*y[0] Else

Begin

a := x[n-1].. . x[n/2];b := x[n/2-1] . . .x[0];

c := y[n-1]. .. y[n/2];d := y[n/2-1] . . .y[0]; U :=Karatsuba(a,c,n/2);

V :=Karasuba(b,d,n/2);

W :=Karatsuba(a+b,c+d,n/2); Return U*10n+ (W-U-V)*10n/2+ V end

End;

Phân tích hiệu quả thuật toán : T ( n )

T (1) =1

T ( n ) = 3 T ( n /2) + cn

=>Theo định lý thợ T( n ) =Ρ(nlog 3)

Một số giải thuật sắp xếp

Cho T[1..n] là một mảng n phần tử. Vấn đề đặt ra là sắp xếp các phần tử này theo thứ tự tăng. Chúng ta đã có thể giải quyết vấn đề này bằng các phương phápselection sort hay insertion sort hoặc là heapsort

Như chúng ta đã biết thời gian dùng selection sort hay insertion sort để sắp xếp mảng T trong cả hai trường hợp: xấu nhất và trung bình đều vào cỡ n2. Còn heapsort vào khoảng nlogn.

Có một số giải thuật đặc biệt cho bài toán này theo mô hình chia để trị đó làmergesortvà quicksort, chúng ta sẽ lần lượt đi nghiên cứu chúng.

MergeSort

Chia để trị tiếp cận tới bài toán này bằng việc tách mảng T thành hai phần màkích thước của chúng sai khác nhau càng ít càng tốt, sắp xếp các phần này bằng cách gọi đệ qui và sau đó trộn chúng lại (chú ý duy trì tính thứ tự). Để làm được điều này chúng ta cần một giải thuật hiệu quả cho việc trộn hai mảng đã được sắp U và V thành một mảng mới T mà kích thước của mảng T bằng tổng kích thước của hai mảng U và V.

51/129

Vấn đề này có thể thực hiện tốt hơn nếu ta thêm vào các ô nhớ có sẵn ở cuối của mảng U và V các giá trị đứng canh (giá trị lớn hơn tất cả các giá trị trong U và V) .

Procedure merge(U[1..m+1],V[1..n+1],Ta[1..m+n]);

(*Trộn 2 mảng U[1..m+1] và V[1..n+1] thành mảng T[1..m+n]); U[m+1],V[n+1] được dùng để chứa các giá trị cầm canh*)

Begin i:=1;j:=1;

U[m+1]:= ∞ ; V[n+1]:= ∞ ;

For k:=1 to n+m do

If U[i]

Begin

T[k]:=U[i];

i:=i+1;

Else

End

Begin

T[k]:=V[j];

j:=j+1;

End;

End;

Giải thuật sắp xếp trộn sau đây có thể tốt hơn nếu các mảng U và V là các biến toàn cục và xem việc sắp xếp chèn Insert(T) như là giải thuật cơ bản

Procedure mergesort(T[1..n]);

Begin

If n đủ nhỏ then Insert(T)

52/129

Else

Begin

Array U[1..1+],V[1..1+; U[1..]:=T[1..];

V[1..]:=T[1+..n]; mergesort(U[1..]);

End;

mergesort(V[1..]);

merge(U,V,T);

Hình sau chỉ ra các bước của mergesort.

Giải thuật sắp xếp này minh hoạ tất cả các khía cạnh của chia để trị. Khi số lượng các phần tử cần sắp là nhỏ thì ta thường sử dụng các giải thuật sắp xếp đơn giản.

Khi số phần tử đủ lớn thì ta chia mảng ra 2 phần, tiếp đến trị từng phần một và cuối cùng là kết hợp các lời giải.

Giả sử t(n) là thời gian cần thiết để giải thuật này sắp xếp một mảng n phần tử. Việc tách T thành U và V là tuyến tính. Ta cũng dễ thấy merge(U,V,T) cũng tuyến tính. Do vậy:

t(n)=t([n/2]) + t([n/2]) + g(n)

53/129

trong đó g( n ) = O( n )

hay t( n )=2t( n /2)+g( n )

Theo định lý chủ

Tacó: l=2; b=2và k=1

Nên t(n)= Ρ (nlogn), vì bk =l

Như vậy hiệu quả của mergesort tương tự heapsort. Trong thực tế sắp xếp trộn có thể nhanh hơn heapsort một ít nhưng nó cần nhiều hơn bộ nhớ cho các mảng trung gian U và V. Ta nhớ lại heapsort có thể sắp xếp tại chỗ (in-place), và cảm giác nó chỉ sử dụng một ít biến phụ mà thôi. Theo lý thuyết mergesort cũng có thể làm được như vậy tuy nhiên giá thành có tăng một chút ít.

Khi giải bài toán theo thuật giải chia để trị chúng ta hết sức chú ý đến việc tạo ra các bài toán con, nếu không nó có thể tạo ra những thảm hại mà không thể lường trước được. Giải thuật sau đây minh hoạ tính chất quan trọng này khi kích thước bài toán con là hỗn độn:

Procedure badmergesort(T[1..n]);

Begin

If n đủ nhỏ then Insert(T) Else

Begin

Array U[1..n-1, V[1..2]; U[1..n-1]:= T[1..n-1]; V[1]:= T[n]; badmergesort(U[1..n-1]); badergesort(V[1..1]);

merge(U,V,T);

End;

ˆ t (n)

Gọi

ˆ t

ˆ t

ˆ t

là thời gian cần để sắp n phần tử với giải thuật badmergesort trên. Rõ ràng là:

ˆ g (n), trong đó (n) ∈ Ρ(n).

(n) = (n-1) + (1) +

54/129

Sự đệ qui này tạo ra (n) ∈ Ρ(n2), như vậy việc quên cân bằng kích thước của bài toán con đã ảnh hưởng đáng kể đến hiệu quả của việc sử dụng giải thuật chia đểtrị.

Quicksort

Giải thuật này được phát minh bởi Hoare, nó thường được hiểu như là tên gọi của nó - sắp xếp nhanh, hơn nữa nó cũng dựa theo nguyên tắc chia để trị. Không giống như mergesort nó quan tâm đến việc giải các bài toán con hơn là sự kết hợp giữa các lời giải của chúng. Bước đầu tiên của giải thuật này là chọn 1 vật trung tâm (pivot) từ các phần tử của mảng cần sắp. Tiếp đến vật trung tâm sẽ ngăn mảng này ra 2 phần: các phần tử lớn hơn vật trung tâm thì được chuyển về bên phải nó, ngược lại thì chuyển về bên trái. Sau đó mỗi phần của mảng được sắp xếp độc lập bằng cách gọi đệ qui giải thuật này. Cuối cùng mảng sẽ được sắp xếp xong. Để cân bằng kích thước của 2 mảng này ta có thể sử dụng phần tử ở giữa (median) như là vật trung tâm . Đáng tiếc là việc tìm phần ở giữa cũng mất 1 thời gian đáng kể. Để giải quyêt điều đó đơn giNn là chúng ta sử dụng 1 phần tử tuỳ ý trong mảng cần sắp như là vậttrung tâm và hi vọng nó làtốt nhất có thể.

Việc thiết kế giải thuật ngăn cách mảng bằng vật trung tâm với thời gian tuyến tính không phải là sự thách đố (có thể làm được). Tuy nhiên điều đó là cần thiết để so sánh với các giải thuật sắp xếp khác như là heapsort. Vấn đề đặt ra là mảng con T[i..j] cần được ngăn bởi vật trung tâm p=T[i]. Một cách làm có thể chấp nhận được là:

Duyệt qua từng phần tử của của nó chỉ một lần nhưng bắt đầu từ hai phía (đầu và cuối mảng). Khi đó khởi tạo k=i; l=j+1, k tăng dần cho đến khi T[k] > p, l giảm dần cho đến khi T[l] ( l. Tiếp đến hoán vị T[k] và T[l]. Quá trình này tiếp tục cho đến khi k ( l. Cuối cùng đổi chổ T[i] và T[l] cho nhau và lúc này ta xác định đúng vị trí của phần tử trung tâm.

Procedure Pivot(T[i..j], var l)

(* Hoán vị các phần tử trong mảng T[i..j] và cuối cùng trả về giá trị l (1≤l≤j)

sao cho T[l]=p ,T[k]≤p với mọi k (i≤k < l) và T[k] > p với mọi k (l < k≤ j), ở đây

p được khởi tạo là T[i] *) Begin

p:=T[i]; k:=i; l:=j+1;

repeat k:=k+1; until (T[k] > p) or (k≥j);

repeat l:=l-1; until (T[l] < p);

while (k

begin

55/129

End;

Swap(T[k],T[l]); (* Đổi chỗ T[k] và T[l] *)

repeat k:=k+1; until (T[k] > p); repeat l:=l-1; until (T[l]≤p); Swap(T[i],T[l]);

end;

Sau đây là giải thuật sắp xếp với tên gọi là Quicksort dùng để sắp xếp mảng T[1..n]:

Procedure Quicksort(T[i..j]); (* Sắp xếp theo thứ tự không giảm *) Begin

if n đủ nhỏ then Insert(T[i..j])

else begin

pivot(T[i..j],l);

quicksort(T[i..l-1];

quicksort(T[l+1,j];

End;

end;

56/129

Hình vẽ sau cho thấy sự làm việc của pivot và quicksort.

Quicksort sẽ không hiệu quả nếu sử dụng việc gọi đệ quy của các bài toán con mà không chú ý đến sự cân bằng kích thước của chúng. Tình huống xấu nhất là khi T đã được sắp trước mà gọi quicksort và thời gian dùng quicksort để sắp là O( n 2).

57/129

Gọi t( n ) là thời gian trung bình dùng quicksort để sắp mảngnphần tử T[1.. n ].llà

giá trị trả về khi gọi pivot(T[1..n],l). Theo pivot() thì l nằm giữa 1 ( n và xác suất là 1/n. Thời gian để tìm vật trung tâm g(n) là tuyến tính. Thời gian để dùng đệ qui để sắp xếp hai mảng con kích thước (l-1) và (n-l) tương ứng là t(n-1) và t(n-l). Như vậy với n đủ lớn ta có:

Hay rõ ràng hơn ta chọnn 0 là giá trị đủ lớn để sử dụng công thức trên. Nghĩa là nếu n nn 0.

Với công thức như trên quả là khó phân tích độ phức tạp. Ta dự đoán nó tương tự mergesort và hi vọng nó là như vậy tức là vào cỡ O(nlogn). Thật vậy ta có định lý sau:

Định lý: Quicksort cần nlogn thời gian để sắp xếp n phần tử trong trường hợp trung bình.

Chứng minh

Gọi t( n ) là thời gian cần thiết để sắp n phần tử trong trường hợp trung bình. a,n 0 là các hằng số giống như công thức 2.7.1

Ta chứng minh t( n ) = cnlogn với mọin≥ 2. với c là hằng số.

Dùng phương pháp qui nạp để chứng minh:

- Với mọinnguyên dương: (2 ≤n≤n) Dễ thấy t( n ) ≤ cnlogn

- Bước qui nạp

58/129

Ta có

Giả thiết rằng: t(k) ≤ cklogk với mọi 2 ≤ k < n

Ta chỉ ra c sao cho t( n ) ≤ cnlogn

Lấy a = t(0) +t(1)

Theo giả thiết qui nạp : t(k) = cklogk

t( n ) = cnlogn với điều kiện là

59/129

,

hay c ≥ 2d + 4a/n2

Từ đó chúng ta chỉ xem xét với những n > n0 thoả mãn:

Hay ta có t( n ) ≤ cnlogn với mọin≥ 2, và như vậy định lý được chứng minh.

Như vậy quicksort có thể sắp xếp 1 mảng n phần tử khác nhau trong trường hợp trung bình là O( nlogn ). Câu hỏi đặt ra là liệu có thể sửa đổi quicksort để nó sắp xếp với thời gian O( nlogn ) trong trương hợp xấu nhất hay không. Câu trả lời là có thể!!!. Tuy nhiên nếu việc tìm phần tử ở giữa của T[i..j] là tuyến tính và lấy nó làm vật trung tâm (pivot) (Finding the median) thì quicksort cũng cần O( n 2) để sắp xếpnphần tử trong trường hợp xấu nhất (khi tất cả các phần tử của mảng cần sắp là bằng nhau). Giải thuật sau đây có thể khắc phục được vấn đề này:

Procedure Pivotbis(T[1..n],p; var k,l);

p - là vật trung tâm

T[1..n] chia ra 3 phần:

T[1..k]: gồm các phần tử < p T[k+1..l-1]: gồm các phần tử = p T[l..n]: gồm các phần tử > p

k,l là các giá trị trả về của Pivotbis(T[i..j],T[i],k,l)

Sau khi ngăn cách mảng T[1..n] bằng việc gọi Pivotbis(T[i..j],T[i],k,l), phần còn lại có thể gọi đệ qui quicksort cho T[1..k] và T[l+1..n].

60/129

Với cách sửa đổi này việc sắp mảng trên là tuyến tính. Thú vị hơn là quicksort có thể sắp với thời gian là O( nlogn ) trong trường hợp xấu nhất nếu phần tử ở giữa chọn làm vật trung tâm là tuyến tính. Tuy nhiên chúng ta đưa ra vấn đề này chỉ có tính lý thuyết

bởi vì để cải tiến nó thì sẽ tăng sự phức tạp của giải thuật này ở các hằng số Nn (hide constant), thà vậy thì dùng heapsort còn hơn!.

Bài toán nhân ma trận

Bài toán : Cho hai ma trận A, B với kích thước n*n, ta có ma trận C chứa kết quả của phép nhân hai ma trận A và B. Thuật toán nhân ma trận cổ điển như công thức dưới đây:

phân tích thuật toán

Với mảng một chiều (kích thước n phần tử), ma trận C được tính trong thời gian O(n), giả sử rằng phép cộng vô hướng và phép nhân là các phép tính cơ bản (có thời gian tính là hằng số). Với mảng hai chiểu (kích thước n*n) thì thời gian để tính phép nhân ma trận AB là O( n 3)

Đến cuối những năm 1960, Strassen đưa ra một giải pháp cải tiến thuật toán trên, nó có tính đột phá trong lịch sử của thuật toán chia để trị, thậm chí gây ngạc nhiên không kém thuật toán nhân số nguyên lớn được phát minh ở thập kỷ trước. ý tưởng cơ bản của thuật toán Strassen cũng tương tự như thuật toán trên. Đầu tiên ta chứng minh rằng phép nhân hai ma trận với kích thước 2*2 có thể thực hiện được bằng cách sử dụng ít hơn 8 phép nhân vô hướng như thuật toán cổ điển bắt buộc. Ta xét phép nhân hai ma trận A, B như sau:

61/129

Ta có các biểu thức sau, mỗi biểu thức chỉ có một phép nhân:

Ta có ma trận C là tích của hai ma trận A và B là:

Do đó ta thấy rằng, có thể nhân hai ma trận kích thước 2*2 bằng cách chỉ sử dụng 7 phép nhân vô hướng. Nhìn thoáng qua thấy rằng thuật toán này không có gì thú vị lắm, nó sử dụng một số lượng lớn các phép cộng và phép trừ, trong khi thuật toán cổ điển chỉ cần 4 phép cộng.

Bây giờ nếu ta thay thế các phần tử trong A và B bằng các ma trận có kích thước n*n, thì để thực hiện phép nhân hai ma trận A và B ta phải thực hiện 7 phép nhân hai ma trận với kích thước n*n và cũng từng đấy phép cộng, trừ của hai ma trận n*n. Nếu ta làm việc với các ma trận lớn thì phép cộng sẽ nhanh hơn rất nhiều so với phép nhân, việc tiết kiệm 1 phép nhân sẽ lợi hơn nhiều so với việc thực hiện các phép cộng cơ bản.

Gọi t(n) là thời gian cần thiết để nhân hai ma trận kích thước n*n bằng cách sử dụng đệ quy hai phương trình 2.3.1 và 2.3.2. Giả sử rằng n là luỹ thừa bậc 2. Do thời gian để tình phép cộng, trừ ma trận là

Do đó ta thấy rằng, có thể nhân hai ma trận kích thước 2*2 bằng cách chỉ sử dụng 7 phép nhân vô hướng. Nhìn thoáng qua thấy rằng thuật toán này không có gì thú vị lắm, nó sử dụng một số lượng lớn các phép cộng và phép trừ, trong khi thuật toán cổ điển chỉ cần 4 phép cộng.

62/129

Bây giờ nếu ta thay thế các phần tử trong A và B bằng các ma trận có kích thước n*n, thì để thực hiện phép nhân hai ma trận A và B ta phải thực hiện 7 phép nhân hai ma trận với kích thước n*n và cũng từng đấy phép cộng, trừ của hai ma trận n*n. Nếu ta làm việc với các ma trận lớn thì phép cộng sẽ nhanh hơn rất nhiều so với phép nhân, việc tiết kiệm 1 phép nhân sẽ lợi hơn nhiều so với việc thực hiện các phép cộng cơ bản.

Gọi t(n) là thời gian cần thiết để nhân hai ma trận kích thước n*n bằng cách sử dụng đệ quy hai phương trình 2.3.1 và 2.3.2. Giả sử rằng n là luỹ thừa bậc 2. Do thời gian để tình phép cộng, trừ ma trận là, do đót ( n ) = 7 t ( n /2) +dn 2, điều này là một ví dụ minh hoạ cho chúng ta trong việc phân tích tổng quát thuật toán chia để trị. áp dụng dụng định lý thợ ta có . Đối với các trường hợp ma trận vuông nhưng kích thước không phải là luỹ thừa bậc 2 thì giải quyết vấn đề bằng cách thêm các dòng và các cột sao cho kích thước ma trận mới gấp đôi kích thước ma trận cũ và gán giá trị cho các phần tử mới thêm là 0. gian tính toán. Do lg7<2,81 nên có thể Điều này không làm ảnh hưởng đến thời thực hiện phép nhân hai ma trận kích thước n*n trong thời gian với điều kiện các phép tính vô hướng là phép tính cơ bản.

Cùng với phát minh của Strassen, có một số nhà nghiên cứu cố gắng tìm kiếm thuật toán để xác định được hằng số ω, khi đó độ phức tạp tính toán phép nhân hai ma trận kích thước n*n là . Để thực hiện được điều này, việc đầu tiên phải tiến hành là nhân hai ma trận kích thước 2*2 với 6 phép nhân cơ bản. Nhưng vào năm 1971 Hopcroft và Kerr đã chứng minh điều này là không thể vì phép nhân hai ma trận không có tính chất giao hoán. Việc tiếp theo phải thực hiện là tìm cách nào để nhân hai ma trận 3*3 với nhiều nhất chỉ 21 phép nhân cơ bản. Nếu thực hiện được việc này có thể sử dụng thuật toán này để suy ra thuật toán đệ quy nhân hai ma trận n*n với thời gian , nhanh hơn thuật toán của Strassen vì . Không may mắn là điều này không thể thực hiện. Trong suốt một thập kỷ trước khi Pan phát hiện ra cách để nhân hai ma trân kích thước 70*70 với 143640 phép nhân cơ bản – so sánh với 343000 phép nhân nếu sử dụng thuật toán cổ điển và quả thực là bé hơn một chút so với lg7. Phát hiện này được gọi là cuộc chiến tranh của số thập phân (decimal war). Nhiều thuật toán, mà trong đó hiệu suất tiệm cận cao, được tìm ra sau đó. Ví dụ như cuối năm 1979, phép nhân ma trận có thời gian tính toán là . Hãy tưởng tượng rằng, ngay sau đó tháng 1 năm 1980 thời gian tính của phép nhân ma trận là . Biểu thức tiệm cận thời gian tính toán tồi nhất của thuật toán nhân ma trận kích thước n*n được Coppersmith và Winograd phát minh ra năm 1986 là . Tại vì các hằng số liên quan bị Nn nên không một thuật toán nào được tìm ra sau thuật toán của Strassen được nghiên cứu và sử dụng.

Giới thiệu về khoa học mật mã

63/129

Trong phần trước chúng ta đã thấy việc rút gọn số mũ trong số các phép nhân cần thiết để tínhankhông tiết kiệm được một cách đáng kể thời gian tính. Tuy nhiên, có những ứng dụng trong đó các phép nhân được coi là có chi phí ngang nhau. Đó là trường hợp khi chúng ta quan tâm đến số học đồng dư, tức là đến các phép toánanchia đồng dư cho một số nguyênz . Chúng ta đã biết rằngxmodzsẽ cho phần dư của phép chia nguyênxchoz . Ví dụ, 25 mod 7 = 4 vì 25 = 3 x 7 + 4. Nếuxvàylà các số nguyên nằm giữa 0 vàz- 1, và nếuzlà một số nguyên có kích thướcm , thì phép tính nhân đồng dưxymodzsẽ bao gồm một phép nhân thường của hai số nguyên có kích thước tối đam , mà kết quả là một số nguyên có kích thước tối đa 2 m , và tiếp theo là một phép chia tích của hai số đó choz , cũng là một số nguyên có kích thước m , kết quả mà chúng ta quan tâm sẽ là phần dư

của phép chia này. Như vậy thời gian cần cho mỗi phép nhân đồng dư phần nào không bị ảnh hưởng bởi giá trị của hai sốxvày . dụng những phân tích trong phần trước với một số thay đổi cần thiết cho phép chúng ta kết luận rằng thuật toán trên chỉ cần một số lượng phép nhân đồng dư vào cỡ (log n) để tínhanmodz . Phân tích một cách chính xác hơn ta thấy số lượng phép nhân đồng dư bằng số Bít trong phép triển khai nhị phân củan , cộng với số Bít 1 trong số những Bít này; tức là vào khoảng 3/2 lgn cho các giá trị đặc trưng củan . Thuật toán tương ứngexposeqđòi hỏin– 1 phép nhân cho tất cả các giá trị củan . Để rõ hơn về điều này, hãy giả dụa ,nvàzlà những số có 200 chữ số và với các số có độ lớn như vậy có thể thực hiện phép nhân đồng dư trong một phần ngàn giây. Thuật toán expomod sẽ tính anmodz trong thời gian ít hơn một giây. Trong khi thuật toánexposeqcần thời giản vào khoảng 10179 lần tuổi của vũ trụ để tínhan .

Trong thực tế, liệu chúng ta có cần tính những lũy thừa đồng dư lớn như vậy hay không? Khoa học mật mã hiện đại, môn khoa học và nghệ thuật của những giao tiếp bí

mật trên những kênh không an toàn, phụ thuộc chủ yếu vào những phép tính này.

Chúng ta hãy xem xét trường hợp sau: Hai người là anh A và chị B trao đổi các thông

điệp với nhau. Giả sử anh A muốn gửi thông điệp cá nhânmcho chị B, nhưng kênh liên lạc lại không an toàn, hay nói một cách khác là dễ dàng bị nghe trộm. Để ngăn không cho những người khác đọc được thông điệp, anh A chuyển nó thành dạng mật mãc , sau đó gửi cho chị B. Việc chuyển đổi này là kết quả của một thuật toán chuyển mã. Đầu ra của nó không những chỉ phụ thuộc vào thông điệpmmà còn phụ thuộc vào

tham biếnk . Chúng ta gọi tham biến này làkhóa . Theo phương pháp kinh điển thì khóa chính là thông tin bí mật được thoả thuận giữa anh A và chị B trước khi họ trao đổi thông điệp với nhau. Nhờ có khoáknên khi nhận được thông điệp (đã mật mã hoá)c , chị B có thể tạo lại thông điệpm . Những hệ thống bí mật kiểu như vậy đều dựa trên nguyên tắc là dù kẻ nghe trộm lấy được thông điệpc , nhưng không biết khóa k thì cũng không thể đọc được nội dung thông điệpm .

64/129

Phương pháp mật mã hoá này được sử dụng với những thành công nhất định trong lịch sử phát triển của nó. Việc đòi hỏi các bên tham gia phải thỏa thuận những thông tin bí mật trước khi tham gia truyền thông có thể chấp nhận được trong giới ngoại giao và quân sự, nhưng khó có thể chấp nhận đối với những người dân bình thường. Trong thời đại siêu tốc điện tử, người ta có nhu cầu truyền thông riêng tư với nhau mà không cần có sự sắp đặt từ trước. Liệu anh A và chị B có thể trao đổi thông tin với nhau một cách bí mật với sự có mặt của những người khác mà không cần thỏa thuận từ trước những quy ước bí mật với nhau? Thế hệ mật mã hóa với khóa công khai đã được khai sinh với ý tưởng của Diffie, Hellman và Merkle về sự khả thi vấn đề trên trong những năm giữa thập kỷ 70 thế kỷ 20. Tiếp theo đây chúng tôi sẽ trình bày một giải pháp độc đáo được

Rivest, Shamir và Adleman đưa ra ít năm sau. Giải pháp nàyn ngày nay được biết dưới cái tên hệ thống mật mã RSA, viết tắt từ tên của những người đã phát minh ra nó.

Xét hai số nguyên tố có 1 trăm chữ sốpvàqđược chọn một cách ngẫu nhiên bởi chị B. Gọizlà tích củapvàq . Chị B có thể tínhzmột cách hiệu quả từpvàq . Cho dù chúng ta sở hữu những máy tính hiện đại bậc nhất, cũng không có cách nào tính đượcpvàqtừzsử dụng những thuật toán đã biết, ngay cả khi chúng ta sử dụng hết cả thời gian của vũ trụ. Gọi ϕ là tích ( p- 1)( q- 1). Gọinlà một số nguyên nằm giữa 1 vàz– 1 được chọn một cách ngẫu nhiên bởi chị B sao cho n và ϕ nguyên tố cùng nhau. (Chị B không cần kiểm tra một cách cụ thể xemncó thỏa mãn điều kiện trên hay không vì chị sẽ nhanh chóng biết được điều đó). Trong số học chúng ta đã biết là chỉ có duy nhất một số nguyên s nằm giữa 1 và z– 1 thỏa mãn điều kiện nsmod = 1. Ngoài ra có thể dễ dàng tính rastừnvà ϕ (xem lời giải bài tập 7.31) đồng thời sự tồn

tại củascòn cho phép kiểm tra xemnvà ϕ có nguyên tố cùng nhau hay không. Nếuskhông tồn tại, chị B cần phải chọn một giá trị ngẫu nhiên khác chon ; xác xuất thành công của mỗi lần chọn đều như nhau. Mấu chốt trong giải pháp được trình bày ở đây là định lý:axmodz=atrong đó 0 ≤a

Để có thể cho phép anh A hoặc ai đó truyền thông riêng tư với mình, chị B phổ biến cho tất cả sự lựa chọn của chị về giá trị củaxvàn , nhưng giữ bí mậts . Gọimlà một thông điệp mà anh A định gửi cho chị B. Sử dụng bộ mã chuNn chẳng hạn như ASCII, anh A chuyển thông điệp của mình thành một chuỗi Bít, được hiểu như là một sốa . Để đơn giản chúng ta giả thiết rằng 0 ≤a

65/129

Bây giờ chúng ta sẽ xét đến hành động của kẻ nghe trộm. Giả sử anh ta nghe được mọi trao đổi giữa anh A và chị B, như vậy anh ta sẽ biếtz ,nvàc . Mục đích của anh ta là xác định giá trị sốamà anh A gửi cho chị B, sốalà số duy nhất nằm giữa 0 vàz– 1 thỏa mãn điều kiệnc=anmodz . Để tính ra a chưa có một thuật toán hiệu quả nào được biết đến: phép tính lũy thừa đồng dư có thể thực hiện một cách hiệu quả với thuật toánexpomodnhưng điều ngược lại hình như không thể thực hiện được. Phương pháp tốt nhất được biết đến hiện nay là: phân tíchzra thành hai thừa số p và q , ( p- 1)( q- 1), tính s và tính a=csmod. Đó chính là cách chị B đã làm. Mỗi bước nêu trên đều khả thi, trừ bước đầu tiên: phân tích một số có 200 chữ số ra thừa số là một việc vượt quá khả năng cho phép của công nghệ hiện nay. Bởi vậy lợi thế của chị B trong việc giải mã chính là ở chỗ chị ta là người duy nhất biết các thừa số củaz , là những số cần thiết để tính ra ϕ

vàs . Chị ta biết được không phải do có tài phân tíchzra thừa số mà do chị ta tính z từ các thừa số được chị ta chọn.

Hiện tại độ chắc chắn của sơ đồ mật mã hóa này vẫn chưa được xác định trên phương diện toán học: Không có chứng minh toán học nào khẳng định việc phân tích ra thừa số là không thể được và cũng không có chứng minh nào khẳng định rằng để phá mã cần phải phân tích ra thừa số. Xét trên phương diện khác thì chúng ta có thể có

những thuật toán có khả năng phân tích thừa số một cách hiệu quả, nhưng chúng lại đòi hỏi những máy tính lượng tử, mà để tạo ra những máy tính đó, thì lại nằm ngoài mtầm của công nghệ hiện tại. Hệ thống mật mã hóa mà chúng tôi mô tả ở trên vẫn được coi là một trong những phát minh sáng giá nhất trong lịch sử khoa học mật mã.

Bài tập chương

Cho mảng số liệu sau:

10, 4, -5, 7, -45, 14, 30, -2, 50

Hãy minh họa các bước của thuật toán để tìm mảng con lớn nhất.

Dành cho độc giả

Cho dãy số liệu

80, 12, 47, 16, 7, 56, 14, 19, 100

Hãy minh họa các bước của thuật toán MergeSort, QuickSort để sắp xếp dãy khóa trên theo thứ tự tăng dần.

Dành cho độc giả

Thiết kế thuật toán nhân 2 số nguyên dương, sử dụng thuật toán chia để trị, trong

đó mỗi số nguyên dương được chia làm ba phần, và tích của hai số đó sẽ tìm được sau 5 phép nhân số này với độ xấp xỉ n/3. Phân tích độ phức tạp tính toán trong

thuật toán thu được

Dành cho độc giả

66/129

Sử dụng các kĩ thuật đánh giá độ phức tạp trong chương 1 để đánh giá độ phức tạp của các thuật toán trong chương 2.

Dành cho độc giả

Xét ma trận

F =

0 1

1 1

Hãy tính thử kết quả của phép nhân ma trận này với vector (i, j). Trong đó i, j là hai số

nguyên. Có gì đặc biệt khi i, j là hai số hạng liên tiếp của dãy Fibonaci? Từ đó xây dựng thuật toán chia để trị để tính các phần tử của dãy số Fibonaci và phân tích độ phức tạp tính toán của thuật toán trong 2 trường hợp

a. Coi mỗi phép toán số học là phép toán cơ bản đòi hỏi một đơn vị thời gian

b. Thời gian tính tích của hai số nguyên có độ dài s và q là : O(sqa-1) (s ³ q).

Lưu ý là độ dài của số Fn cỡ O(n) với số thực a > 1.

67/129

Dành cho độc giả

Quy hoạch động

Công thức truy hồi

Ví dụ

Cho số tự nhiên n ≤ 100. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng của dãy các

số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là một cách.

n = 5 có 7 cách phân tích:

(Lưu ý: n = 0 vẫn coi là có 1 cách phân tích thành tổng các số nguyên dương (0 là tổng của dãy rỗng))

Để giải bài toán này, trong chuyên mục trước ta đã dùng phương pháp liệt kê tất cả các cách phân tích và đếm số cấu hình. Bây giờ ta thử nghĩ xem, cócáchnàotínhngayrasốlượngcáccách phântíchmàkhôngcầnphảiliệtkêhaykhông?. Bởi vì khi số cách phân tích tương đối lớn, phương pháp liệt kê tỏ ra khá chậm. (n = 100 có 190569292 cách phân tích).

Nhận xét:

Nếu gọi F[m, v] là số cách phân tích số v thành tổng các số nguyên dương ≤ m. Khi đó: Các cách phân tích số v thành tổng các số nguyên dương ≤ m có thể chia làm hai loại:

• Loại 1: Không chứa số m trong phép phân tích, khi đó số cách phân tích loại

68/129

này chính là số cách phân tích số v thành tổng các số nguyên dương < m, tức là

số cách phân tích số v thành tổng các số nguyên dương ≤ m - 1 và bằng F[m - 1, v].

• Loại 2: Có chứa ít nhất một số m trong phép phân tích. Khi đó nếu trong các

cách phân tích loại này ta bỏ đi số m đó thì ta sẽ được các cách phân tích số v - m thành tổng các số nguyên dương ≤ m (Lưu ý: điều này chỉ đúng khi không tính lặp lại các hoán vị của một cách). Có nghĩa là về mặt số lượng, số các cách phân tích loại này bằng F[m, v - m]

Trong trường hợp m > v thì rõ ràng chỉ có các cách phân tích loại 1, còn trong trường hợp m ≤ v thì sẽ có cả các cách phân tích loại 1 và loại 2. Vì thế:

• F[m, v] = F[m - 1, v] nếu m > v • F[m, v] = F[m - 1, v] + F[m, v - m] nếu m ≤ v

Ta có công thức xây dựng F[m, v] từ F[m - 1, v] và F[m, v - m]. Công thức này có tên gọi là công thứctruyhồiđưa việc tính F[m, v] về việc tính các F[m', v'] với dữ liệu nhỏ hơn. Tất nhiên cuối

cùng ta sẽ quan tâm đến F[n, n]: Số các cách phân tích n thành tổng các số nguyên dương ≤ n.

Với n = 5, bảng F sẽ là:

Nhìn vào bảng F, ta thấy rằng F[m, v] được tính bằng tổng của:

Một phần tử ở hàng trên: F[m - 1, v] và một phần tử ở cùng hàng, bên trái: F[m, v - m].

F[5, 5] sẽ được tính bằng F[4, 5] + F[5, 0], hay F[3, 5] sẽ được tính bằng F[2, 5] + F[3, 2].

69/129

Chính vì vậy để tính F[m, v] thì F[m - 1, v] và F[m, v - m] phải được tính trước. Suy ra thứ tự hợp lý để tính các phần tử trong bảng F sẽ phải là theo thứ tự từ trên xuống và trên mỗi hàng thì tính theo thứ tự từ trái qua phải.

Điều đó có nghĩa là ban đầu ta phải tính hàng 0 của bảng: F[0, v] = số dãy có các phần tử ≤ 0 mà tổng bằng v, theo quy ước ở đề bài thì F[0, 0] = 1 còn F[0, v] với mọi v > 0 đều là 0.

Vậy giải thuật dựng rất đơn giản: Khởi tạo dòng 0 của bảng F: F[0, 0] = 1 còn F[0, v] với mọi v > 0 đều bằng 0, sau đó dùng công thức truy hồi tính ra tất cả các phần tử của bảng F. Cuối cùng F[n, n] là số cách phân tích cần tìm

PROG01_1.PAS * Đếm số cách phân tích số n

program Analyse1; {Bài toán phân tích số}

const

max = 100;

var

F: array[0..max, 0..max] of LongInt;

n, m, v: Integer;

begin

Write('n = '); ReadLn(n);

FillChar(F[0], SizeOf(F[0]), 0); {Khởi tạo dòng 0 của bảng F toàn số 0}

F[0, 0] := 1; {Duy chỉ có F[0, 0] = 1}

for m := 1 to n do {Dùng công thức tính các dòng theo thứ tự từ trên xuống dưới}

for v := 0 to n do {Các phần tử trên một dòng thì tính theo thứ tự từ trái qua phải}

if v < m then F[m, v] := F[m - 1, v]

else F[m, v] := F[m - 1, v] + F[m, v - m]; WriteLn(F[n, n], ' Analyses');{Cuối cùng F[n, n] là số cách phân tích}

70/129

end.

Cải tiến thứ nhất

Cách làm trên có thể tóm tắt lại như sau: Khởi tạo dòng 0 của bảng, sau đó dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2 v.v... tới khi tính được hết dòng n. Có thể nhận thấy rằng khi đã tính xong dòng thứ k thì việc lưu trữ các dòng từ dòng 0 tới dòng k - 1 là không cần thiết bởi vì việc tính dòng k+ 1 chỉ phụ thuộc các giá trị lưu trữ trên dòng k. Vậy ta có thể dùng hai mảng một chiều: Mảng Current lưu dòng hiện thời đang xét của bảng và mảng Next lưu dòng kế tiếp, đầu tiên mảng Current được gán các giá trị tương ứng trên dòng 0. Sau đó dùng mảng Current tính mảng Next, mảng Next sau khi tính sẽ mang các giá trị tương ứng trên dòng 1. Rồi lại gán mảng Current := Next và tiếp tục dùng mảng Current tính mảng Next, mảng Next sẽ gồm các giá trị tương ứng trên dòng 2 v.v... Vậy ta có cài đặt cải tiến sau:

PROG01_2.PAS * Đếm số cách phân tích số n

program Analyse2;

const

max = 100;

var

Current, Next: array[0..max] of LongInt;

n, m, v: Integer;

begin

Write('n = '); ReadLn(n); FillChar(Current, SizeOf(Current), 0);

Current[0] := 1; {Khởi tạo mảng Current tương ứng với dòng 0 của bảng F}

for m := 1 to n do

begin {Dùng dòng hiện thời Current tính dòng kế tiếp Next → Dùng dòng m - 1 tính dòng m của bảng F}

for v := 0 to n do

if v < m then Next[v] := Current[v]

71/129

else Next[v] := Current[v] + Next[v - m];

Current := Next; {Gán Current := Next tức là Current bây giờ lại lưu các phần tử trên dòng m của bảng F}

end;

WriteLn(Current[n], ' Analyses');

end.

Cách làm trên đã tiết kiệm được khá nhiều không gian lưu trữ, nhưng nó hơi chậm hơn phương

pháp đầu tiên vì phép gán mảng (Current := Next). Có thể cải tiến thêm cách làm này như sau:

PROG01_3.PAS * Đếm số cách phân tích số n

program Analyse3;

const

max = 100;

var

B: array[1..2, 0..max] of LongInt;{Bảng B chỉ gồm 2 dòng thay cho 2 dòng liên tiếp của bảng phương án}

n, m, v, x, y: Integer;

begin

Write('n = '); ReadLn(n);

{Trước hết, dòng 1 của bảng B tương ứng với dòng 0 của bảng phương án F, được điền cơ sở quy hoạch động}

FillChar(B[1], SizeOf(B[1]), 0); B[1][0] := 1;

x := 1; {Dòng B[x] đóng vai trò là dòng hiện thời trong bảng phương án}

y := 2; {Dòng B[y] đóng vai trò là dòng kế tiếp trong bảng phương án}

72/129

for m := 1 to n do begin

{Dùng dòng x tính dòng y → Dùng dòng hiện thời trong bảng phương án để tính dòng kế tiếp}

for v := 0 to n do

if v < m then B[y][v] := B[x][v]

else B[y][v] := B[x][v] + B[y][v - m];

x := 3 - x; y := 3 - y; {Đảo giá trị x và y, tính xoay lại}

end;

WriteLn(B[x][n], ' Analyses');

end.

Cải tiến thứ hai

Ta vẫn còn cách tốt hơn nữa, tại mỗi bước, ta chỉ cần lưu lại một dòng của bảng F bằng một mảng 1 chiều, sau đó dùng mảng đó tính lại chính nó để sau khi tính, mảng một chiều sẽ lưu các giá trị của bảng F trên dòng kế tiếp.

PROG01_4.PAS * Đếm số cách phân tích số n

program Analyse4;

const

max = 100;

var

L: array[0..max] of LongInt; {Chỉ cần lưu 1 dòng}

n, m, v: Integer;

begin

Write('n = '); ReadLn(n); FillChar(L, SizeOf(L), 0);

L[0] := 1; {Khởi tạo mảng 1 chiều L lưu dòng 0 của bảng}

73/129

for m := 1 to n do {Dùng L tính lại chính nó}

for v := m to n do

L[v] := L[v] + L[v - m]; WriteLn(L[n], ' Analyses');

end.

Bài tập:

Kết hợp với chương trình phân tích số dùng thuật toán quay lui, kiểm tra tính đúng đắn của công thức truy hồi trên với n ≤ 30.

Dành cho độc giả

Hãy cho biết có bao nhiêu cách phân tích số nguyên dương n ≤ 1000 thành tổng của những số nguyên dương khác nhau đôi một, các cách phân tích là hoán vị của nhau chỉ tính là một cách.

Dành cho độc giả

Công thức truy hồi trên có thể tính bằng hàm đệ quy như trong chương trình sau:

program Analyse5;

var

n: Integer;

function F(m, v: Integer): LongInt;

begin

if m = 0 then

if v = 0 then F := 1

else F := 0

else

if m > v then F := F(m - 1, v)

else F := F(m - 1, v) + F(m, v - m);

74/129

end;

begin

Write('n = '); ReadLn(n); WriteLn(F(n, n), ' Analyses');

end.

Hãy thử với những giá trị n ≤ 50 và giải thích tại sao phương pháp này tuy có nhanh hơn phương pháp duyệt đếm nhưng cũng không thể nào hiệu quả bằng ba cách cài đặt trước. Nếu giải thích được thì những điều nói sau đây trở nên hết sức đơn giản.

Dành cho độc giả

Phương pháp quy hoạch động

Bài toán quy hoạch

Bài toán quy hoạch là bài toán tối ưu :gồm có một hàm f gọi là hàm mục tiêu hay hàm đánh giá; các hàm g1, g2, ..., gn cho giá trị logic gọi là hàm ràng buộc. Yêu cầu của bài toán là tìm một cấu hình x thoả mãn tất cả các ràng buộc g1, g2, ...gn: gi(x) = TRUE (∀i: 1 ≤ i ≤ n) và x là tốt nhất, theo nghĩa không tồn tại một cấu hình y nào khác thoả mãn các hàm ràng buộc mà f(y) tốt hơn f(x).

Tìm (x, y) để

Hàm mục tiêu : x + y → max

Hàm ràng buộc : x2 + y2 ≤ 1.

Xét trong mặt phẳng toạ độ, những cặp (x, y) thoả mãn x2 + y2 ≤ 1 là tọa độ của những điểm nằm trong hình tròn có tâm O là gốc toạ độ, bán kính 1. Vậy nghiệm của bài toán bắt buộc nằm trong hình tròn đó.

Những đường thẳng có phương trình: x + y = C (C là một hằng số) là đường thẳng vuông góc với đường phân giác góc phần tư thứ nhất. Ta phải tìm số C lớn nhất mà đường thẳng x + y = C vẫn điểm chúng với đường tròn (O, 1). Đường thẳng đó là một tiếp tuyến của đường tròn:

x +y= √2

√2, 1

√2) tương ứng với nghiệm tối ưu của bài toán đã cho.

75/129

Tiếp điểm( 1

Các dạng bài toán quy hoạch rất phong phú và đa dạng, ứng dụng nhiều trong thực tế, nhưng cũng cần biết rằng, đa số các bài toán quy hoạch là không giải được, hoặc chưa giải được. Cho đến nay, người ta mới chỉ có thuật toán đơn hình giải bài toán quy hoạch tuyến tính lồi, và một vài thuật toán khác áp dụng cho các lớp bài toán cụ thể.

Phương pháp quy hoạch động

Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy chúng ta đã tìm hiểu, nguyên lý chia để trị (divide and conquer) thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó làm nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên lý này càng được thể hiện rõ: Khi không biết cần phải giải quyết những bài toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưutrữnhữnglờigiảihayđápsốcủa chúngvới mục đích sửdụnglạitheo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy và cũng là nội dung phương pháp quy hoạch động:

• Phép phân giải đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán

con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa.

• Quy hoạch động bắt đầu từ việcgiải tất cả các bài toán nhỏ nhất ( bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu).

Ta xét một ví dụ đơn giản:

Dãy Fibonacci là dãy số nguyên dương được định nghĩa như sau: F1 = F2 = 1;

76/129

∀ i: 3 ≤ i: Fi = Fi-1 + Fi-2

Hãy tính F6

Xét hai cách cài đặt chương trình:

Cách 1

program Fibo1;

function F(i: Integer): Integer;

begin

if i < 3 then F := 1

else F := F(i - 1) + F(i - 2);

end;

begin

WriteLn(F(6));

end.

Cách 2

program Fibo2;

var

F: array[1..6] of Integer;

i: Integer;

begin

F[1] := 1; F[2] := 1;

for i := 3 to 6 do

F[i] := F[i - 1] + F[i - 2]; WriteLn(F[6]);

77/129

end.

Trong cách 1, ta viết một hàm đệ quy F(i) để tính số Fibonacci thứ i. Chương trình chính gọi F(6), nó sẽ gọi tiếp F(5) và F(4) để tính ... Quá trình tính toán có thể vẽ như cây dưới đây. Ta nhận thấy để tính F(6) nó phải tính 1 lần F(5), hai lần F(4), ba lần F(3), năm lần F(2), ba lần F(1).

Cách 2 thì không như vậy. Trước hết nó tính sẵn F[1] và F[2], từ đó tính tiếp F[3], lại tính tiếp được F[4], F[5], F[6]. Đảm bảo rằng mỗi giá trị Fibonacci chỉ phải tính 1 lần. (Cách 2 còn có thể cải tiến thêm nữa, chỉ cần dùng 3 giá trị tính lại lẫn nhau)

Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương pháp đó có thoả mãn những yêu cầu dưới đây hay không:

• Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối hợp lời

giải của các bài toán con đó cho ta lời giải của bài toán lớn.

• Vì quy hoạch động là đi giải tất cả các bài toán con, nên nếu không đủ không gian vật lý lưu trữ lời giải (bộ nhớ, đĩa...) để phối hợp chúng thì phương pháp quy hoạch động cũng không thể thực hiện được.

• Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn

bước.

Các khái niệm:

• Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy hoạch

động

• Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn

gọi là công thức truy hồi của quy hoạch động

• Tập các bài toán nhỏ nhất có ngay lời giải để từ đó giải quyết các bài toán lớn

hơn gọi là cơ sở quy hoạch động

• Không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng gọi là

bảngphươngán của quy hoạch động

78/129

Các bước cài đặt một chương trình sử dụng quy hoạch động: (nhớ kỹ)

• Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu các lời giải vào bảng

phương án.

• Dùng công thức truy hồi phối hợp những lời giải của những bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của những bài toán lớn hơn và lưu chúng vào bảng phương án. Cho tới khi bài toán ban đầu tìm được lời giải.

• Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.

Một số bài toán quy hoạch động

Dãy con đơn điệu tăng dài nhất

Cho dãy số nguyên A = a1, a2, ..., an. (n ≤ 10000, -10000 ≤ ai ≤ 10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có 2n dãy con.

Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất.

A = (1, 2, 3, 4, 9, 10, 5, 6, 7, 8). Dãy con đơn điệu tăng dài nhất là: (1, 2, 3, 4, 5, 6, 7, 8). Dữ liệu (Input) vào từ file văn bản INCSEQ.INP

• Dòng 1: Chứa số n • Dòng 2: Chứa n số a1, a2, ..., an cách nhau ít nhất một dấu cách

Kết quả (Output) ghi ra file văn bản INCSEQ.OUT

• Dòng 1: Ghi độ dài dãy con tìm được • Các dòng tiếp: ghi dãy con tìm được và chỉ số những phần tử được chọn vào

dãy con đó.

79/129

Cách giải:

sung vào A hai -∞ và an+1 phần = = +∞. ao

Bổ tử: Khiđódãyconđơnđiệutăngdàinhấtchắc chắn sẽ bắt đầu từ a0và kết thúc ở an+1.

Với ∀ i: 0 ≤ i ≤ n + 1. Ta sẽ tính L[i] = độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại ai.

Cơ sở quy hoạch động (bài toán nhỏ nhất):

L[n + 1] = Độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại an+1 = +∞. Dãy con này chỉ gồm mỗi một phần tử (+∞) nên L[n + 1] = 1.

Công thức truy hồi:

Giả sử với i từ n đến 0, ta cần tính L[i]: độ dài dãy con tăng dài nhất bắt đầu tại ai. L[i] được tính trong điều kiện L[i + 1], L[i + 2], ..., L[n + 1] đã biết:

Dãy con đơn điệu tăng dài nhất bắt đầu từ ai sẽ được thành lập bằng cách lấy ai ghép vào đầu một trong số những dãy con đơn điệu tăng dài nhất bắt đầu tại vị trí aj đứng sau ai. Ta sẽ chọn dãy nào

để ghép ai vào đầu? Tất nhiên là chỉ được ghép ai vào đầu những dãy con bắt đầu tại aj nào đó lớn hơn ai (để đảm bảo tính tăng) và dĩ nhiên ta sẽ chọn dãy dài nhất để ghép ai vào đầu (để đảm bảo tính dài nhất). Vậy L[i] được tính như sau: Xéttấtcảcácchỉsốjtrongkhoảngtừi+1đếnn+1

mà a j > a i , chọn ra chỉ số jmax có L[jmax] lớn nhất. Đặt L[i] := L[jmax] + 1.

Truy vết

Tại bước xây dựng dãy L, mỗi khi tính L[i] := L[jmax] + 1, ta đặt T[i] = jmax. Để lưu lại rằng: Dãy con dài nhất bắt đầu tại ai sẽ có phần tử thứ hai kế tiếp là ajmax.

Sau khi tính xong hay dãy L và T, ta bắt đầu từ 0. T[0] là phần tử đầu tiên được chọn,

T[T[0]] là phần tử thứ hai được chọn,

T[T[T[0]]] là phần tử thứ ba được chọn ...Quá trình truy vết có thể diễn tả như sau:

i := T[0];

while i <> n + 1 do {Chừng nào chưa duyệt đến số an+1=+∞ ở cuối}

80/129

begin

i := T[i];

end;

với A = (5, 2, 3, 4, 9, 10, 5, 6, 7, 8). Hai dãy L và T sau khi tính sẽ là:

PROG03_1.PAS * Tìm dãy con đơn điệu tăng dài nhất

program LongestSubSequence;

const

max = 10000;

var

a, L, T: array[0..max + 1] of Integer;

n: Word;

procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn theo đúng khuôn dạng Input}

var

i: Word;

begin

ReadLn(n);

for i := 1 to n do Read(a[i]);

81/129

end;

procedure Optimize; {Quy hoạch động}

var

i, j, jmax: Word;

begin

a[0] := -32768; a[n + 1] := 32767; {Thêm hai phần tử canh hai đầu dãy a}

L[n + 1] := 1; {Điền cơ sở quy hoach động vào bảng phương án}

for i := n downto 0 do {Tính bảng phương án}

begin

{Chọn trong các chỉ số j đứng sau i thoả mãn aj > ai ra chỉ số jmax có L[jmax] lớn nhất}

jmax := n + 1;

for j := i + 1 to n + 1 do

if (a[j] > a[i]) and (L[j] > L[jmax]) then jmax := j;

1; {Lưu độ dài dãy con tăng dài nhất bắt đầu tại ai} L[i] := L[jmax] +

T[i] := jmax; {Lưu vết: phần tử đứng liền sau ai trong dãy con tăng dài nhất đó là ajmax}

end;

WriteLn(L[0] - 2);{Chiều dài dãy con tăng dài nhất}

i := T[0]; {Bắt đầu truy vết tìm nghiệm}

while i <> n + 1 do begin

WriteLn('a[', i, '] = ', a[i]);

i := T[i];

82/129

end;

end;

begin

{Định nghĩa lại thiết bị nhập/xuất chuẩn}

'INCSEQ.INP'); Reset(Input); Assign(Output, 'INCSEQ.OUT');

Assign(Input, Rewrite(Output); Enter;

Optimize;

Close(Input); Close(Output);

end.

Nhận xét:

1. Ta có thể làm cách khác: Gọi L[i] là độ dài dãy con dài nhất kết thúc tại a[i], T[i] là chỉ số đứng liền trước ai trong dãy con dài nhất đó. Cách này khi truy vết sẽ cho thứ tự các chỉ số được chọn giảm dần.

2. Dùng mảng T lưu vết để có chương trình ngắn gọn chứ thực ra không cần có nó

vẫn có thể dò lại được nghiệm, chỉ cần dùng mảng L mà thôi.

Bài tập

Trong cách giải trên, đâu là bảng phương án:

a) Mảng L? b) mảng T? c) cả mảng L và mảng T?

Dành cho độc giả

Vẫn giữ nguyên giả thiết và kích cỡ dữ liệu như trên hãy lập chương trình trả lời câu hỏi:

a) Có bao nhiêu dãy con đơn điệu tăng dài nhất ?

b) Cho biết tất cả những dãy con đơn điệu tăng dài nhất đó

Dành cho độc giả

Bài toán cái túi

83/129

Trong siêu thị có n gói hàng (n ≤ 100), gói hàng thứ i có trọng lượng là Wi ≤ 100 và trị giá Vi ≤ 100. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể

mang được tối đa trọng lượng M ( M ≤ 100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất.

Input: file văn bản BAG.INP

- Dòng 1: Chứa hai số n, M cách nhau ít nhất một dấu cách

- n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương Wi, Vi cách nhau ít nhất một dấu cách

Output: file văn bản BAG.OUT

- Dòng 1: Ghi giá trị lớn nhất tên trộm có thể lấy

- Dòng 2: Ghi chỉ số những gói bị lấy

BAG.INP BAG.OUT

5 113 34 45 49 104 4 115 2 1

Cách giải:

Nếu gọi F[i,j]làgiátrịlớnnhấtcóthểcóbằng cách chọn trong các gói {1, 2, ..., i} với giới hạn trọng lượng j. Thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F[n, M].

Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, ...,i - 1, i} để có giá trị lớn nhất sẽ có hai khả năng:

• Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn

trong số các gói {1, 2, ..., i - 1} với giới hạn trọng lượng là j. Tức là F[i, j] = F[i - 1, j]

• Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà Wi ≤ j) thì F[i, j] bằng giá trị gói thứ i là Vi cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1, 2, ..., i - 1} với giới hạn trọng lượng j - Wi. Tức là về mặt giá trị thu được: F[i, j] = Vi + F[i - 1, j - Wi]

• Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là max

trong 2 giá trị thu được ở trên.

Cơ sở quy hoạch động:

84/129

Dễ thấy F[0, j] = giá trị lớn nhất có thể bằng cách chọn trong số 0 gói = 0.

Tính bảng phương án:

Bảng phương án F gồm n + 1 dòng, M + 1 cột, trước tiên được điền cơ sở quy hoạch động: Dòng 0 gồm toàn số 0. Sử dụng công thức truy hồi, dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2, v.v... đến khi tính hết dòng n.

Truy vết:

Tính xong bảng phương án thì ta quan tâm đến F[n, M] đó chính là giá trị lớn nhất thu được khi chọn trong cả n gói với giới hạn trọng lượng M. Nếu F[n, M] = F[n - 1, M] thì tức là không chọn gói thứ n, ta truy tiếp F[n - 1, M]. Còn nếu F[n, M] ≠ F[n - 1, M] thì ta thông báo rằng phép chọn tối

ưu có chọn gói thứ n và truy tiếp F[n - 1, M - Wn]. Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án.

program The_Bag;

const

max = 100;

var

PROG03_2.PAS * Bài toán cái túi

W, V: Array[1..max] of Integer;

F: array[0..max, 0..max] of Integer;

n, M: Integer;

procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn (Input)}

var

i: Integer;

begin

ReadLn(n, M);

85/129

for i := 1 to n do ReadLn(W[i], V[i]);

end;

procedure Optimize; {Tính bảng phương án bằng công thức truy hồi}

var

i, j: Integer;

begin

FillChar(F[0], SizeOf(F[0]), 0); {Điền cơ sở quy hoạch động}

for i := 1 to n do for j := 0 to M do

begin {Tính F[i, j]}

F[i, j] := F[i - 1, j]; {Giả sử không chọn gói thứ i thì F[i, j] = F[i - 1, j]}

{Sau đó đánh giá: nếu chọn gói thứ i sẽ được lợi hơn thì đặt lại F[i, j]}

if (j >= W[i]) and

(F[i, j] < F[i - 1, j - W[i]] + V[i]) then

F[i, j] := F[i - 1, j - W[i]] + V[i];

end;

end;

procedure Trace; {Truy vết tìm nghiệm tối ưu}

begin

WriteLn(F[n, M]); {In ra giá trị lớn nhất có thể kiếm được}

while n <> 0 do {Truy vết trên bảng phương án từ hàng n lên hàng 0}

begin

if F[n, M] <> F[n - 1, M] then {Nếu có chọn gói thứ n}

86/129

begin

Write(n, ' ');

M := M - W[n]; {Đã chọn gói thứ n rồi thì chỉ có thể mang thêm được trọng lượng M - Wn nữa thôi}

end; Dec(n);

end;

end;

begin

{Định nghĩa lại thiết bị nhập/xuất chuẩn}

'BAG.INP'); Reset(Input); Assign(Output, 'BAG.OUT');

Assign(Input, Rewrite(Output); Enter;

Optimize;

Trace;

Close(Input); Close(Output);

end.

Biến đổi xâu

Cho xâu ký tự X, xét 3 phép biến đổi:

a) Insert(i, C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu X.

b) Replace(i, C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X bởi ký tự C.

c) Delete(i): i là số, Phép Delete xoá ký tự tại vị trí i của xâu X.

Yêu cầu: Cho trước xâu Y, hãy tìm một số ít nhất các phép biến đổi trên để biến xâu X thành xâu Y.

Input: file văn bản STR.INP

87/129

• Dòng 1: Chứa xâu X (độ dài ≤ 100) • Dòng 2: Chứa xâu Y (độ dài ≤ 100)

Output: file văn bản STR.OUT ghi các phép biến đổi cần thực hiện và xâu X tại mỗi phép biến đổi.

Cách giải:

Đối với xâu ký tự thì việc xoá, chèn sẽ làm cho các phần tử phía sau vị trí biến đổi bị đánh chỉ số lại, gây khó khăn cho việc quản lý vị trí. Để khắc phục điều này, ta sẽ tìm một thứ tự biến đổi thoả mãn: Phép biến đổi tại vị trí i bắt buộc phải thực hiện sau các phép biến đổi tại vị trí i + 1, i + 2, ...

X = 'ABCD';

Insert(0, E) sau đó Delete(4) cho ra X = 'EABD'. Cách này không tuân thủ nguyên tắc Delete(3) sau đó Insert(0, E) cho ra X = 'EABD'. Cách này tuân thủ nguyên tắc đề ra. Nói tóm lại ta sẽ tìm một dãy biến đổi có vị trí thực hiện giảm dần.

Công thức truy hồi

Giả sử m là độ dài xâu X và n là độ dài xâu Y. Gọi F[i, j] là số phép biến đổi tối thiểu để biến xâu gồm i ký tự đầu của xâu X: X1X2 ... Xi thành xâu gồm j ký tự đầu của xâu Y: Y1Y2...Yj.

Ta nhận thấy rằng X = X1X2...Xm và Y = Y1Y2...Yn nên:

- Nếu Xm = Yn thì ta chỉ cần biến đoạn X1X2...Xm-1 thành Y1Y2...Yn-1 tức là trong trường hợp này F[m, n] = F[m - 1, n - 1].

- Nếu Xm ≠ Yn thì tại vị trí Xm ta có thể sử dụng một trong 3 phép biến đổi:

88/129

a) Hoặc chèn vào sau vị trí m của X, một ký t ự đúng bằng Y n :

Thì khi đó F[m, n] sẽ bằng 1 phép chèn vừa rồi cộng với số phép biến đổi biến dãy X1...Xm thành dãy Y1...Yn-1: F[m, n] = 1 + F[m, n - 1]

b) Hoặc thay vị t r í m của X bằng m ộ t ký tự đúng bằng Y n

Thì khi đó F[m, n] sẽ bằng 1 phép thay vừa rồi cộng với số phép biến đổi biến dãy X1...Xm-1 thành dãy Y1...Yn-1: F[m, n] = 1 + F[m-1, n - 1]

c) Hoặc xoá vị t r í thứ m của X

Thì khi đó F[m, n] sẽ bằng 1 phép xoá vừa rồi cộng với số phép biến đổi biến dãy X1...Xm-1 thành dãy Y1...Yn: F[m, n] = 1 + F[m-1, n]

Vì F[m, n] phải là nhỏ nhất có thể, nên trong trường hợp Xm ≠ Ynthì

F[m, n] = min(F[m, n - 1], F[m - 1, n - 1], F[m - 1, n]) + 1. Ta xây dựng xong công thức truy hồi.

Cơ sở quy hoạch động

• F[0, j] là số phép biến đổi biến xâu rỗng thành xâu gồm j ký tự đầu của F. Nó

cần tối thiểu j phép chèn: F[0, j] = j

• F[i, 0] là số phép biến đổi biến xâu gồm i ký tự đầu của S thành xâu rỗng, nó

cần tối thiểu i phép xoá: F[i, 0] = i

Vậy đầu tiên bảng phương án F (cỡ[0..m, 0..n]) được khởi tạo hàng 0 và cột 0 là cơ sở quy hoạch động. Từ đó dùng công thức truy hồi tính ra tất cả các phần tử bảng B. Sau khi tính xong thì F[m, n] cho ta biết số phép biến đổi tối thiểu.

Truy vết:

• Nếu Xm = Yn thì chỉ việc xét tiếp F[m - 1, n - 1]. • Nếu không, xét 3 trường hợp: • Nếu F[m, n] = F[m, n - 1] + 1 thì phép biến đổi đầu tiên được sử dụng là:

Insert(m, Yn)

• Nếu F[m, n] = F[m - 1, n - 1] + 1 thì phép biến đổi đầu tiên được sử dụng là:

Replace(m, Yn)

• Nếu F[m, n] = F[m - 1, n] + 1 thì phép biến đổi đầu tiên được sử dụng là:

89/129

Delete(m)

Lưu ý: khi truy vết, để tránh truy nhập ra ngoài bảng, nên tạo viền cho bảng.

PROG03_3.PAS * Biến đổi xâu

program StrOpt;

const

max = 100;

var

X, Y: String[2 * max];

F: array[-1..max, -1..max] of Integer;

m, n: Integer;

procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn}

begin

ReadLn(X); ReadLn(Y);

m := Length(X); n := Length(Y);

end;

function Min3(x, y, z: Integer): Integer; {Cho giá trị nhỏ nhất trong 3 giá trị x, y, z}

var

t: Integer;

begin

if x < y then t := x else t := y;

if z < t then t := z; Min3 := t;

end;

90/129

procedure Optimize;

var

i, j: Integer;

begin

{Khởi tạo viền cho bảng phương án}

for i := 0 to m do F[i, -1] := max + 1;

for j := 0 to n do F[-1, j] := max + 1;

{Lưu cơ sở quy hoạch động}

for j := 0 to n do F[0, j] := j;

for i := 1 to m do F[i, 0] := i;

{Dùng công thức truy hồi tính toàn bảng phương án}

for i := 1 to m do for j := 1 to n do

if X[i] = Y[j] then F[i, j] := F[i - 1, j - 1]

else F[i, j] := Min3(F[i, j - 1], F[i - 1, j - 1], F[i - 1, j]) + 1;

end;

procedure Trace; {Truy vết}

begin

WriteLn(F[m, n]); {F[m, n] chính là số ít nhất các phép biến đổi cần thực hiện}

while (m <> 0) or (n <> 0) do {Vòng lặp kết thúc khi m = n = 0}

if X[m] = Y[n] then {Hai ký tự cuối của 2 xâu giống nhau}

end;

begin

Dec(m); Dec(n);{Chỉ việc truy chéo lên trên bảng phương án}

91/129

end

else {Tại đây cần một phép biến đổi}

begin

Write(X, ' -> '); {In ra xâu X trước khi biến đổi}

if F[m, n] = F[m, n - 1] + 1 then {Nếu đây là phép chèn}

begin

Write('Insert(', m, ', ', Y[n], ')'); Insert(Y[n], X, m + 1);

Dec(n); {Truy sang phải}

end else

if F[m, n] = F[m - 1, n - 1] + 1 then {Nếu đây là phép thay}

begin

Write('Replace(', m, ', ', Y[n], ')'); X[m] := Y[n];

Dec(m); Dec(n); {Truy chéo lên trên}

end

else {Nếu đây là phép xoá}

begin

Write('Delete(', m, ')'); Delete(X, m, 1);

Dec(m); {Truy lên trên}

end;

WriteLn(' -> ', X); {In ra xâu X sau phép biến đổi}

end;

begin

92/129

Assign(Input, 'STR.INP'); Reset(Input); Assign(Output, 'STR.OUT'); Rewrite(Output); Enter;

Optimize; Trace;

Close(Input); Close(Output);

end.

Bài này giải với các xâu ≤ 100 ký tự, nếu lưu bảng phương án dưới dạng mảng cấp phát động thì có

thể làm với các xâu 255 ký tự. (Tốt hơn nên lưu mỗi dòng của bảng phương án là một mảng cấp phát động 1 chiều). Hãy tự giải thích tại sao khi giới hạn độ dài dữ liệu là 100, lại phải khai báo X và Y là String[200] chứ không phải là String[100] ?.

Dãy con có tổng chia hết cho k

Cho một dãy gồm n ( n ≤ 1000) số nguyên dương A1, A2, ..., An và số nguyên dương k (k ≤ 50). Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các phần tử của dãy con này chia hết cho k.

Cách giải:

Đề bài yêu cầu chọn ra một số tối đa các phần tử trong dãy A để được một dãy có tổng chia hết cho k, ta có thể giải bài toán bằng phương pháp duyệt tổ hợp bằng quay lui có đánh giá nhánh cận nhằm giảm bớt chi phí trong kỹ thuật vét cạn. Dưới đây ta trình bày phương pháp quy hoạch động:

Nhận xét 1: Không ảnh hưởng đến kết quả cuối cùng, ta có thể đặt: Ai := Ai mod k với ∀i: 1 ≤ i ≤ n

Nhậnxét2:Gọi S là tổng các phần tử trong mảng A, ta có thể thay đổi cách tiếp cận bài toán: thay

vì tìm xem phải chọn ra một số tối đa những phần tử để có tổng chia hết cho k, ta sẽ chọn ra một số

tối thiểu các phần tử có tổng đồng dư với S theo modul k. Khi đó chỉ cần loại bỏ những phần tử này thì những phần tử còn lại sẽ là kết quả.

Nhận xét 3: Số phần tử tối thiểu cần loại bỏ bao giờ cũng nhỏ hơn k

Thật vậy, giả sử số phần tử ít nhất cần loại bỏ là m và các phần tử cần loại bỏ là Ai1, Ai2, ..., Aim.

93/129

Các phần tử này có tổng đồng dư với S theo mô-đun k. Xét các dãy sau

Dãy 0 := () = Dãy rỗng (Tổng 0 (mod k)) Dãy 1 := (Ai1)

Dãy 2 := (Ai1, Ai2)

Dãy 3 := (Ai1, Ai2, Ai3)

... ...

Dãy m := (Ai1, Ai2, ..., Aim)

Như vậy có m + 1 dãy, nếu m ≥ k thì theo nguyên lý Dirichlet sẽ tồn tại hai dãy có tổng đồng dư

theo mô-đun k. Giả sử đó là hai dãy:

Ai1 + Ai2 + ... + Aip Ai1 + Ai2 + ... + Aip + Aip+1+ ... + Aiq(mod k)

Suy ra Aip+1 +...+Aiq chia hết cho k. Vậy ta có thể xoá hết các phần tử này trong dãy đã chọn mà vẫn được một dãy có tổng đồng dư với S theo modul k, mâu thuẫn với giả thiết là dãy đã chọn có số phần tử tối thiểu.

Công thức truy hồi:

Nếu ta gọi F[i, t] là số phần tử tối thiểu phải chọn trong dãy A1, A2, ..., Ai để có tổng chia k dư t. Nếu không có phương án chọn ta coi F[m, t] = +∞ . Khi đó F[m, t] được tính qua công thức truy hồi sau:

• Nếu trong dãy trên không phải chọn Am thì F[m, t] = F[m - 1, t]; • Nếu trong dãy trên phải chọn Am thì F[m, t] = 1 + F[m - 1, t - Am] (t - Am ở đây hiểu là phép trừ trên các lớp đồng dư mod k. Ví dụ khi k = 7 thì 1 - 3 = 5) Từ trên suy ra F[m, t] = min (F[m - 1, t], 1 + F[m - 1, t - Am]).

Còn tất nhiên, cơ sở quy hoạch động: F(0, 0) = 0; F(0, i) = + ∞ (với ∀i: 1 ≤ i < k).

Bảng phương án F có kích thước [0..n, 0.. k - 1] tối đa là 1001x50 phần tử kiểu Byte.

Đến đây thì vấn đề trở nên quá dễ, thiết nghĩ cũng không cần nói thêm mà cũng chẳng cần phải viết chương trình ra làm gì nữa.

Phép nhân tổ hợp dãy ma trận

94/129

Với ma trận A kích thước p x q và ma trận B kích thước q x r. Người ta có phép nhân hai ma trận đó

để được ma trận C kích thước pxr. Mỗi phần tử của ma trận C được tính theo công thức:

Cij = ∑k = 1

q AikBkj(∀i, j: 1 ≤ i ≤ p; 1 ≤ j ≤ r)

A là ma trận kích thước 3x4, B là ma trận kích thước 4x5 thì C sẽ là ma trận kích thước 3x5

Để thực hiện phép nhân hai ma trận A(mxn) và B(nxp) ta có thể làm như đoạn chương trình sau:

for i := 1 to p do for j := 1 to r do

begin

c ij := 0;

for k := 1 to q do c ij := c ij + a ik * b kj ;

end;

Phí tổn để thực hiện phép nhân này có thể đánh giá qua số phép nhân, để nhân hai ma trận A(pxq) và B(qxr) ta cần thực hiện p.q.r phép nhân số học.

Phép nhân ma trận không có tính chất giao hoán nhưng có tính chất kết hợp

(A * B) * C = A * (B * C)

Vậy nếu A là ma trận cấp 3x4, B là ma trận cấp 4x10 và C là ma trận cấp 10x15 thì:

• Để tính (A * B) * C, ta thực hiện (A * B) trước, được ma trận X kích thước

3x10 sau 3.4.10 = 120 phép nhân số. Sau đó ta thực hiện X * C được ma trận kết quả kích thước 3x15 sau 3.10.15 = 450 phép nhân số. Vậy tổng số phép nhân số học phải thực hiện sẽ là 570.

• Để tính A * (B * C), ta thực hiện (B * C) trước, được ma trận Y kích thước

95/129

4x15 sau 4.10.15 = 600 phép nhân số. Sau đó ta thực hiện A * Y được ma trận kết quả kích thước 3x15 sau 3.4.15 = 180 phép nhân số. Vậy tổng số phép nhân số học phải thực hiện sẽ là 780.

Vậy thì trình tự thực hiện có ảnh hưởng lớn tới chi phí. Vấn đề đặt ra là tính số phí tổn ít nhất khi thực hiện phép nhân một dãy các ma trận:

M1 * M2 * ... * Mn

Với :

M1 là ma trận kích thước a1 x a2

M2 là ma trận kích thước a2 x a3

...

Mn là ma trận kích thước an x an+1

Input: file văn bản MATRIXES.INP

• Dòng 1: Chứa số nguyên dương n ≤ 100 • Dòng 2: Chứa n + 1 số nguyên dương a1, a2, ..., an+1 (∀i: 1 ≤ ai ≤ 100) cách nhau ít nhất một dấu cách

Output: file văn bản MATRIXES.OUT

• Dòng 1: Ghi số phép nhân số học tối thiểu cần thực hiện • Dòng 2: Ghi biểu thức kết hợp tối ưu của phép nhân dãy ma trận

Trước hết, nếu dãy chỉ có một ma trận thì chi phí bằng 0, tiếp theo ta nhận thấy để nhân một cặp ma trận thì không có chuyện kết hợp gì ở đây cả, chi phí cho phép nhân đó là tính được ngay. Vậy thì phí tổn cho phép nhân hai ma trận liên tiếp trong dãy là hoàn toàn có thể ghi nhận lại được. Sử dụng những thông tin đã ghi nhận để tối ưu hoá phí tổn nhân những bộ ba ma trận liên tiếp ... Cứ tiếp tục như vậy cho tới khi ta tính được phí tổn nhân n ma trận liên tiếp.

Công thức truy hồi:

Gọi F[i, j] là số phép nhân tối thiểu cần thực hiện để nhân đoạn ma trận liên tiếp: Mi*Mi+1*...*Mj. Thì khi đó F[i, i] = 0 với ∀i.

Để tính Mi * Mi+1 * ... * Mj, ta có thể có nhiều cách kết hợp:

96/129

Mi * Mi+1 * ... * Mj = (Mi * Mi+1 * ... * Mk) * (Mk+1 * Mk+2 * ... * Mj) (Với i ≤ k < j)

Với một cách kết hợp (phụ thuộc vào cách chọn vị trí k), chi phí tối thiểu phải thực hiện bằng:

• Chi phí thực hiện phép nhân Mi * Mi+1 * ... * Mk = F[i, k] • Cộng với chi phí thực hiện phép nhân Mk+1 * Mk+2 * ... * Mj = F[k + 1, j] • Cộng với chi phí thực hiện phép nhân hai ma trận cuối cùng: ma trận tạo thành từ phép nhân (Mi * Mi+1 * ... * Mk) có kích thước ai x ak+1 và ma trận tạo thành từ phép nhân (Mk+1 * Mk+2 * ... * Mj) có kích thước ak+1 x aj+1, vậy chi phí này là ai * ak+1 * aj+1.

Từ đó suy ra: do có nhiều cách kết hợp, mà ta cần chọn cách kết hợp để có chi phí ít nhất nên ta sẽ cực tiểu hoá F[i, j] theo công thức:

(F[i.k] + F[k + 1,j] + ai * ak-1 * aj-1 ) F[i , j]= min i ≤ k < j

Tính bảng phương án

Bảng phương án F là bảng hai chiều, nhìn vào công thức truy hồi, ta thấy F[i, j] chỉ được tính khi mà F[i, k] cũng như F[k + 1, j] đều đã biết. Tức là ban đầu ta điền cơ sở quy hoạch động vào đường chéo chính của bảng(F[i, i] = 0), từ đó tính các giá trị thuộc đường chéo nằm phía trên (Tính các F[i, i + 1]), rồi lại tính các giá trị thuộc đường chéo nằm phía trên nữa (F[i, i + 2]) ... Đến khi tính được F[1, n] thì dừng lại

Tìm cách kết hợp tối ưu

Tại mỗi bước tính F[i, j], ta ghi nhận lại điểm k mà cách tính (Mi * Mi+1 * ... * Mk) * (Mk+1 * Mk+2 * ... * Mj) cho số phép nhân số học nhỏ nhất, chẳng hạn ta đặt T[i, j] = k. Khi đó, muốn in ra phép kết hợp tối ưu để nhân đoạn Mi * Mi+1 * ... * Mk * Mk+1 * Mk+2 * ... * Mj, ta sẽ in ra cách kết hợp tối ưu để nhân đoạn Mi * Mi+1 * ... * Mk và cách kết hợp tối ưu để nhân đoạn Mk+1 * Mk+2 * ... * Mj (có kèm theo dấu đóng mở ngoặc) đồng thời viết thêm dấu "*" vào giữa hai biểu thức đó.

PROG03_4.PAS * Nhân tối ưu dãy ma trận

program MatrixesMultiplier;

const

max = 100;

MaxLong = 1000000000;

97/129

var

a: array[1..max + 1] of Integer;

F: array[1..max, 1..max] of LongInt;

T: array[1..max, 1..max] of Byte;

n: Integer;

procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn}

var

i: Integer;

begin

ReadLn(n);

for i := 1 to n + 1 do Read(a[i]);

end;

procedure Optimize;

var

i, j, k, len: Integer;

x, p, q, r: LongInt;

begin

for i := 1 to n do for j := i to n do

if i = j then F[i, j] := 0

else F[i, j] := MaxLong; {Khởi tạo bảng phương án: đường chéo chính = 0, các ô khác = +∞≤}

for len := 2 to n do {Tìm cách kết hợp tối ưu để nhân đoạn gồm len ma trận liên tiếp}

for i := 1 to n - len + 1 do begin

98/129

j := i + len - 1; {Tính F[i, j]}

for k := i to j - 1 do {Xét mọi vị trí phân hoạch k}

begin

{Giả sử ta tính Mi * ... * Mj = (Mi * ... * Mk) * (Mk+1 * ... * Mj)}

p := a[i]; q := a[k + 1]; r := a[j + 1]; {Kích thước 2 ma trận sẽ nhân cuối cùng}

x := F[i, k] + F[k + 1, j] + p * q * r; {Chi phí nếu phân hoạch theo k}

end;

if x < F[i, j] then {Nếu phép phân hoạch đó tốt hơn F[i, j] thì ghi nhận lại}

begin

F[i, j] := x; T[i, j] := k;

end;

end;

end;

procedure Trace(i, j: Integer); {In ra phép kết hợp để nhân đoạn Mi * Mi+1 * ... * Mj}

var

k: Integer;

begin

if i = j then Write('M[', i, ']'){Nếu đoạn chỉ gồm 1 ma trận thì in luôn}

else {Nếu đoạn gồm từ 2 ma trận trở lên}

begin

99/129

Write('('); {Mở ngoặc}

k := T[i, j]; {Lấy vị trí phân hoạch tối ưu đoạn Mi...Mj} Trace(i, k); {In ra phép kết hợp để nhân đoạn đầu} Write(' * '); {Dấu nhân}

Trace(k + 1, j); {In ra phép kết hợp để nhân đoạn sau}

Write(')'); {Đóng ngoặc}

end;

end;

begin

Assign(Input, 'MATRIXES.INP'); Reset(Input); Assign(Output, 'MATRIXES.OUT'); Rewrite(Output); Enter;

Optimize;

WriteLn(F[1, n]); {Số phép nhân cần thực hiện} Trace(1, n); {Truy vết bằng đệ quy} WriteLn;

Close(Input); Close(Output);

end.

Bài tập luyện tập

Nhận xét: Nhiều vô kể, dễ, khó, dài, ngắn, to, nhỏ có hết!

Bài tập có gợi ý lời giải

Nhập vào hai số nguyên dương n và k (n, k ≤ 100). Hãy cho biết

a)Cóbaonhiêusốnguyêndươngcó≤ nchữsốmàtổngcácchữsốđúngbằngk.Nếucóhơn1 tỉ số thì chỉ cần thông báo có nhiều hơn 1 tỉ.

b) Nhập vào một số p ≤ 1 tỉ. Cho biết nếu đem các số tìm được xếp theo thứ tự tăng dần thì sốthứ p là số nào ?

Câua:Ta sẽ đếm số các số có đúng n chữ số mà tổng các chữ số (TCCS) bằng k, chỉ có điều các số

100/129

của ta cho phép có thể bắt đầu bằng 0. Ví dụ: ta coi 0045 là số có 4 chữ số mà TCCS là 9. Gọi F[n,

; x1, x2,… ,xn ở

k] là số các số có n chữ số mà TCCS bằng k. Các số đó có dạng ¯x1x2....xn đây là các

chữ số 0...9 và x1 + x2 + ... + xn = k. Nếu cố định x1 = t thì ta nhận thấy

x2 ...xn

lập thành một số có

n - 1 chữ số mà TCCS bằng k - t. Suy ra do x1 có thể nhận các giá trị từ 0 tới 9 nên về 9 F[n − 1,k − t]..Đây là công thức truy hồi tính F[n, k], thực mặt số lượng: F[n, k] = ∑t = 0 ra chỉ xét những giá trị t từ 0 tới 9 và t ≤ k mà thôi (để tránh trường hợp k - t <0). Chú ý rằng nếu tại một bước nào đó tính ra một phần tử của F > 109 thì ta đặt lại phần tử đó là 109 + 1 để tránh bị tràn số do cộng hai số quá lớn.

Kết thúc quá trình tính toán, nếu F[n, k] = 109 + 1 thì ta chỉ cần thông báo chung chung là có > 1 tỉ số.

Còn cơ sở quy hoạch động thì có nhiều cách đặt:

• Cách 1: F[1, k] = số các số có 1 chữ số mà TCCS bằng k, như vậy nếu k ≥ 10

thì F[1, k] = 0 còn nếu 0 ≤ k ≤ 9 thì F[1, k] = 1.

• Cách 2: F[0, k] = số các số có 0 chữ số mà TCCS bằng k, thì F[0, 0] = 1 (Dãy

X rỗng có tổng = 0) và F[0, k] = 0 với k > 0 (Bởi dãy X rỗng thì không thể cho tổng là số k dương được)

Câu b: Dựa vào bảng phương án F[0..n, 0..k],

F[n - 1, k] = số các số có n - 1 CS mà TCCS bằng k = số các số có n CS, bắt đầu là 0, TCCS bằng k.

F[n - 1, k - 1] = số các số có n - 1 CS mà TCCS bằng k - 1 = số các số có n CS, bắt đầu là 1, TCCS bằng k. F[n - 1, k - 2] = số các số có n - 1 CS mà TCCS bằng k - 2 = số các số có n CS, bắt đầu là 2, TCCS bằng k.

...

F[n - 1, k - 9] = số các số có n - 1 CS mà TCCS bằng k - 9 = số các số có n CS, bắt đầu là 9, TCCS bằng k.

101/129

Từ đó ta có thể biết được số thứ p (theo thứ tự tăng dần) cần tìm sẽ có chữ số đầu tiên là chữ số nào, tương tự ta sẽ tìm được chữ số thứ hai, thứ ba v.v... của số đó.

Cho n gói kẹo (n ≤ 200), mỗi gói chứa không quá 200 viên kẹo, và mộtsố M≤ 40000.Hãy chỉ ra một cách lấy ra m ộ t số các gói kẹo để được tổng số kẹo là M, hoặc thông báo rằng không thểthực hiện được việc đó.

Giả sử số kẹo chứa trong gói thứ i là Ai

Gọi b[V] là số nguyên dương bénhấtthoả mãn: Có thể chọn trong số các gói kẹo từ gói 1 đến gói b[V] ra một số gói để được tổng số kẹo là V. Nếu không có phương án chọn, ta coi b[V] = +∞. Trước tiên, khởi tạo b[0] = 0 và các b[V] = +∞ với mọi V > 0. Ta sẽ xây dựng b[V] như sau:

Để tiện nói, ta đặt k = b[V]. Vì k là bé nhất có thể, nên nếu có cách chọn trong số các gói kẹo từ gói 1 đến gói k để được số kẹo V thì chắcchắnphảichọngóik. Mà đã chọn gói k rồi thì trongsốcácgóikẹotừ1đếnk-1, phải chọn ra được một số gói đểđượcsốkẹolàV-Ak. Tức là b[V - Ak] ≤ k - 1 < k. Vậy thì b[V] sẽ được tính bằng cách:

Xét tất cả các gói kẹo k có Ak ≤ V và thoả mãn b[V - Ak] < k, chọn ra chỉ số k bé nhất, sau đó gán b[V] := k. Đây chính là công thức truy hồi tính bảng phương án.

Sau khi đã tính b[1], b[2], ..., b[M]. Nếu b[M] vẫn bằng +∞ thì có nghĩa là không có phương án chọn. Nếu không thì sẽ chọn gói p1 = b[M], tiếp theo sẽ chọn gói p2 = b[M - Ap1], rồi lại chọn gói p3 =b[M - Ap1 - Ap2]... Đến khi truy vết về tới b[0] thì thôi.

Chongóikẹo(n≤ 200),mỗigóichứakhôngquá200viênkẹo,hãychiacácgóikẹoralàm hai nhóm sao cho số kẹo giữa hai nhóm chênh lệch nhau ít nhất

Gọi S là tổng số kẹo và M là nửa tổng số kẹo, áp dụng cách giải như bài 2. Sau đó

Tìm số nguyên dương T thoả mãn:

• T ≤ M • Tồn tại một cách chọn ra một số gói kẹo để được tổng số kẹo là T (b[T] ≠ +∞) • T lớn nhất có thể

Sau đó chọn ra một số gói kẹo để được T viên kẹo, các gói kẹo đó được đưa vào một nhóm, số còn lại vào nhóm thứ hai.

102/129

Cho một bảng A kích thước m x n, trên đó ghi các số nguyên. Một người xuất phát t ạ i ô nào đó của cột 1, cần sang c ột n (tại ô nào cũng được). Quy tắc: T ừ ô A[i, j] c h ỉ được quyền sang m ột trong 3 ô A[i, j + 1]; A[i - 1, j + 1]; A[i + 1, j + 1]. Hãy tìm vị trí ô xuất phát và hành trình đi từ cột 1 sang cột n sao cho tổng các số ghi trên đường đi là lớn nhất.

Gọi B[i, j] là số điểm lớn nhất có thể có được khi tới ô A[i, j]. Rõ ràng đối với những ô ở cột 1 thì B[i, 1] = A[i, 1]:

Với những ô (i, j) ở các cột khác. Vì chỉ những ô (i, j - 1), (i - 1, j - 1), (i + 1, j - 1) là có thể sang được ô (i, j), và khi sang ô (i, j) thì số điểm được cộng thêm A[i, j] nữa. Chúng ta cần B[i, j] là số điểm lớn nhất có thể nên B[i, j] = max(B[i, j - 1], B[i - 1, j - 1], B[i + 1, j - 1]) + A[i, j]. Ta dùng công thức truy hồi này tính tất cả các B[i, j]. Cuối cùng chọn ra B[i, n] là phần tử lớn nhất trên cột n của bảng B và từ đó truy vết tìm ra đường đi nhiều điểm nhất.

Bài tập tự làm

Bài toán cái túi với kích thước như nêu trên là không thực tế, chẳng có siêu thị nào có ≤ 100 gói hàng cả. Hãy lập chương trình giải bài toán cái túi với n ≤ 10000; M ≤ 1000.

Dành cho độc giả

Xâu ký tự S gọi là xâu con của xâu ký tự T nếu có thể xoá bớt một số ký tự trong xâu T để được xâu S. Lập chương trình nhập vào hai xâu ký tự S1, S2. Tìm xâu S3 có độ dài lớn nhất là xâu con của cả S1 và S2. Ví dụ: S1 = 'abcdefghi123'; S2 = 'abc1def2ghi3' thì S3 là 'abcdefghi3'.

Dành cho độc giả

Một xâukýtựXgọilàchứaxâukýtựYnếu như có thể xoá bớt một số ký tự trong xâu X để được xâu Y: Ví dụ: Xâu '1a2b3c45d' chứa xâu '12345'. Một xâu ký tự gọi là đối xứng nếu nó không thay đổi khi ta viết các ký tự trong xâu theo thứ tự ngược lại: Ví dụ: 'abcABADABAcba', 'MADAM' là các xâu đối xứng.

103/129

Nhập một xâu ký tự S có độ dài không quá 128, hãy tìm xâu ký tự T thoả mãn cả 3 điều kiện:

1. Đối xứng 2. Chứa xâu S 3. Có ít ký tự nhất (có độ dài ngắn nhất)

Nếu có nhiều xâu T thoả mãn đồng thời 3 điều kiện trên thì chỉ cần cho biết một. Chẳng hạn với S = 'a_101_b' thì chọn T = 'ab_101_ba' hay T = 'ba_101_ab' đều đúng.

Dành cho độc giả

Có n loại tiền giấy: Tờ giấy bạc loại i có mệnh giá là V[i] ( n ≤ 20, 1 ≤ V[i] ≤ 10000). Hỏi muốn mua một món hàng giá là M thì có bao nhiêu cách trả số tiền đó bằng những loại giấy bạc đã cho (Trường hợp có > 1 tỉ cách thì chỉ cần thông báo có nhiều hơn 1 tỉ). Nếu tồn tại cách trả, cho biết cách trả phải dùng ít tờ tiền nhất.

Dành cho độc giả

Cho N số tự nhiên A1, A2, ..., AN. Biết rằng 1 ≤ N ≤ 200 và 0 ≤ Ai ≤ 200. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu "?": A1 ? A2 ? ... ? AN. Yêu cầu: Cho trước số nguyên K, hãy tìm cách thay các dấu "?" bằng dấu cộng hay dấu trừ để được một biểu thức số học cho giá trị là K. Biết rằng 1 ≤ N≤ 200 và 0 ≤ Ai ≤ 100.

Ban đầu 1 ? 2 ? 3 ? 4 và K = 0 sẽ cho kết quả 1 - 2 - 3 + 4.

Dãy Catalant là một dãy số tự nhiên bắt đầu là 0, kết thúc là 0, hai phần tử liên tiếp hơn kém nhau 1 đơn vị. Hãy lập chương trình nhập vào số nguyên dương n lẻ và một số nguyên dương p. Cho biết rằng nếu như ta đem tất cả các dãy Catalant độ dài n xếp theo thứ tự từ điển thì dãy thứ p là dãy nào.

Đối với phương pháp quy hoạch động, lượng bộ nhớ dùng để lưu bảng phương án có thể rất lớn nên ta tiết kiệm được càng nhiều càng tốt. Nếu bảng phương án được tính dưới dạng dùng dòng i tính dòng i + 1 thì rõ ràng việc lưu trữ các dòng i - 1, i - 2... bây giờ là không cần thiết, ta có thể cải tiến bằng cách dùng 2 mảng trước, sau tương ứng với 2 dòng i, i + 1 của bảng và cứ dùng chúng tính lại lẫn nhau, thậm chí chỉ cần dùng 1 mảng tương ứng với 1 dòng và tính lại chính nó như ví dụ đầu tiên đã làm, như vậy có thể tiết kiệm được bộ nhớ để chạy các dữ liệu lớn.

104/129

Dành cho độc giả

Thuật toán đồ thị cơ bản

Biểu diễn đồ thị

Các phương pháp biểu diễn đồ thị

Có hai chuẩn dùng để biểu diễn đồ thị G = (V, E):

Sử dụng tập hợp các danh sách kề:

Danh sách kề biểu diễn các đỉnh kề nhau, và thường hay được sử dụng bởi vì nó biểu diễn được một cách tối ưu đồ thị thưa (đồ thị thưa là đồ thị có số cạnh |E| ít hơn bình phương số các đỉnh |V|2 ). Hầu hết các thuật toán đồ thị được trình bày trong các phần sau sẽ sử dụng danh sách kề để biểu diễn đồ thị.

Sử dụng ma trận kề:

Nên sử dụng cách biểu diễn này đối với đồ thị dày, có nghĩa là khi |E| gần bằng |V|2, hoặc khi cần biết giữa hai đỉnh nào đó có cạnh nối hay không. Một số thuật toán tìm đường đi ngắn nhất sử dụng cách biểu diễn đồ thị đầu vào G qua ma trận kề.

Danh sách kề

Danh sách kề (là danh sách các đỉnh kề của đồ thị G = (V, E)) được mô tả bởi mảng Adj của |V| danh sách, mỗi một danh sách tương ứng với mỗi một đỉnh thuộc V. Với mỗi đỉnh u ∈ V, danh sách kề Adj[u] chứa (hay còn nói là trỏ tới) tất cả các đỉnh v mà từ v có cạnh nối tới u (có nghĩa là (u,v) ∈ E). Điều này có nghĩa là Adj[u] chứa tất cả các đỉnh kề với u trên đồ thị G. Các đỉnh trong mỗi một danh sách kề thông thường được lưu theo một trật tự tùy ý.

Nếu G là đồ thị có hướng, tổng chiều dài của tất cả các danh sách kề là |E|, do có cạnh nối (u,v) chỉ khi đỉnh v xuất hiện trong Adj[u]. Nếu G là một đồ thị vô hướng, tổng độ dài của tất cả các danh sách kề là 2|E|, do tồn tại cạnh vô hướng (u,v) chỉ khi đỉnh u xuất hiện trong danh sách các đỉnh kề của v và đỉnh v xuất hiện trong danh sách các đỉnh kề của u. Dù đồ thị có hướng hay vô hướng, việc biểu diễn qua danh sách kề chiếm một vùng bộ nhớ có kích thước là O(max(V,E)) = O(V + E).

105/129

Các danh sách các đỉnh kề có thể dễ dàng được sử dụng để biểu diễn các đồ thị có trọng số. Đó là đồ thị mà mỗi cạnh đều có một trọng số riêng, được tính bằng hàm trọng số w: E → R.

Cho G = (V,E) là một đồ thị trọng số với hàm trọng số w. Trọng số w(u,v) của cạnh (u,v) ∈ E được chứa cùng với đỉnh v trong danh sách các đỉnh kề với đỉnh u.

Biểu diễn danh sách đỉnh kề khá mạnh, xét từ khía cạnh nó có thể được biến đổi để hỗ trợ nhiều đồ thị đa dạng khác.

Một nhược điểm của cách biểu diễn đồ thị qua danh sách các đỉnh kề là để xác nhận cạnh (u,v) đã cho có tồn tại trên đồ thị G(V,E) không, không có một cách nào nhanh hơn là tiến hành tìm kiếm đỉnh v trong danh sách đỉnh Adj[u]. Có thể khắc phục nhược điểm này bằng cách chuyển sang biểu diễn đồ thị qua ma trận kề, tuy nhiên, việc này sẽ dòi hỏi phải sử dụng nhiều bộ nhớ hơn.

Ma trận kề

Với cách biểu diễn đồ thị G = (V, E) qua ma trận kề, quy ước rằng các đỉnh được đánh tùy ý từ 1, 2, ... cho đến |V|. Biểu diễn qua ma trận kề này được mô tả qua ma trận A = (aij) có kích thước |V| x |V| như sau:

aij = 1 nếu (i,f )∈ E

= 0 trong trường hợp khác

Hình 23.1(c) và hình 23.2(c) là các ma trận kề của đồ thị vô hướng và có hướng cho

trong hình 23.1(a) và 23.2(a) tương ứng. Ma trận kề của đồ thị yêu cầu Ρ(V2) bộ nhớ, không phụ thuộc vào số cạnh trong đồ thị.

Nếu để ý quan sát tính đối xứng qua đường chéo chính của ma trận kề trong hình 23.1(c). Định nghĩa hoán vị của ma trận A = (aij) là ma trận AT = (aijT) với aijT = aij.

Do với đồ thị vô hướng (u,v) và (v,u) đều biểu diễn cùng một cạnh, nên ma trận kề A của một đồ thị vô hướng chính là hoán vị của nó: A = AT. Trong một vài ứng dụng, chỉ cần lưu toàn bộ dữ liệu trên đường chéo của ma trận (tạo thành hình tam giác trên), do đó bộ nhớ được giảm một nửa.

Giống như cách biểu diễn qua danh sách các đỉnh kề, cách biểu diễn qua ma trận kề có thể được sử dung cho đồ thị có trọng số. Ví dụ, nếu G = (V, E) là một đồ thị trọng số với hàm w, trọng số w(u,v) của cạnh (u,v) được lưu trữ tương ứng với hàng v và cột u của ma trận kề. Nếu cạnh không tồn tại, một giá trị rỗng (NIL) sẽ được lưu trưữ tưng ứng trên ma trận. Nhiều bài toán thông thường sử dụng giá trị 0 hoặc ∞.

106/129

Mặc dù cách biểu diễn đồ thị danh sách các đỉnh kề gần như có hiệu quả ít nhất là bằng gần cách biểu diễn ma trận kề, nhưng vì tính đơn giản của cách biểu diễn ma trậnkề nên cách biểu diễn này hay được sử dụng hơn đới với đồ thị khá nhỏ. Hơn thế nữa, nếu đồ

thị không trọng số, lợi ích của việc sử dụng ma trận kề lại càng rõ ràng hơn:thay vì sử dụng một word nhớ cho mỗi một phần tử ma trận, ma trận kề chỉ cần sử dụng đến một bit tướng ứng với một phần tử của ma trận.

Tìm kiếm theo chiều rộng

Khái niệm

Duyệt theo chiều rộng (Breadth – first search, BFS) là một trong những thuật toán đơn giản nhất được sử dụng trong việc duyệt và tím kiếm trên đồ thị. Trên cơ sở của thuậttoán này mà nhiều các thuật toán đồ thị quan trọng khác đã ra đời, như là:

• Thuật toán Dijkstra giải bài toán đường đi ngắn nhất • Thuật toán Prim giải bài toán cây khung nhỏ nhất.

Giả sử cho đồ thị G=(V,E) vô hướng hoặc có hướng và một đỉnh xuất phát s bất kỳ. Thuật toán duyệt theo chiều sâu tiến hành:

• Duyệt các cạnh của đồ thị G để tìm ra từ đỉnh xuất phát s có thể đến được các

đỉnh nào. Các đỉnh này còng được gọi là các đỉnh được “thăm”.

• Tính toán khoảng cách (là số ít nhất các cạnh) từ s tới tất cả các đỉnh có thể đến

được từ s.

• Xây dựng cây (breath-first tree) có gốc là s và chứa tất cả các đỉnh có thể đến được từ s.Với một đỉnh v được thăm bất kỳ, tồn tại một đường đi trên cây này từ gốc s tới nút tương ứng với đỉnh v đó. Đường đi này chính là đường đi nhắn nhất từ s tới v trong đồ thị G, có nghĩa là số các cạnh của đường này là ít nhất.

Hoạt động của giải thuật

Nguyên tắc tô màu

Sở dĩ thuật toán BFS có tên gọi như vậy là do tại mỗi một bước của thuật toán, nó mở rộng biên giới giữa các đỉnh được thăm và chưa được thăm theo một quy tắc nhất định: thuật toán lần lượt thăm các đỉnh co khoảng cách từ đỉnh xuất phát là k (có nghĩa là số cạnh tự s tới các đỉnh này là k) trước khi thăm bất cứ một đỉnh nào co khoảng cách từ đỉnh s tới nó là k+1.

Trong quá trình hoạt động, thuật toán tiến hành bôi màu các đỉnh với một trong 3 màu - màu trắng, xám hoặc đen theo nguyên tắc sau:

107/129

• Tại bước khởi động tất cả các đỉnh của đồ thị đều có màu trắng. • Tất cả các đỉnh đã được thăm đều có màu xám hoặc đen.

• Thuật toán BFS phân biệt giữa các đỉnh có màu xám và màu đen để đảm bảo

tính chất duyệt theo chiều rộng của mình.

• Khi đỉnh v được thăm lần đầu tiên, nó được bôi màu xám. Các đỉnh này biểu hiện biên giới giữa các đỉnh đã được thăm và chưa được thăm. Sau đó thuật toán tiến hành duyệt các đỉnh kề với đỉnh v.

• Đỉnh v được bôi màu đen chỉ khi duyệt xong (thăm) tất cả các đỉnh kề với v.

Như vậy là nếu có cạnh (u,v)∈E và đỉnh u có màu den, đỉnh v có thể là xám hoặc đen.

Điều này có nghĩa là tất cả các đỉnh kề với đỉnh có màu đen đều chưa được thăm.

Cây Breadth–First Tree

Thuật toán BFS cho phép xây dựng cây T (breadth – first tree) như sau:

• Ban đầu cây này chỉ có mỗi một gốc là đỉnh s. • Trong quá trình duyệt, giả sử thuật toán đã duyệt đến đỉnh chưa được thăm u.

Khi đó u trở thành đỉnh đã được thăm và thuật toán sẽ tiến hành duyệt danh sách các đỉnh kề với đỉnh u. Nếu gặp phải đỉnh v kề với u, mà đỉnh v lại có màu trắng (chưa dược thăm lần nào cả), đỉnh v và cạnh (u,v) được bổ sung vào trong cây. Điều này có nghĩa là nút tương ứng với đỉnh u là nút cha của nút tương ứng với đỉnh v, còn đỉnh u được gọi là đỉnh trước của đỉnh v trong thứ tự duyệ theo chiều rộng.

Do các đỉnh được thăm nhiều nhất là một lần, nên nút trong cây T tương ứng với đỉnh này chỉ có một cha.

Mô tả thuật toán

Thuât toán BFS được mô tả như sau:

Đầu vào:

• Cho đồ thị vô hướng hoặc có hướng G=(V,E) được biểu diễn bằng danh sách

kề.

• Màu của đỉnh u∈V được lưu trong mảng color[u]. • Đỉnh trước của đỉnh u được lưu trong mảng π[u]. Nếu đỉnh u không có đỉnh

trước, khi đó π[u]=NIL.

• Khoảng cách từ đỉnh xuất phát s tới dỉnh u được lưu trong mảng d[u]. • Thuật toán sử dụng hàng đợi Q (theo nguyên tắc FIFO – vào trước ra trước) để

quản lý tập các đỉnh có màu xám.

108/129

Mô phỏng thuật toán BFS bằng ngôn ngữ giả Pascal:

BFS (G,s)

1 for each vertex u <-V[G]–{s}

2 do color[u]<-WHITE

3 d[u]<- ∞

4 π[u]<-NIL

5 colors[s]<-GRAY

6 d[s]<-0

7 π[s]<-NIL

8 Q<-{s}

9 while Q≠0

10 do u<-head[Q]

11 for each v<-Adj[u]

12 do if color[v]=WHITE

13 then color[v]<-GRAY

14 d[v]<-d[u]+1

15 π[v]<-u

16 ENQUEUE(Q,v)

17 DEQUEUE(Q)

18 color[u]<-BLACK

Phân tích đọan mã:

Bước 1 (dòng 1 cho đến dòng 4):

109/129

Thực hiện vòng lặp for để khởi tạo các giá trị ban đầu cho tất cả các đỉnh khác với đỉnh xuất phát s của đồ thị (each vertex u <- V[G] - {s}):

• Gán màu trắng cho mọi đỉnh của đồ thị G trừ đỉnh s (color [u] <- white) • Do tại bước đầu chưa tiến hành duyệt đồ thị, nên gán khoảng cách từ đỉnh s tới

các đỉnh còn lại bằng vô cùng (d[u] <- ∞)

• pi[u] <- NIL, có nghĩa là chưa xác định được đỉnh đứng trước đỉnh u trong thứ

tự duyệt theo chiều rộng.

Bước 2 (dòng 5 cho đến dòng 7):

Khởi tạo cho đỉnh xuất phát s:

• Gán màu xám cho s color[s] <- gray • Gán d[u] <- 0 (khoảng cách từ s tới chính nó là 0) • Gán pi[s] <- nil • Đẩy đỉnh s vào hàng đợi Q ( s trở thành phần tử đầu của Q)

Bước 3 (dòng 9 cho đến 18):

Đây là bước chính của thuật toán. Nó được lặp đi lặp lại khi trên đồ thị vẫn còn các đỉnh có màu xám, có nghĩa là khi còn có các đỉnh mà danh sách kề của chúng vẫn chưa được duyệt:

1) Kiểm tra hàng đợi Q co rỗng không. Nếu rỗng, kết thúc thuật toán. Ngược lại, chuyển sang bước 2.

2) Lấy phần tử u đầu từ Q.

3) Duyệt lần lượt danh sách các đỉnh kề của đỉnh u.

4) Với mỗi phần tử v của danh sách kề này kiểm tra xem v đã được thăm chưa (đỉnh v chưa được thăm khi color[v] <- WHITE). Nếu v chưa được thăm thì:

Tiến thành thăm đỉnh này bằng cách:

- gán color[v] <- GRAY

- gán giá trị mới cho khoảng cách tử đỉnh xuất phát s tới v: d[v] <- d[u]+1

- ghi nhớ lại đỉnh đứng trước đỉnh v: pi[v] <- u

Đẩy đỉnh vào cuối của hàng đợi Q (dòng 16).

110/129

5) Lặp lại bước 4 với phần tử tiếp theo trong danh sách các đỉnh kề với đỉnh u cho đến khi duyệt hết danh sách này.

6) Lấy phần tử u ra khởi hàng đợi Q.

7) Gán màu đen cho u: color[u] <- BLACK

Chú ý:

Thuật toán BFS trên sẽ không duyệt hết tất cả các đỉnh của đồ thị G nếu đồ thị này gồm nhiều thành phần liên thông khác nhau.

Trong trường hợp này thuật toán BFS phải được điều chỉnh lại như sau:

Để duyệt được hết các thành phần liên thông của đồ thị G, thuật toán được điều chỉch lại như sau:

Thêm một vòng lặp for ở ngoài cùng để duyệt mọi đỉnh của G. Đỉnh nào chưa được thăm, tiến hành đẩy đỉnh đó vào hành đợi Q và tiến hành một số động tác duyệt danh sách kề và gán giá trị tương ứng như đã được đề cập trong thuật toán đầu.

Như vậy, xuất phát từ đỉnh s nếu đã duyệt xong tất cả các đỉnh thuộc cùng một vùng liên thông mà thuật toán vẫn còn bỏ sót các đỉnh thuộc các thanh phần liên thông khác, thuật toán kiểm tra xem có còn các đỉnh bị bỏ sót không (khác với thuật toán đầu), nếu còn, nó sẽ tiến hành duyệt tiếp các đỉnh này.

Đánh giá độ phức tạp tính toán của thuật toán BFS

- Sau khi được khởi tạo, các đỉnh đều được gán màu trắng, nên mỗi một đỉnh sẽ được đưa vào trong hàng đợi Q nhiều nhất là một lần, và hiển nhiên là cũng được đưa ra khỏi hàng đợi nhiều nhất là một lần. Thao tác đẩy vào và lấy ra khỏi hàng đợi Q sẽ mất thời gian là O(1), vì vậy, thời gian tổng cộng dành cho các phép toán với hàng đợi là O(V).

- Do danh sách kề của mỗi một đỉnh được duyệt chri khi đỉnh này được đưa vào trong hành đợi, nên danh sách kề của mỗi một đỉnh cũng được duyệt nhiều nhất là một lần. Chiều dài của tất cả các danh dách kề là Ρ(E). Do vậy, thời gian dành cho việc duyệt toàn bộ các danh sách kề là O(E).

Vậy, độ phức tạp tính toán của thuật toán BFS là O(V+E). Từ đó cũng suy ra thời gian tính toán của BFS tỷ lệ tuyến tính với kích thước của danh sách kề của đồ thị G.

Tìm kiếm theo chiều sâu

Khái niệm

111/129

Thuật toán tìm kiếm theo chiều sâu đúng như cái tên của nó nghĩa là tìm kiếm sâu dần trên đồ thị chừng nào còn có thể. ý tưởng của thuật toán có thể được trình bày như sau:

Ta sẽ bắt đầu tìm kiếm từ một đỉnh v0 nào đó của đồ thị. Sau đó chọn u là một đỉnh kề với v0 và lặp lại quá trình đối với u. ở bước tổng quát giả sử ta đang xét đỉnh v. Trong thuật toán tìm kiếm theo chiều sâu, các cạnh đến được đỉnh v sẽ chưa được thăm cho đến khi nào v còn cạnh chưa được thăm. Khi tất cả các cạnh của v đã được thăm, thì ta nói rằng đỉnh v đã được duyệt xong và quay trở lại tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v. Quá trình này tiếp tục cho đến khi v = v0 thì kết thúc nghĩa là tất cả các cạnh của đồ thị đã được thăm.

Trong thuật toán tìm kiếm theo chiều sâu, với u là một đỉnh đã được thăm, thì mỗi khi một đỉnh v thuộc danh sách kề của u được thăm, thuật toán sẽ đánh dấu bằng cách đặt trước v một truờng πv có giá trị là u. Khác với thuật toán tìm kiếm theo chiều rộng toàn bộ đồ thị con trước đó (predecessor subgraph – là đồ thị tạo ra khi thăm các đỉnh trước đó trong quá trình tìm kiếm) xác định một cây tìm kiếm duy nhất , trong thuật toán tìm kiếm theo chiều sâu, đồ thị con trước đó có thể xác định nhiều cây tìm kiếm khác nhau bởi thuật toán có thể được lặp lại từ nhiều đỉnh khác nhau. Vì vậy đồ thị con trước đó trong thuật toán tìm kiếm theo chiều sâu được định nghĩa hơi khác một chút so với trong thuật toán tìm kiếm theo chiều rộng. Ta định nghĩa như sau:

Gπ = (V, Eπ) trong đó Eπ = { ( π[v], v) : v ∈ V và π[v] # Nil }

Đồ thị con trước đó trong thuật toán tìm kiếm theo chiều sâu sẽ xác định một rừng cây tìm kiếm theo chiều sâu ( a depth-first forest ) là tập hợp của các cây tìm kiếm theo chiều sâu ( deepth- first trees ).Các cạnh thuộc Eπ gọi là các cạnh của cây (tree edges).

Trong thuật toán tìm kiếm theo chiều sâu các đỉnh của đồ thị được tô màu để mô tả trạng thái của nó tại mỗi thời điểm.Các đỉnh ban đầu chưa được thăm sẽ được khởi tạo là màu trắng., khi được thăm sẽ tô màu xám và tô màu đen khi đã duyệt xong. Giải thuật tô màu trên sẽ đảm bảo chính xác mỗi đỉnh chỉ được duyệt một lần, vì vậy mà các cây tìm kiếm theo chiều sâu phân biệt được với nhau.

Bên cạnh việc tạo ra một rừng cây tìm kiếm theo chiều sâu, thuật toán tìm kiếm theo chiều sâu còn gán cho mỗi đỉnh một tem thời gian (timestamps). Mỗi đỉnh v sẽ có 2 tem thời gian: tem thứ nhất d[v] sẽ được gán khi đỉnh v được thăm lần đầu tiên ( được tô màu xám), tem thứ hai f[v] sẽ được gán khi các đỉnh trong danh sách kề của v đã được duyệt (v được tô màu đen). Các tem thời gian này được sử dụng nhiều trong các thuật toán đồ thị và cũng giúp ích rất nhiều cho việc mô tả quá trình thực hiện các bước trong thuật toán tìm kiếm theo chiều sâu .

112/129

Thủ tục DFS dưới đây sẽ ghi lại thời điểm thăm đỉnh u lần đầu tiên trong biến d[u] và thời điểm đỉnh u đã duyệt xong trong biến f[u]. Giá trị của 2 tem thời gian d[u], f[u] là các số nguyên nằm trong khoảng từ 1 đến 2 ?V?. Với mỗi đỉnh u: d[u] < f[u] , đỉnh u được tô màu trắng trước thời điểm d[u], màu xám trong khoảng thời gian giữa d[u] và f[u], và màu đen sau thời điểm f[u].

Thủ tục mô phỏng thuật toán tìm kiếm theo chiều sâu, trong đó đồ thị G ban đầu có thể vô hướng hoặc có hướng. Biến time là biến chung được chúng ta sử dụng cho việc gán tem thời gian.

DFS(G)

1 for u ∈ V[G] do

2 do color[u] <- WHITE

3 [u] <- NIL

4 time <- 0

5 for u ∈ V[G] do

6 if color[u] = WHITE

7 then DFS-Visit(u)

DFS - V is i t(u)

1 color[u] <- GRAY Trong khi đỉnh v chưa được thăm.

2 d[u] <- time <- time + 1

3 for v ∈ Adj[u] thăm cạnh (u,v)

4 do if color[v] = WHITE

5 then [v] <- u

6 DFS-Visit(v)

7 color[u] <- BLACK Tô màu đen cho đỉnh v khi đã duyệt xong

8 f[u] <- time <- time + 1

Thủ tục DFS làm việc như sau:

Dòng 1-3 sẽ tô màu tất cả các đỉnh của đồ thị là màu trắng và khởi tạo trường π của mỗi đỉnh về giá trị NIL.

113/129

Dòng 4 sẽ khởi tạo lại biến đếm thời gian chung.

Dòng 5-7 sẽ kiểm tra từng đỉnh thuộc tập V, khi một đỉnh màu trắng được tìm thấy, thực hiện thăm đỉnh bằng thủ tục DFS-Visit. Mỗi khi thủ tục DFS- Visit(u) được gọi tại dòng 7, đỉnh u sẽ trở thành gốc của một cây tìm kiếm mới trong rừng cây tìm kiếm theo chiều sâu.

Khi thủ tục DFS kết thúc , mỗi đỉnh u sẽ được gán hai tem thời gian thời gian là d[u] và f[u].

Tại mỗi lần gọi thủ tục DFS-Visit(u):

Đỉnh u ban đầu đang được tô màu trắng.

Khi thực hiện, dòng 1 sẽ tô màu xám cho đỉnh u

Dòng 2 ghi lại thời điểm đỉnh u bắt đầu được thăm lần đầu tiên vào biến time sau ki tăng biến lên 1.

Dòng 3-6 kiểm tra các đỉnh v kề với đỉnh u và thực hiện thăm v một cách đệ quy nếu nó vẫn là đỉnh trắng. Với mỗi đỉnh v được xét tại dòng 3, ta nói rằng cạnh (u,v) đã được thăm trong thuật toán tìm kiếm theo chiều sâu .

Khi tất cả các cạnh đi từ u đã được thăm, dòng 7-8 sẽ tô màu đen cho đỉnh u và ghi lại thời điểm đỉnh u đã duyệt xong trong biến f[u].

Độ phức tạp tính toán

Để đánh giá được độ phức tạp tính toán của thủ tục DFS, trước hết nhận thấy rằng số phép toán cần thực hiện trong hai chu trình của thuật toán ( hai vòng for ở dòng 1-2 và 5-7) là cỡ θ(V). Thủ tục DFS-Visit sẽ được gọi chính xác chỉ một lần cho mỗi đỉnh thuộc V và mỗi lần thực hiện không quá |Adj[v]|. phép toán. Trong đó :

Nghiã là tổng số phép toán cần thực hiện tại các dòng 2-5 của thủ tục DFS-Visit là θ (E). Vì vậy độ phức tạp tính toán của thủ tục DFS sẽ là θ (V+E).

Một số định lý của thuật toán tìm kiếm theo chiều sâu

114/129

Quá trình tìm kiếm theo chiều sâu trên đồ thị mô tả nhiều thông tin về cấu trúc của đồ thị. Một trong các thuộc tính cơ bản nhất của tìm kiếm sâu là đồ thị con trước đó Gπ sẽ xác định một rừng cây tìm kiếm sâu dần, trong đó cấu trúc của các cây tìm kiếm sâu

phản ánh cấu trúc của các lệnh gọi đệ quy thủ tục DFS-VISIT. Nghĩa là u=π[v] khi và chỉ khi thủ tục DFS-VISIT được gọi trong suốt quá trình tìm kiếm các đỉnh thuộc danh sách kề của u.

Để dễ hiểu ta xét ví dụ với đồ thị chỉ có 2 đỉnh là u,v: khi thăm u danh sách kề của u là v. Theo thủ tục DFS-VISIT thì quá trình tìm kiếm có thể hiểu như sau: Bước khởi tạo sẽ tô mầu trắng cho các đỉnh và gán các đỉnh trước của nó là rỗng. Sau khi gọi, thủ tục DFS-VISIT đầu tiên sẽ tô mầu cho u là xám (thủ tục bình thường thì thường có các hành động như xem xét kết thúc.. nhưng thủ tục ở đây đưa ra mang tính tổng quan tiếp sau chúng ta không đề cập nữa), sau đó duyệt trên danh sách kề của u thấy v thăm tiếp và tô v mầu xám. Khi xét danh sách kề của v thấy không còn đỉnh nào, tô màu đen cho đỉnh v và quay trở lại thăm gốc u.. Như vậy ta có thể thấy nó tạo thành một cây có 2 nút u, v, và quá trình thăm mỗi nút chính là thực hiện gọi thủ tục đệ quy DFS-VISIT.

Đối với đồ thị tổng quát nhiều đỉnh hơn thì cũng thực hiện tương tự.

Một thuộc tính quan trọng khác của tìm kiếm sâu trên đồ thị là các lần thăm và kết thúc thăm đỉnh đều có cấu trúc ngoặc đơn (parenthesis structure). Nghĩa là nếu chúng ta biểu diễn quá trình bắt đầu thăm một đỉnh u (chẳng hạn có thể dùng stack,..) bằng một dấu ngoặc trái trước u: ”(u”, quá trình kết thúc thăm u bằng một dấu ngoặc phải sau u: “u)”, thì toàn bộ quá trình thăm và kết thúc thăm sẽ tạo ra một biểu thức có các dấu ngoặc đơn xếp lồng nhau và đối xứng hay còn gọi là có biểu thức cấu trúc ngoặc đơn.

Định lý cấu trúc ngoặc đơn được đưa ra như sau:

Định lý 1 (Định lý dấu ngoặc đơn)

Khi tìm kiếm theo chiều sâu trên một đồ thị có hướng hay vô hướng G=(V,E), với 2 đỉnh u và v bất kỳ, thì sẽ xảy ra một trong 3 trường hợp sau: Các khoảng [d[u],f[u]] và [d[v],f[v]] hoàn toàn rời nhau.

Khoảng [d[u],f[u]] hoàn toàn nằm trong khoảng [d[v],f[v]] , và u là con của v trong cây tìm kiếm sâu

Khoảng [d[v],f[v]] hoàn toàn nằm trong khoảng [d[u],f[u]] , và v là con của u trong cây tìm kiếm sâu

Chứng minh:

Chúng ta bắt đầu với trường hợp d[u]

115/129

d[v]

khi quá trình tìm kiếm tiếp tục quay trở lại duyệt đỉnh u. Như vậy trong trường hợp này [d[v],f[v]] hoàn toàn trong khoảng [d[u],f[u]].

Khả năng thứ 2 là f[u]

Chúng ta chứng minh tương tự với trường hợp d[v]

Hệ quả 2

Đỉnh v được gọi là con thực sự của u trong rừng tìm kiếm sâu của một đồ thị có hướng hoặc vô hướng G khi và chỉ khi d[u]

Chứng minh: áp dụng định lý 1 ta có điều phải chứng minh

Định lý 3 (Định lý đường đi trắng)

Trong rừng tìm kiếm sâu của một đồ thị có hướng hoặc vô hướng G=(V,E), đỉnh vlà một đỉnh con của đỉnh u khi và chỉ khi tại thời điểm d[u] nghĩa là tại thời điểm khi bắt đầu thăm đỉnh u, đỉnh v có thể tới được từ u theo một con đường gồm toàn bộ các đỉnh tô mầu trắng.

Chứng minh:

Đ iều kiện c ầ n :

Giả sử đỉnh v là một con của u và w là một đỉnh bất kì trên đường đi giữa u và v trong cây tìm kiếm sâu, có nghĩa là w là con của u. Theo hệ quả 2, d[u]

Điều kiện đủ:

116/129

Giả sử tại thời điểm d[u], từ đỉnh u ta có thể đến được đỉnh v dọc theo một con đường gồm các đỉnh vẫn tô màu trắng, nhưng v không phải là con của u trong cây tìm kiếm sâu. Không mất tính tổng quát, giả sử mọi đỉnh khác trên đường đi trắng đó đều là con của u. (nếu không thì cho v là đỉnh gần u nhất dọc theo đường đi trắng nhưng không là con u). Cho w là đỉnh trước của v trên đường trắng, mà w là con của u (w và u có thể cùng là một đỉnh), theo hệ quả 2: f(w) ≤ f(u). Chú ý rằng v phải được thăm sau khi u đã được thăm, nhưng trước khi w thăm xong. Do đó d[u]

Ta có điều cần chứng minh.

Phân loại cạnh

Một trong các thuộc tính đáng quan tâm của tìm kiếm sâu là quá trình tìm kiếm có thể sử dụng để phân loại các cạnh của đồ thị đầu vào G=(V,E). Việc phân loại các cạnh có thể sử dụng để thu thập thông tin về đồ thị. Ví dụ, trong phần tiếp theo chúng ta sẽ thấy một đồ thị có hướng là không có chu trình nếu quá trình tìm kiếm sâu không gồm các cạnh back.

Chúng ta có thể định nghĩa 4 loại cạnh trong rừng tìm kiếm sâu Gπ. khi tìm kiếm sâu trên đồ thị G.

Các cạnh cây là các cạnh trong rừng tìm kiếm sâu Gπ. Cạnh (u,v) là một cạnh của cây nếu v được thăm lần đầu khi duyệt cạnh (u,v).

Cạnh Back là những cạnh (u,v) mà đỉnh u nối tới tổ tiên v trong cây tìm kiếm sâu.

Cạnh của một đỉnh (cạnh nối một đỉnh với chính nó) cũng được coi như là cạnh Back. Cạnh Forwardlà các cạnh không phải là cạnh cây (u,v) nối một đỉnh u tới con v trong một cây tìm kiếm sâu.

Cạnh Chéolà tất cả các cạnh khác các loại cạnh trên. Chúng có thể là cạnh giữa các đỉnh trong cùng một cây tìm kiếm sâu khi một đỉnh không là tổ tiên của đỉnh khác, chúng cũng có thể là cạnh giữa các đỉnh trong các cây tìm kiếm sâu khác nhau.

Thuật toán DFS có thể thay đổi để giúp ta có thể phân loại các cạnh khi thực hiện tìm kiếm sâu trên đồ thị. ý tưởng chủ đạo của nó là mỗi cạnh (u,v) có thể phân lớp bằng màu của đỉnh v - tức là đỉnh tới được khi thăm cạnh lần đầu tiên - (ngoại trừ các cạnh forward và chéo không thể phân biệt được): Màu trắng chỉ một cạnh của cây

Màu xám chỉ một cạnh back

Màu đen chỉ một cạnh forward hay một cạnh chéo

Trường hợp 1 xuất phát từ đặc điểm của thuật toán. Trường hợp 2 là do khi quan sát quá trình tìm kiếm sâu ta thấy các đỉnh tô màu xám luôn tạo ra một chuỗi các đỉnh con tương ứng với stack của đỉnh đang gọi thủ tục DFS_VISIT. Số các đỉnh xám lớn hơn 1 so với độ sâu rừng tìm kiếm sâu của đỉnh được thăm gần đây nhất . Quá trình duyệt được tiếp tục từ đỉnh xám có độ sâu lớn nhất qua một cạnh để tới đỉnh xám khác,.. rồi đến đỉnh xám tổ tiên. Trường hợp thứ 3 là các khả năng còn lại, cạnh (u,v) là cạnh forward nếu d[u] < d[v] và là cạnh chéo nếu d[u] > d[v].

117/129

Định lý 4

Khi tìm kiếm theo chiều sâu trên một đồ thị vô hướng G, mọi cạnh của G hoặc là cạnh cây hoặc là cạnh back.

Chứng minh:

Cho (u, v) là một cạnh tuỳ ý của G, không làm mất tính tổng quát ta có thể giả sử d[u]

Chúng ta sẽ còn thấy rất nhiều ứng dụng của các định lý trên trong các phần sau.

Sắp xếp Topo

Giải thuật sắp xếp Topo

Sau đây là giải thuật sắp xếp tôpô cho một đồ thị dag:

Topological_sort (G)

• Gọi DFS(G) để tính các thời điểm xem xét f[v] cho mỗi đỉnh v • Với mỗi điểm đã được xem xét, cho nó vào đầu của một danh sách liên kết • Trở lại danh sách liên kết các đỉnh

Hình 23.7(b) chỉ ra cách các đỉnh được sắp xếp tôpô xuất hiện theo thứ tự ngược với thời điểm kết thúc chúng.

Độ phức tạp tính toán

Chúng ta có thể đánh giá độ phức tạp tính toán của giải thuật là Q(V+E) vì: tìm kiếm theo chiều sâu mất Q(V+E) và để chèn một đỉnh (trong số |V| đỉnh) vào trước danh sách liên kết mất O(1) .

Chúng ta chứng minh tính đúng đắn của giải thuật này bằng cách sử dụng một bổ đề quan trọng nêu lên đặc tính của các đồ thị không chu trình có hướng.

Bổ đề 5

Một đồ thị có hướng G là không có chu trình nếu và chỉ nếu thực hiện tìm kiếm theo chiều sâu trên G sẽ không có các cạnh back.

118/129

Chứng minh.

Điều kiện cần:

Giả sử rằng có một cạnh back (u,v). Khi đó đỉnh v là đỉnh trước (đỉnh tổ tiên) của đỉnh u trong tìm kiếm theo chiều sâu. Vì thế sẽ có một đường đi từ v tới u trong G, do vậy khi kết hợp cạnh (u,v) sẽ tạo thành một chu trình.

Điều kiện đủ:

Giả sử rằng G chứa một chu trình c. Chúng ta sẽ chỉ ra rằng khi tìm kiếm theo chiều sâu trên G sẽ có một cạnh back. Gọi v là đỉnh đầu tiên được thăm trong c, và gọi (u, v) là cạnh trước c. Tại thời điểm d[v], có một đường đi trắng từ v tới u. Theo định lý đường đi trắng, đỉnh u trở thành đỉnh trước của đỉnh v trong tìm kiếm theo chiều sâu. Vì thế (u, v) là một cạnh back.

Đ ịnh lý 6

Giải thuật sắp xếp tôpô TOPOLOGICAL_SORT(G) ở trên tạo ra một sắp xếp tôpô đối với đồ thị không chu trình có hướng G.

Ch ứ ng m inh

Giả sử rằng thủ tục DFS được thực hiện trên một đồ thị dag G=(V,E) cho trước để xác định thời điểm kết thúc thăm các đỉnh của đồ thị. Ta sẽ chỉ ra bất cứ một cặp đỉnh riêng biệt u,v ∈ V, nếu có một cạnh trong G từ u tới v thì f[v]

Xét một cạnh bất kỳ (u,v) được thăm bởi DFS(G). Khi cạnh này được thăm, đỉnh v không thể có màu xám vì khi đó v có thể là đỉnh trước u và (u,v) sẽ là một cạnh back, mâu thuẫn. Vì thế v chỉ có thể là đỉnh màu trắng hoặc là đỉnh màu đen. Nếu v là đỉnh trắng nó thành đỉnh sau của u và vì thế f[v]

Định lý được chứng minh.

Độ phức tạp tính toán

Chúng ta có thể đánh giá độ phức tạp tính toán của giải thuật là Q(V+E) vì: tìm kiếm theo chiều sâu mất Q(V+E) và để chèn một đỉnh (trong số |V| đỉnh) vào trước danh sách liên kết mất O(1) .

Chúng ta chứng minh tính đúng đắn của giải thuật này bằng cách sử dụng một bổ đề quan trọng nêu lên đặc tính của các đồ thị không chu trình có hướng.

119/129

Bổ đề 5

Một đồ thị có hướng G là không có chu trình nếu và chỉ nếu thực hiện tìm kiếm theo chiều sâu trên G sẽ không có các cạnh back.

Chứng minh.

Điều kiện cần:

Giả sử rằng có một cạnh back (u,v). Khi đó đỉnh v là đỉnh trước (đỉnh tổ tiên) của đỉnh u trong tìm kiếm theo chiều sâu. Vì thế sẽ có một đường đi từ v tới u trong G, do vậy khi kết hợp cạnh (u,v) sẽ tạo thành một chu trình.

Điều kiện đủ:

Giả sử rằng G chứa một chu trình c. Chúng ta sẽ chỉ ra rằng khi tìm kiếm theo chiều sâu trên G sẽ có một cạnh back. Gọi v là đỉnh đầu tiên được thăm trong c, và gọi (u, v) là cạnh trước c. Tại thời điểm d[v], có một đường đi trắng từ v tới u. Theo định lý đường đi trắng, đỉnh u trở thành đỉnh trước của đỉnh v trong tìm kiếm theo chiều sâu. Vì thế (u, v) là một cạnh back.

Đ ịnh lý 6

Giải thuật sắp xếp tôpô TOPOLOGICAL_SORT(G) ở trên tạo ra một sắp xếp tôpô đối với đồ thị không chu trình có hướng G.

Ch ứ ng m inh

Giả sử rằng thủ tục DFS được thực hiện trên một đồ thị dag G=(V,E) cho trước để xác định thời điểm kết thúc thăm các đỉnh của đồ thị. Ta sẽ chỉ ra bất cứ một cặp đỉnh riêng biệt u,v ∈ V, nếu có một cạnh trong G từ u tới v thì f[v]

Xét một cạnh bất kỳ (u,v) được thăm bởi DFS(G). Khi cạnh này được thăm, đỉnh v không thể có màu xám vì khi đó v có thể là đỉnh trước u và (u,v) sẽ là một cạnh back,mâu thuẫn. Vì thế v chỉ có thể là đỉnh màu trắng hoặc là đỉnh màu đen. Nếu v là đỉnh trắng nó thành đỉnh sau của u và vì thế f[v]

Các thành phần liên thông mạnh

Giới thiệu

120/129

Ta xét một ứng dụng kinh điển của việc tìm kiếm theo chiều sâu: phân rã một đồ thị có hướng thành các thành phần liên thông mạnh. Trong phần này sẽ trình bày cách phân rã sử dụng hai lần tìm kiếm theo chiều sâu. Có rất nhiều các thuật toán làm việc với đồ thị

có hướng sử dụng phép phân rã này; cách tiếp cận này cho phép chia một bài toán thành các bài toán nhỏ, mỗi bài toán tương ứng với một thành phần liên thông mạnh. Kết hợp các giải pháp của các bài toán nhỏ theo kiến trúc liên kết giữa các thành phần liên thông mạnh; kiến trúc này có thể được biểu diễn bởi một đồ thị được gọi là đồ thị thành phần.

Một thành phần liên thông mạnh của một đồ thị có hướng G=(V, E) là tập cực đại các đỉnh U ⊆ V sao cho mỗi cặp đỉnh u và v thuộc U ta có uv và vu có nghĩa là u và v đều có thể được đi tới từ các đỉnh khác.

Thuật toán tìm kiếm các thành phần liên thông mạnh của một đồ thị G=(V, E) sử dụng đồ thị đảo của G, đồ thị này gọi là GT = (V, ET), trong đó ET = {(u,v): (v,u) ∈ E}. ET bao gồm các cung của đồ thị G với chiều đảo ngược. Với danh sách kề biểu diễn cho đồ thị G, thời gian để xây dựng GT là O(V+E). Có một điều khá thú vị đó là G và GT có cùng số lượng các thành phần liên thông: u và v có thể được đi tới từ các đỉnh thuộc G nếu và chỉ nếu chúng có thể được đi tới từ các đỉnh thuộc GT. Hình 5.1(b) biểu diễn đồ thị đảo của đồ thị ở hình 5.1(a), các thành phần liên thông được tô đậm.

a) Một đồ thị có hướng G. Các thành phần liên thông mạnh của G là các vùng được tô đậm. Mỗi đỉnh được đánh nhãn là thời gian thăm và thời gian kết thúc. Các cung của cây được tô đậm.

b) GT - đồ thị đảo của G. Cây tìm kiếm chiều sâu được tính toán ở dòng 3 của STRONGLY-CONNECTED-COMPONENTS được chỉ ra với các cung của cây được tô đậm. Mỗi thành phần liên thông mạnh tương ứng với một cây tìm kiếm chiều sâu. Các đỉnh b, c, g và h được tô đậm hơn là tổ tiên của tất cả các đỉnh trong thành phần liên thông mạnh của chúng; các đỉnh này cũng là các gốc của các cây tìm kiếm chiều sâu được tạo ra do tìm kiếm theo chiều sâu trên GT.

c) ồ thị thành phần GSCC được thu được bằng cách co mỗi thành phần của G thành một đỉnh đơn.

Thuật toán với thời gian tính tuyến tính sau tính toán các thành phần liên thông của đồ thị có hướng G= (V, E) bằng cách sử dụng 2 lần tìm kiếm theo chiều sâu, một trên G và một trên GT.

STRONGLY-CONNECTED-COMPONENTS(G)

1. gọi DFS(G) để tính toán thời gian kết thúc f[u] cho mỗi đỉnh u

2. tính GT

121/129

3. gọi DFS(GT), nhưng trong vòng lặp chính của DFS, xem xét các đỉnh để giảm f[u] (như tính toán trong bước 1)

4. đưa ra các đỉnh của mỗi cây trong rừng tìm kiếm theo chiều sâu của bước 3 như một thành phần liên thông mạnh riêng rẽ

Thuật toán trông khá đơn giản và có vẻ như không liên quan gì tới các thành phần liên thông mạnh. Tuy nhiên, bí mật thiết kế và tính đúng đắn của nó sẽ được nghiên cứu trong phần tiếp theo.

Các bổ đề và định lý cơ bản

Bổ đề 7

Nếu 2 đỉnh cùng thuộc một thành phần liên thông mạnh thì không có cung nào giữa chúng nằm tách rời thành phần liên thông mạnh đó.

Chứng minh:

Giả sử u và v là 2 đỉnh thuộc cùng thành phần liên thông mạnh. Theo định nghĩa về thành phần liên thông mạnh, có các đường đi từ u tới v và từ v tới u. Gọi w là một đỉnh nằm trên đường đi uwv do vậy w là đỉnh có thể được đi tới từ u. Hơn nữa, do có đường đi từ vu ta biết rằng u có thể được đi tới từ w bởi đường đi wvu. Do vậy, u và w là ở trong cùng một thành phần liên thông mạnh. Do w được chọn một cách tuỳ ý, định lý được chứng minh.

Bổ đề 8

Trong các phép tìm kiếm theo chiều sâu, tất cả các đỉnh thuộc cùng một thành phần liên thông mạnh sẽ thuộc cùng cây tìm kiếm theo chiều sâu.

Chứng minh:

Với các đỉnh trong thành phần liên thông mạnh, gọi r là đỉnh đầu tiên được thăm. Do r là đỉnh đầu tiên, các đỉnh khác trong thành phần liên thông mạnh là có màu trắng tại thời điểm nó được thăm. Có các đường đi từ r tới tất cả các đỉnh còn lại trong thành phần liên thông mạnh, do các cung này không nằm tách rời thành phần liên thông

mạnh , tất cả các đỉnh thuộc chúng đều là trắng. Do vậy, theo định lý đường đi trắng, tất cả các đỉnh trong thành phần liên thông mạnh trở thành con cháu của r trong cây tìm kiếm chiều sâu

122/129

Trong phần còn lại của phần này, ký hiệu d[u] và f[u] biểu diễn cho thời gian thă ra và thời gian kết thúc được tính toán bởi lần tìm kiếm theo chiều sâu thứ nhất ở dòng 1 của thủ tục STRONGLY-CONNECTED-COMPONENTS. Tương tự ký hiệu uv biểu diễn cho sự hiện diện của một đường đi trong G chứ không phải GT.

Để chứng minh STRONGLY-CONNECTED-COMPONENTS đúng, ta giới thiệu khái niệm ϕ(u) là tổ tiên của đỉnh u là một đỉnh w có thể được đi tới từ u và được kết thúc cuối cùng trong lần tìm kiếm theo chiều sâu trong dòng 1. Nói cách khác:

ϕ(u) = w sao cho uw và f[w] là cực đại

Chú ý rằng ϕ(u) = u là có thể xảy ra do u là có thể được đi tới từ chính nó, và do vậy: f[u] ≤ f[ϕ(u)] (*)

Ta cũng có thể chỉ ra rằng ϕ(ϕ(u)) = ϕ(u) bởi lý do sau: với u,v V U,v có nghĩa là f[ϕ(v)] ≤ f[ϕ(u)] (**)do {w: v→→w } ⊆ {w: u→→w } và đỉnh tổ tiên có thời gian kết thúc lớn nhất trong tất cả các đỉnh. Do ϕ(u) là có thể được đi tới từ u công thức (**) có nghĩa là f[ϕ(ϕ(u))] ≤ f[ϕ(u)]. Ta cũng có f[ϕ(u)] ≤ f[ϕ(ϕ(u))] theo bất đẳng thức (*). Do vậy f[ϕ(ϕ(u))] = f[ϕ(u)] nên ta có ϕ(ϕ(u)) = ϕ(u) do 2 đỉnh mà kết thúc tại cùng thời điểm thì chính là một đỉnh.

Như ta đã thấy, tất cả các thành phần liên thông mạnh có một đỉnh là tổ tiên của tất cả các đỉnh khác trong thành phần liên thông mạnh đó; đỉnh này gọi là đỉnh đại diện của thành phần liên thông mạnh đó. Trong lần tìm kiếm theo chiều sâu của G, nó là đỉnh đầu tiên của thành phần liên thông mạnh được thăm. Trong lần tìm kiếm theo chiều sâu trên GT, nó là gốc của cây tìm kiếm chiều sâu. Chúng ta sẽ chứng minh các tính chất này

Định lý đầu tiên chứng minh gọi ϕ(u) là tổ tiên của u

Định lý 9

Trong một đồ thị có hướng G = (V, E), (u) của mọi đỉnh u V trong bất kỳ phép tìm kiếm theo chiều sâu trên G là tổ tiên của u.

Chứng minh:

Nếu ϕ(u)= u, định lý hiển nhiên đúng. Nếu ϕ(u) ≠ u, xem xét màu của các đỉnh tại thời điểm d[u]. Nếu ϕ(u) là màu đen, thì f[(u)] < f[u] mâu thuẫn với bất đẳng thức (*). Nếu ϕ(u) là xám thì đó là một tổ tiên của u và do đó định lý được chứng minh.

Ta cần chứng minh rằng ϕ(u) không phải màu trắng. Có hai trường hợp, theo màu của các đỉnh trung gian trên đường đi từ u tới ϕ(u):

1. Nếu tất cả các đỉnh là màu trắng, thì ϕ(u) trở thành con cháu của u theo định lý đường đi trắng. Nhưng từ đó ta có f[(u)]

123/129

2. Nếu có một đỉnh trung gian nào đó không phải là trắng, gọi t là đỉnh không trắng cuối cùng trên đường đi từ u tới ϕ(u). Do vậy, t phải là xám, do không có một cung nào từ

một đỉnh đen tới một đỉnh trắng, và đỉnh tiếp theo t là trắng. Nhưng từ đó do có một đường đi của các đỉnh trắng từ t tới ϕ(u), và do vậy ϕ(u)

là một con cháu của t theo định lý đường đi trắng. Điều đó có nghĩa là f[t] >

f[(u)], mâu thuẫn với lựa chọn của chúng ta với ϕ(u), do vậy có một đường đi từ

u tới t 3) và tính chất r = F(r) ta thu được f[?(w)] ≥ f[?(r)] = ?(r), điều này mâu thuẫn với giả thiết f[?(w)] < f[r].

Do vậy T sẽ chứa các đỉnh mà ϕ(w) = r. Có nghĩa là T tương đương với thành phần liên thông mạnh C(r), định lý đã được chứng minh.

Bài tập chương

Cho đồ thị sau:

Hãy biểu diễn đồ thị bằng a). Ma trận kề

b). Danh sách kề

Dành cho độc giả

124/129

Cho đồ thị sau

Hãy biểu diễn đồ thị bằng

c) Ma trận trọng số

d) Danh sách kề

3.Cho các đồ thị

Hãy minh họa các bước của thuật toán a) Tìm kiếm theo chiều sâu

b) Tìm kiếm theo chiều rộng

Dành cho độc giả

125/129

Cho đồ thị

Nêu cách sắp xếp thứ tự các đỉnh do thuật toán Topological-Sort tạo ra cho hình trên.

Minh họa thuật toán.

Dành cho độc giả

Cho đồ thị

Xác định các thành phần liên thông mạnh của đồ thị

126/129

Dành cho độc giả

Tham gia đóng góp

Tài liệu: Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán

Biên tập bởi: Đại Học Phương Đông

URL: http://voer.edu.vn/c/d95aa558

Giấy phép: http://creativecommons.org/licenses/by/3.0/

Module: Độ phức tạp tính toán và tính hiệu quả của thuật toán

Các tác giả: Đại Học Phương Đông

URL: http://www.voer.edu.vn/m/a51dc616

Giấy phép: http://creativecommons.org/licenses/by/3.0/

Module: Mở đầu về thiết kế, đánh giá thuật toán và kiến thức bổ trợ

Các tác giả: Đại Học Phương Đông

URL: http://www.voer.edu.vn/m/f5007ea2

Giấy phép: http://creativecommons.org/licenses/by/3.0/

Module: Phương pháp tham lam

Các tác giả: Đại Học Phương Đông

URL: http://www.voer.edu.vn/m/f09a14a9

Giấy phép: http://creativecommons.org/licenses/by/3.0/

Module: Phương pháp “chia để trị”

Các tác giả: Đại Học Phương Đông

URL: http://www.voer.edu.vn/m/61608553

Giấy phép: http://creativecommons.org/licenses/by/3.0/

Module: Quy hoạch động

Các tác giả: Đại Học Phương Đông

URL: http://www.voer.edu.vn/m/9a197ec0

Giấy phép: http://creativecommons.org/licenses/by/3.0/

Module: Thuật toán đồ thị cơ bản

Các tác giả: Đại Học Phương Đông

127/129

URL: http://www.voer.edu.vn/m/211f7618

128/129

Giấy phép: http://creativecommons.org/licenses/by/3.0/

Chương trình Thư viện Học liệu Mở Việt Nam

Chương trình Thư viện Học liệu Mở Việt Nam (Vietnam Open Educational Resources – VOER) được hỗ trợ bởi Quỹ Việt Nam. Mục tiêu của chương trình là xây dựng kho Tài nguyên giáo dục Mở miễn phí của người Việt và cho người Việt, có nội dung phong phú. Các nội dung đểu tuân thủ Giấy phép Creative Commons Attribution (CC-by) 4.0 do đó các nội dung đều có thể được sử dụng, tái sử dụng và truy nhập miễn phí trước hết trong trong môi trường giảng dạy, học tập và nghiên cứu sau đó cho toàn xã hội.

Với sự hỗ trợ của Quỹ Việt Nam, Thư viện Học liệu Mở Việt Nam (VOER) đã trở thành một cổng thông tin chính cho các sinh viên và giảng viên trong và ngoài Việt Nam. Mỗi ngày có hàng chục nghìn lượt truy cập VOER (www.voer.edu.vn) để nghiên cứu, học tập và tải tài liệu giảng dạy về. Với hàng chục nghìn module kiến thức từ hàng nghìn tác giả khác nhau đóng góp, Thư Viện Học liệu Mở Việt Nam là một kho tàng tài liệu khổng lồ, nội dung phong phú phục vụ cho tất cả các nhu cầu học tập, nghiên cứu của độc giả.

Nguồn tài liệu mở phong phú có trên VOER có được là do sự chia sẻ tự nguyện của các tác giả trong và ngoài nước. Quá trình chia sẻ tài liệu trên VOER trở lên dễ dàng như đếm 1, 2, 3 nhờ vào sức mạnh của nền tảng Hanoi Spring.

129/129

Hanoi Spring là một nền tảng công nghệ tiên tiến được thiết kế cho phép công chúng dễ dàng chia sẻ tài liệu giảng dạy, học tập cũng như chủ động phát triển chương trình giảng dạy dựa trên khái niệm về học liệu mở (OCW) và tài nguyên giáo dục mở (OER) . Khái niệm chia sẻ tri thức có tính cách mạng đã được khởi xướng và phát triển tiên phong bởi Đại học MIT và Đại học Rice Hoa Kỳ trong vòng một thập kỷ qua. Kể từ đó, phong trào Tài nguyên Giáo dục Mở đã phát triển nhanh chóng, được UNESCO hỗ trợ và được chấp nhận như một chương trình chính thức ở nhiều nước trên thế giới.