Các chiến lược thiết kế thuật toán

 CÁC CHIẾN LƯỢC THIẾT KẾ THUẬT TOÁN 
 Với một vấn đề đặt ra, làm thế nào chúng ta có thể đưa ra thuật toán giải quyết 
nó? Trong chương này, chúng ta sẽ trình bày các chiến lược thiết kế thuật toán, còn 
được gọi là các kỹ thuật thiết kế thuật toán. Mỗi chiến lược này có thể áp dụng để giải 
quyết một phạm vi khá rộng các bài toán. Mỗi chiến lược có các tính chất riêng và chỉ 
thích hợp cho một số dạng bài toán nào đó. Chúng ta sẽ lần lượt trình bày các chiến 
lược sau: chia-để-trị (divide-and-conquer), quy hoạch động (dynamic programming), 
quay lui (backtracking) và tham ăn (greedy method). Trong mỗi chiến lược chúng ta sẽ 
trình bày ý tưởng chung của phương pháp và sau đó đưa ra một số ví dụ minh họa. 
 Cần nhấn mạnh rằng, ta không thể áp dụng máy móc một chiến lược cho một 
vấn đề, mà ta phải phân tích kỹ vấn đề. Cấu trúc của vấn đề, các đặc điểm của vấn đề 
sẽ quyết định chiến lược có khả năng áp dụng. 
1. CHIA - ĐỂ - TRỊ 
1.1. Phương pháp chung 
 Chiến lược thiết kế thuật toán được sử dụng rộng rãi nhất là chiến lược chia-để-
trị. Ý tưởng chung của kỹ thuật này là như sau: Chia vấn đề cần giải thành một số vấn 
đề con cùng dạng với vấn đề đã cho, chỉ khác là cỡ của chúng nhỏ hơn. Mỗi vấn đề 
con được giải quyết độc lập. Sau đó, ta kết hợp nghiệm của các vấn đề con để nhận 
được nghiệm của vấn đề đã cho. Nếu vấn đề con là đủ nhỏ có thể dễ dàng tính được 
nghiệm, thì ta giải quyết nó, nếu không vấn đề con được giải quyết bằng cách áp dụng 
đệ quy thủ tục trên (tức là lại tiếp tục chia nó thành các vấn đề con nhỏ hơn,). Do 
đó, các thuật toán được thiết kế bằng chiến lược chia-để-trị sẽ là các thuật toán đệ quy. 
 Sau đây là lược đồ của kỹ thuật chia-để-trị: 
 DivideConquer (A,x) 
 // tìm nghiệm x của bài toán A. 
 if (A đủ nhỏ) 
 Solve (A); 
 else 
 Chia bài toán A thành các bài toán con 
 A1, A2,, Am; 
 for (i = 1; i <= m ; i ++) 
 DivideConquer (Ai , xi); 
 Kết hợp các nghiệm xi của các bài toán con Ai (i=1, , m) để nhận 
 được nghiệm x của bài toán A; 
  
 1 
 Như vậy, trong trường hợp xấu nhất, ta cần thực hiện 2(n-1) phép so sánh, tức là thời 
gian chạy của thuật toán là O(n). 
 Bây giờ ta áp dụng kỹ thuật chia-để-trị để đưa ra một thuật toán khác. Ta chia 
mảng A[0..n-1] thành các mảng con A[0..k] và A[k+1..n-1] với k = [n/2]. Nếu tìm 
được max, min của các mảng con A[0..k] và A[k+1..n-1], ta dễ dàng xác định được 
max, min trên mảng A[0..n-1]. Để tìm max, min trên mảng con ta tiếp tục chia đôi 
chúng. Quá trình sẽ dừng lại khi ta nhận được mảng con chỉ có một hoặc hai phần tử. 
Trong các trường hợp này ta xác định được dễ dàng max, min. Do đó, ta có thể đưa ra 
thuật toán sau: 
 MaxMin (i, j, max, min) 
 // Biến max, min ghi lại giá trị lớn nhất, nhỏ nhất trong mảng A[i..j] 
 { 
 if (i = = j) 
 max = min = A[i]; 
 else if (i = = j-1) 
 if (A[i] A[j]) 
 { 
 max = A[j]; 
 min = A[i]; 
 } 
 else { 
 max = A[i]; 
 min = A[j]; 
 } 
 else { 
 mid = (i+j) / 2; 
 MaxMin (i, mid, max1, min1); 
 MaxMin (mid + 1, j, max2, min2); 
 if (max 1 max2) 
 max = max2; 
 else max = max1; 
 if (min1 min2) 
 min = min1; 
 else min = min2; 
 } 
 3 
 int Fact(int n) 
 { 
 if (n = 0) 
 return 1; 
 else 
 return n * Fact(n-1); // gọi đệ quy. 
 } 
 Trong hàm đệ quy trên, trường hợp cơ sở là n = 0. Để tính Fact(n) cần thực hiện 
lời gọi Fact(n-1), lời gọi này lại dẫn đến lời gọi F(n-2),, và cuối cùng dẫn tới lời gọi 
F(0), tức là dẫn tới trường hợp cơ sở. 
 Đệ quy và phép lặp. Đối với một vấn đề, có thể có hai cách giải: giải thuật đệ 
quy và giải thuật dùng phép lặp. Giải thuật đệ quy được mô tả bởi hàm đệ quy, còn 
giải thuật dùng phép lặp được mô tả bởi hàm chứa các lệnh lặp, để phân biệt với hàm 
đệ quy ta sẽ gọi là hàm lặp. Chẳng hạn, để tính giai thừa, ngoài hàm đệ quy ta có thể 
sử dụng hàm lặp sau: 
 int Fact(int n) 
 { 
 if (n = = 0) 
 return 1; 
 else { 
 int F= 1; 
 for (int i = 1; i = n ; i + +) 
 F = F * i; 
 return F; 
 } 
 } 
 Ưu điểm nổi bật của đệ quy so với phép lặp là đệ quy cho phép ta đưa ra giải 
thuật rất đơn giản, dễ hiểu ngay cả đối với những vấn đề phức tạp. Trong khi đó, nếu 
không sử dụng đệ quy mà dùng phép lặp thì thuật toán thu được thường là phức tạp 
hơn, khó hiểu hơn. Ta có thể thấy điều đó trong ví dụ tính giai thừa, hoặc các thuật 
toán tìm kiếm, xem, loại trên cây tìm kiếm nhị phân (xem mục 8.4). Tuy nhiên, trong 
nhiều trường hợp, các thuật toán lặp lại hiệu quả hơn thuật toán đệ quy. 
 Bây giờ chúng ta phân tích các nhân tố có thể làm cho thuật toán đệ quy kém 
hiệu quả. Trước hết, ta cần biết cơ chế máy tính thực hiện một lời gọi hàm. Khi gặp 
 5 
 Một nhân tố khác làm cho các thuật toán đệ quy kém hiệu quả là các lời gọi đệ 
quy có thể dẫn đến phải tính nghiệm của cùng một bài toán con rất nhiều lần. Số 
Fibonacci thứ n, ký hiệu là F(n), được xác định đệ quy như sau: 
 F(1) = 1 
 F(2) = 1 
 F(n) = F(n-1) + F(n-2) với n 2 
Do đó, ta có thể tính F(n) bởi hàm đệ quy sau. 
 int Fibo(int n) 
 { 
 if ((n = = 1) // (n = = 2)) 
 return 1; 
 else 
 return Fibo (n-1) + Fibo(n-2); 
 } 
 Để tính F(7), các lời gọi trong hàm đệ quy Fibo dẫn ta đến phải tính các F(k) 
vói k 7, như được biểu diễn bởi cây trong hình dưới đây; chẳng hạn để tính F(7) cần 
tính F(6) và F(5), để tính F(6) cần tính F(5) và F(4),  
 F(7) 
 F(6) F(5) 
 F(5) F(4) F(4) F(3) 
 F(4) F(3) F(3) F(2) F(3) F(2) F(2) F(1) 
 F(3) F(2) F(2) F(1) F(2) F(1) F(2) F(1) 
Từ hình vẽ trên ta thấy rằng, để tính được F(7) ta phải tính F(5) 2 lần, tính F(4) 3 lần, 
 F(2) F(1) 
tính F(3) 5 lần, tính F(2) 8 lần và tính F(1) 5 lần. Chính sự kiện để tính F(n) ta phải 
tính các F(k), với k n, rất nhiều lần đã làm cho hàm đệ quy Fibo kém hiệu quả. Có thể 
đánh giá thời gian chạy của nó là O(n), trong đó = (1 + 5 )/2. 
 Chúng ta có thể đưa ra thuật toán lặp để tính dãy số Fibonacci. Ý tưởng của 
thuật toán là ta tính lần lượt các F(1), F(2), F(3), , F(n -2), F(n-1), F(n) và sử dụng 
hai biến để lưu lại hai giá trị vừa tính. Hàm lặp tính dãy số Fibonacci như sau: 
 int Fibo1(int n) 
 { 
 if ((n= = 1)//(n= = 2) 
 return 1; 
 else { 
 7 
 Đưa ra cách tính nghiệm của các bài toán con đơn giản nhất. 
 Tìm ra các công thức (hoặc các quy tắc) xây dựng nghiệm của bài toán 
 thông qua nghiệm của các bài toán con. 
 Thiết kế bảng để lưu nghiệm của các bài toán con. 
 Tính nghiệm của các bài toán con từ nhỏ đến lớn và lưu vào bảng. 
 Xây dựng nghiệm của bài toán từ bảng. 
 Một ví dụ đơn giản của thuật toán được thiết kế bằng quy hoạch động là thuật 
toán lặp tính dãy số Fibonacci mà ta đã đưa ra trong mục 16.2. Trong hàm lặp Fibo1, 
ta đã tính tuần tự F(1), F(2),, đến F(n). Và bởi vì để tính F(k) chỉ cần biết F(k-1) và 
F(k-2), nên ta chỉ cần lưu lại F(k-1) và F(k-2). 
 Kỹ thuật quy hoạch động thường được áp dụng để giải quyết các bài toán tối 
ưu (optimization problems). Các bài toán tối ưu thường là có một số lớn nghiệm, mỗi 
nghiệm được gắn với một giá, và mục tiêu của chúng ta là tìm ra nghiệm có giá nhỏ 
nhất : nghiệm tối ưu (optimization solution). Chẳng hạn, bài toán tìm đường đi từ 
thành phố A đến thành phố B trong bản đồ giao thông, có nhiều đường đi từ A đến B, 
giá của một đường đi đó là độ dài của nó, nghiệm tối ưu là đường đi ngắn nhất từ A 
đến B. Nếu nghiệm tối ưu của bài toán được tạo thành từ nghiệm tối ưu của các bài 
toán con thì ta có thể sử dụng kỹ thuật quy hoạch động. 
 Sau đây, chúng ta sẽ đưa ra một số thuật toán được thiết kế bằng kỹ thuật quy 
hoạch động. 
3.2. Bài toán sắp xếp các đồ vật vào ba lô 
 Giả sử ta có chiếc ba lô có thể chứa được một khối lượng w, chúng ta có n loại 
đồ vật được đánh số i,, n. Mỗi đồ vật loại i (i = 1,, n) có khối lượng ai và có giá trị 
ci. Chúng ta muốn sắp xếp các đồ vật vào ba lô để nhận được ba lô có gía trị lớn nhất 
có thể được. Giả sử mỗi loại đồ vật có đủ nhiều đề xếp vào ba lô. 
 Bài toán ba lô được mô tả chính xác như sau. Cho trước các số nguyên dương 
w, ai, và ci (i = 1,,n). Chúng ta cần tìm các số nguyên không âm xi (i = 1,, n) sao 
cho 
 n
  xi ai w và 
 n 1
 xi ci đạt giá trị lớn nhất. 
 Xét trường hợp đơn giản nhất: chỉ có một loại đồ vật (n = 1). Trong trường hợp 
này ta tìm được ngay lời giải: xếp đồ vật vào ba lô cho tới khi nào không xếp được nữa 
thì thôi, tức là ta tìm được ngay nghiệm xi = w/ai. 
 Bây giờ ta đi tìm cách tính nghiệm của bài toán “xếp n loại đồ vật vào ba lô 
khối lượng w” thông qua nghiệm của các bài toán con “xếp k loại đồ vật (1 k n) 
 9 
 Nếu i 0 và j 0 và ai  bj thì 
 L(i,j) = max [L(i,j-1), L(i-1,j)] (2) 
 Nếu i 0 và j 0 và ai = bj thì 
 L(i,j) = 1 + L(i-1,j-1) (3) 
Sử dụng các công thức đệ quy (1), (2), (3) để tính các L(i,j) lần lượt với i = 0,1,,m 
và j = 0,1,,n. Chúng ta sẽ lưu các giá trị L(i,j) vào mảng L[0..m][0..n]. 
 Công việc tiếp theo là từ mảng L ta xây dựng dãy con chung dài nhất của a và 
b. Giả sử k = L[m][n] và dãy con chung dài nhất là c = (c1,ck-1, ck). Ta xác định các 
thành phần của dãy c lần lượt từ phải sang trái, tức là xác định ck, rồi ck-1,,c1. Ta xem 
xét các thành phần của mảng L bắt từ L[m,n]. Giả sử ta đang ở ô L[i][j] và ta đang cần 
xác định cr, (1 <= r <= k). Nếu ai = bj thì theo (3) ta lấy cr = ai, giảm r đi 1 và đi đến ô 
L[i-1][j-1]. Còn nếu ai # bj thì theo (2) hoặc L[i][j] = L[i][j-1], hoặc L[i][j] = L[i-1][j]. 
Trong trường hợp L[i][j] = L[i][j-1] ta đi tới ô L[i][j-1], còn nếu L[i][j] = L[i-1][j] ta đi 
tới ô L[i-1][j]. Tiếp tục quá trình trên ta xác định được tất cả các thành phần của dãy 
con dài nhất. 
4. QUAY LUI 
4.1. Tìm kiếm vét cạn 
 Trong thực tế chúng ta thường gặp các câu hỏi chẳng hạn như “có bao nhiêu 
khả năng...?”, “hãy cho biết tất cả các khả năng...?”, hoặc “có tồn tại hay không một 
khả năng...?”. Ví dụ, có hay không một cách đặt 8 con hậu vào bàn cờ sao cho chúng 
không tấn công nhau. Các vấn đề như thế thông thường đòi hỏi ta phải xem xét tất cả 
các khả năng có thể có. Tìm kiếm vét cạn (exhaustive search) là xem xét tất cả các 
ứng cử viên nhằm phát hiện ra đối tượng mong muốn. Các thuật toán được thiết kế 
bằng tìm kiếm vét cạn thường được gọi là brute-force algorithms. Ý tưởng của các 
thuật toán này là sinh-kiểm, tức là sinh ra tất cả các khả năng có thể có và kiểm tra mỗi 
khả năng xem nó có thoả mãn các điều kiện của bài toán không. Trong nhiều vấn đề, 
tất cả các khả năng mà ta cần xem xét có thể quy về các đối tượng tổ hợp (các tập con 
của một tập), hoặc các hoán vị của n đối tượng, hoặc các tổ hợp k đối tượng từ n đối 
tượng. Trong các trường hợp như thế, ta cần phải sinh ra, chẳng hạn, tất cả các hoán vị, 
rồi kiểm tra xem mỗi hoán vị có là nghiệm của bài toán không. Tìm kiếm vét cạn 
đương nhiên là kém hiệu quả, đòi hỏi rất nhiều thời gian. Nhưng cũng có vấn đề ta 
không có cách giải quyết nào khác tìm kiếm vét cạn. 
 Ví dụ 1( Bài toán 8 con hậu). Chúng ta cần đặt 8 con hậu vào bàn cờ 8x8 sao 
cho chúng không tấn công nhau, tức là không có hai con hậu nào nằm cùng hàng, hoặc 
cùng cột, hoặc cùng đường chéo. 
 Vì các con hậu phải nằm trên các hàng khác nhau, ta có thể đánh số các con hậu 
từ 1 đến 8, con hậu i là con hậu đứng ở hàng thứ i (i=1,...,8). Gọi xi là cột mà con hậu 
thứ i đứng. Vì các con hậu phải đứng ở các cột khác nhau, nên (x1, x2, ...,x8) là một 
 11