Nguyen lý kế thừa và một số bài toán dãy bị chặn

ừ điển của các dãy bị chặn
Theo thứ tự từ điển, dãy số t′ được kế thừa phần bên trái nhiều nhất có thể của dãy số t
từ thành phần đầu tiên đến thành phần thứ i− 1, với
i = max{j|tj < gj}.
Khi đó, các thành phần từ đầu tiên đến thứ i− 1 sẽ được giữ nguyên
t′j = tj , j = 1, 2, ..., i− 1.
Các thành phần từ vị trí thay đổi i đến thành phần cuối cùng được xác định như sau
t′i = ti + 1, và t
′
j = sj , j = i+ 1, i+ 2, ..., n.
Quá trình sinh các dãy số kết thúc khi đã sinh ra tất cả các dãy số thỏa mãn (3.1). Nghĩa
là khi dãy số lớn nhất 〈g1 g2 ... gn〉 được sinh ra. Khi đó thì i = 0. Đây cũng là điều kiện kết
thúc của thuật toán.
Từ những lý luận trên ta xây dựng thuật toán chi tiết sinh các dãy bị chặn như sau.
Thuật toán 3.1. Sinh các dãy bị chặn
Đầu vào: Số nguyên dương n, hai dãy số biên 〈s1 s2 ... sn〉 và 〈g1 g2 ... gn〉
Đầu ra: Dãy các dãy số 〈t1, t2, ..., tn〉 thỏa mãn (3.1) được sắp tăng theo thứ tự từ điển
1 Begin
2 input n; S[i]←− si, G[i]←− gi, i = 1, 2, ..., n;
3 T [1..n]←− S[1..n];
4 repeat
5 print dãy số T [1..n];
6 i←− n;
NGUYÊN LÝ KẾ THỪA VÀ MỘT SỐ BÀI TOÁN DÃY BỊ CHẶN 83
7 while T [i] = G[i] do
8 {T [i]←− S[i]; i←− i− 1};
9 if i ≥ 1 then T [i]←− T [i] + 1;
10 until i = 0;
11 End.
Độ phức tạp của Thuật toán 3.1:
Các câu lệnh 5–9 sinh ra một dãy số mới với độ phức tạp O(n). Vậy độ phức tạp tổng thể
của thuật toán là O(n×∏ni=1(gi − si + 1)).
Độ phức tạp tổng thể của thuật toán xấp xỉ bằng O(n.an), với
a = max(g1 − s1 + 1, g2 − s2 + 1, ..., gn − sn + 1).
3.3. Một số ứng dụng của bài toán dãy bị chặn
Một số bài toán tổ hợp có thể đưa về bài toán dãy bị chặn. Do vậy, ta có thể áp dụng
Thuật toán 3.1 để tìm nghiệm cho các bài toán này một cách nhanh chóng. Trong phần này,
sẽ áp dụng thuật toán trên cho bài toán tập con của tập hợp và bài toán tập con bội của tập
bội.
1) Bài toán tập con của tập hợp
Giả sử X là một tập hợp n-phần tử. Hãy tìm tất cả các tập con của tập X.
Ký hiệu X = {x1, x2, ..., xn}. Mỗi tập con A ⊆ X có thể biểu diễn bằng một dãy nhị phân
độ dài n, 〈b1, b2...bn〉, với:
bi =
{
1, nếu xi ∈ A
0, ngược lại.
Số tất cả các tập con của tập X là 2n. Việc tìm tất cả các tập con của tập X đưa về việc
tìm tất cả các dãy nhị phân độ dài n.
Các dãy 〈b1, b2...bn〉 cần tìm phải thỏa mãn:
0 ≤ bi ≤ 1, bi ∈ {0, 1}. (3.2)
Vậy bài toán tìm các dãy nhị phân độ dài n có thể đưa về bài toán dãy bị chặn với hai
dãy biên là s = 〈0 0 ... 0〉 và g = 〈1 1 ... 1〉. Khi đó, ta có thuật toán đơn giản tìm các dãy
nhị phân như sau:
Thuật toán 3.2. Sinh các tập con của tập hợp
Đầu vào: Số nguyên dương n
Đầu ra: Dãy các dãy nhị phân độ dài n biểu diễn các tập con của tập n phần tử được sắp
tăng theo thứ tự từ điển
1 Begin
2 input n;
3 B[1..n]←− 0;
4 repeat
5 print B[1..n];
6 i←− n;
7 while B[i] = 1 do {B[i]←− 0; i←− i− 1};
84 HOÀNG CHÍ THÀNH
8 if i ≥ 1 then B[i]←− 1;
9 until i = 0;
10 End.
Độ phức tạp của Thuật toán 3.2:
Dễ thấy rằng, độ phức tạp tổng thể của thuật toán là O(n.2n).
Thuật toán này đơn giản, ngắn gọn và là một trong các thuật toán sinh các tập con có
độ phức tạp nhỏ nhất. Thuật toán sinh các tập con thường được sử dụng trong các bài toán
chọn, mật mã và xử lý ảnh [1, 2]...
2) Bài toán tập con bội của tập bội
Tập bội (multi-set) là tập hợp, mà nó cho phép các phần tử xuất hiện nhiều hơn một
lần. Chẳng hạn, tập giá trị của các biến trong một chương trình, bộ đánh dấu trong một hệ
mạng...
Tập bội được viết dưới dạng tổng quát như sau:
X = (k1 × x1, k2 × x2, ..., kn × xn), trong đó ki ≥ 0, i = 1, 2, ..., n.
Các phần tử x1, x2, ..., xn được gọi là cơ sở của tập bội, còn k1, k2, ..., kn là bội của các
phần tử tương ứng.
Tập con bội của một tập bội là một tập bội mà bội của mỗi phần tử cơ sở trong tập con
không vượt quá bội của phần tử này trong tập mẹ.
Giả sử, tập bội A = (t1 × x1, t2 × x2, ..., tn × xn).
A ⊆ X ⇐⇒ ∀i = 1, 2, ..., n, 0 ≤ ti ≤ ki. (3.3)
Người ta thường biểu diễn tập bội A bằng dãy số nguyên 〈t1 t2 ... tn〉 độ dài n bao gồm
bội của các phần tử cơ sở trong tập này. Chẳng hạn, tập bội A = (3×x1, 4×x2, 1×x3, 5×x4)
có thể biểu diễn bởi dãy số 〈3 4 1 5〉.
Bài toán. Cho tập bội X = (k1 × x1, k2 × x2, ..., kn × xn). Hãy tìm tất cả các tập con bội
của tập này.
Với cách biểu diễn tập con bội như trên, bài toán tập con bội của tập bội có thể đưa về
bài toán dãy bị chặn với hai dãy số biên là s = 〈0 0 ... 0〉 và g = 〈k1 k2 ... kn〉.
Số tập con bội của tập bội X là:
∏n
i=1(k1 + 1). Việc tìm tất cả các tập con bội A của tập
bội X đưa về việc tìm tất cả các dãy số 〈t1 t2 ... tn〉 thỏa mãn (3.3) biểu diễn các tập con bội
cần tìm.
Áp dụng Thuật toán 3.1 ta có thuật toán tìm các tập con bội của tập bội như sau.
Thuật toán 3.3. Sinh các tập con bội
Đầu vào: Các số nguyên dương n, k1, k2, ..., kn.
Đầu ra: Dãy các tập con bội mà các biểu diễn dãy số 〈t1t2...tn〉 của chúng được sắp tăng theo
thứ tự từ điển.
1 Begin
2 input n,K[i]←− ki, i = 1, 2, ..., n;
3 T [1..n]←− 0;
4 repeat
5 print T [1..n];
6 i←− n;
NGUYÊN LÝ KẾ THỪA VÀ MỘT SỐ BÀI TOÁN DÃY BỊ CHẶN 85
7 while T [i] = K[i] do {T [i]←− 0; i←− i− 1};
9 if i ≥ 1 then T [i]←− T [i] + 1;
10 until i = 0;
11 End.
Độ phức tạp của thuật toán:
Độ phức tạp tổng thể của thuật toán trên là O((
∏n
i=1(ki + 1)).n). Độ phức tạp của thuật
toán xấp xỉ bằng O(n.ln), với l = max{k1, k2, ..., kn}.
Thuật toán này ngắn gọn và đơn giản hơn nhiều so với Thuật toán đệ quy 1.14 trình bày
trong [2] để sinh các tập con bội của một tập bội. Ta xét ví dụ ứng dụng sau đây.
Ví dụ 3.3. Bài toán xếp ba lô
Giả sử ta có n loại đồ vật quý và một ba lô có dung tích c. Loại đồ vật thứ i có số lượng
là ki và mỗi đồ vật loại này có giá trị là pi và dung lượng là si (i = 1, 2, ..., n). Hãy chọn và
xếp các đồ vật vào ba lô sao cho tổng giá trị các đồ vật xếp trong ba lô là lớn nhất có thể.
Ký hiệu đồ vật loại thứ nhất là x1, loại thứ hai là x2, ... và loại thứ n là xn. Tập các đồ
vật trên có thể biểu diễn bằng tập bội: X = (k1 × x1, k2 × x2, ..., kn × xn). Mỗi phương án
chọn các đồ vật để xếp vào ba lô chính là một tập con bội A của tập bội trên, sao cho
A = (t1 × x1, t2 × x2, ..., tn × xn), A ⊆ X và
n∑
i=1
ti.si ≤ c.
Phương án tối ưu là phương án mà
∑n
i=1 ti.pi đạt giá trị lớn nhất.
Kết hợp Thuật toán 3.3 sinh các tập con bội và thuật toán tìm số lớn nhất ta sẽ nhận
được nghiệm tối ưu của bài toán một cách nhanh chóng.
Chẳng hạn, xét bài toán trên với dữ liệu được cho trong bảng dưới đây.
Loại đồ vật a b c d e
Số lượng 3 5 2 4 6
Giá trị 25 28 20 12 15
Dung lượng 10 11 8 5 6
và ba lô có dung lượng là 100.
Tính toán theo các thuật toán trên, ta nhận được phương án xếp ba lô tối ưu là A =
(0× a, 5× b, 2× c, 1× d, 4× e) với tổng dung lượng là 100 (đầy ba lô) và tổng giá trị lớn nhất
là 252.
Bài toán xếp ba lô được ứng dụng nhiều trong các hệ thống truyền tin và mạng máy tính.
4. BÀI TOÁN DÃY ĐƠN ĐIỆU BỊ CHẶN
Khi thêm một số ràng buộc trên các dãy bị chặn ta sẽ nhận được bài toán dãy bị chặn
dạng đặc biệt.
4.1. Bài toán dãy đơn điệu bị chặn
Trong Bài toán 3.1 dãy bị chặn, nếu đòi hỏi hai dãy biên s, g và các dãy bị chặn t là đơn
điệu tăng thì ta có bài toán dãy đơn điệu bị chặn.
86 HOÀNG CHÍ THÀNH
Xuất phát từ dãy số đơn điệu tăng đầu tiên 〈s1 s2 ... sn〉 ta xây dựng vòng lặp để sinh ra
các dãy số đơn điệu tăng còn lại. Giả sử t = 〈t1 t2 ... tn〉 là một dãy số đơn điệu tăng độ dài
n thỏa mãn (3.1) vừa tìm được. Ta cần phải tìm dãy số t′ = 〈t′1 t′2 ... t′n〉 đơn điệu tăng thỏa
mãn (3.1), kế tiếp sau dãy số trên trong dãy được sắp tăng.
Theo thứ tự từ điển, dãy số t′ được kế thừa phần bên trái nhiều nhất có thể của dãy số t
từ thành phần đầu tiên đến thành phần thứ i− 1, với
i = max{j|tj < gj}.
Khi đó, các thành phần từ đầu tiên đến thứ i− 1 sẽ được giữ nguyên:
t′j = tj , j = 1, 2, ..., i− 1.
Các thành phần từ vị trí thay đổi i đến thành phần cuối cùng được xác định như sau:
t′i = ti + 1, và t
′
j = max(t
′
j−1 + 1, sj) với j = i+ 1, i+ 2, ..., n.
Từ đó, ta có thuật toán sinh các dãy đơn điệu bị chặn như sau.
Thuật toán 4.1. Sinh các dãy đơn điệu bị chặn
Đầu vào: Số nguyên dương n, hai dãy số biên đơn điệu tăng 〈s1 s2 ... sn〉 và 〈g1 g2 ... gn〉.
Đầu ra: Dãy các dãy số đơn điệu tăng 〈t1, t2, ..., tn〉 thỏa mãn (3.1) được sắp tăng theo thứ tự
từ điển.
1 Begin
2 input n, S[i]←− si, G[i]←− gi, i = 1, 2, ..., n;
3 T [1..n]←− S[1..n];
4 repeat
5 print T [1..n];
6 i←− n;
7 while T [i] = G[i] do i←− i− 1;
8 if i ≥ 1 then for j ←− n downto i do A[j]←− max(A[i] + j − i+ 1, S[j]);
10 until i = 0;
11 End.
Độ phức tạp của Thuật toán 4.1:
Tương tự như Thuật toán 3.1, Thuật toán 4.1 có độ phức tạp tổng thể là
O(n.
∏n
i=1(gi − si + 1)).
4.2. Ứng dụng cho bài toán tập con k-phần tử
Giả sử X là một tập hợp n phần tử và k là một số nguyên không âm.
Bài toán đặt ra là tìm tất cả các tập con k-phần tử của tập X.
Đồng nhất tập n-phần tử X với tập các số nguyên dương {1, 2, ..., n}. Khi đó, mỗi tập con
k-phần tử của tập X tương ứng 1-1 với một dãy các số nguyên dương đơn điệu tăng độ dài k.
Mỗi dãy như thế có thể xem như là một từ trên bảng chữ cái {1, 2, ..., n}.
Sắp xếp các từ trên theo thứ tự từ điển. Từ đầu tiên (nhỏ nhất) là 〈1 2 ... k − 1 k〉 và từ
cuối cùng (lớn nhất) là 〈n− k + 1 n− k + 2 ... n− 1n〉.
NGUYÊN LÝ KẾ THỪA VÀ MỘT SỐ BÀI TOÁN DÃY BỊ CHẶN 87
Vậy bài toán tìm các tập con k-phần tử của tập n phần tử có thể đưa về bài toán tìm các
dãy đơn điệu bị chặn với hai dãy biên là 〈1 2 ... k − 1 k〉 và 〈n− k + 1 n− k + 2 ... n− 1 n〉.
Áp dụng Thuật toán 4.1, ta có thuật toán ngắn gọn sau đây sinh các tập con k-phần tử của
tập n phần tử.
Thuật toán 4.2. Sinh các tập con k-phần tử
Đầu vào: Hai số nguyên không âm n và k
Đầu ra: Dãy tất cả các tập con k phần tử của tập hợp n phần tử được sắp tăng theo thứ tự
từ điển
1 Begin
2 input n, k;
3 for i←− 1 to k do A[i]←− i;
4 p←− k;
5 while p ≥ 1 do
6 { print A[1..k];
7 if A[k] < n then p←− k else p←− p− 1;
8 if p ≥ 1 then
9 for i←− k downto p do A[i]←− A[p] + i− p+ 1};
10 End.
Độ phức tạp của thuật toán:
Chu trình 5-9 sinh ra một tập con k phần tử với độ phức tạp O(k). Vậy độ phức tạp tổng
thể của Thuật toán 4.2 là O(
(
n
k
)
.k).
5. BÀI TOÁN DÃY BỊ CHẶN VỚI RÀNG BUỘC
Trở lại với Bài toán 3.1, nếu ta đòi hỏi các dãy bị chặn t thỏa mãn ràng buộc (*) nào đó
thì ta có bài toán dãy bị chặn với ràng buộc.
Ràng buộc (*) thường được cho dưới dạng một bất biến đối với các dãy bị chặn cần tìm.
Khi đó, trong Thuật toán 3.1 thay câu lệnh 5 như sau:
5 if Dãy số T [1..n] thỏa mãn ràng buộc (*) then print T [1..n];
ta có một thuật toán đơn giản sinh các dãy bị chặn với ràng buộc bất kỳ.
Ứng dụng cho bài toán phân hoạch
Bài toán phân hoạch đặt ra như sau: Cho tập n phần tử X. Hãy tìm tất cả các phân hoạch
của tập này.
Mỗi phân hoạch của tập X là một họ các tập con không rỗng, đôi một không giao nhau
và hợp các tập con này lại phải cho ta đúng tập X.
Ký hiệu Π(X) là tập tất cả các phân hoạch của tập X. Số lượng các phân hoạch của tập
n phần tử là số Bell Bn được xác định theo công thức đệ quy sau đây [2, 4]:
Bn =
n−1∑
i=0
(
n− 1
i
)
Bi, trong đó B0 = 1.
88 HOÀNG CHÍ THÀNH
Giả sử pi = {A1, A2, ..., Ak} là một phân hoạch của tập X. Mỗi tập con Ai được gọi là
một khối của phân hoạch. Để đảm bảo tính duy nhất của biểu diễn, các khối trong một phân
hoạch được sắp xếp theo thứ tự tăng dần của phần tử bé nhất nằm trong mỗi khối.
Phần tử x ∈ X thuộc vào một khối Ai nào đó sẽ có chỉ số i, nghĩa là mỗi phần tử có thể
biểu diễn bởi chỉ số của khối chứa nó. Vậy mỗi phân hoạch sẽ được biểu diễn bởi một dãy n
chỉ số. Với biểu diễn dãy chỉ số thì số khối của phân hoạch bằng chính thành phần lớn nhất
trong dãy chỉ số. Dãy này có thể xem như là một từ có độ dài n trên bảng chữ cái X. Ta sắp
xếp các từ này tăng dần theo thứ tự từ điển. Khi đó thì,
- Từ nhỏ nhất (đầu tiên) sẽ là: 1 1 1 ... 1 - tương ứng với phân hoạch {{1, 2, 3, ..., n}} chỉ gồm
một khối là toàn bộ tập X.
- Từ lớn nhất (cuối cùng) sẽ là: 1 2 3 ... n - tương ứng với phân hoạch {{1}, {2}, {3}, ..., {n}}
có n khối, mỗi khối chỉ có một phần tử.
Dùng mảng nguyên A[1..n] để chứa dãy chỉ số của một phân hoạch trong máy tính. Phần
tử A[i] lưu chỉ số của khối chứa phần tử i.
- Phần tử 1 luôn thuộc khối thứ nhất (A[1] = 1).
- Phần tử 2 chỉ có thể thuộc khối thứ nhất hoặc khối thứ hai.
- Nếu phần tử 2 thuộc khối thứ nhất thì phần tử 3 chỉ có thể thuộc khối thứ nhất hoặc khối
thứ hai; còn nếu phần tử 2 thuộc khối thứ hai thì phần tử 3 có thể thuộc khối thứ nhất, thứ
hai hoặc thứ ba.
- Do vậy, phần tử i chỉ có thể thuộc các khối: 1, 2, ...,max(A[1], A[2], ..., A[i − 1]) + 1. Điều
này có nghĩa là:
1 ≤ A[i] ≤ max(A[1], A[2], ..., A[i− 1]) + 1 ≤ i. (5.1)
Ký hiệu Φ là tập tất cả các dãy số nguyên độ dài n với thành phần đầu tiên bằng 1, các
thành phần còn lại thuộc tập {1, 2, ..., n} và thỏa mãn (5.1). Lưu ý rằng, mỗi dãy trong tập
Φ đều chứa tất cả các số nguyên từ 1 đến số lớn nhất nằm trong dãy.
Xây dựng ánh xạ f : Π(X) −→ Φ như sau:
∀pi ∈ Π(X), f(pi) = A[1..n],
trong đó A[1..n] là biểu diễn dãy chỉ số của phân hoạch p được xác định như ở trên.
Định lý 5.1. Ánh xạ f là một song ánh từ tập Π(X) các phân hoạch lên tập Φ các dãy số
nguyên thỏa mãn (5.1).
Chứng minh:
Trước hết, ta chứng minh rằng f là một đơn ánh. Giả sử β, γ là hai phân hoạch nào đó
của tập X và β 6= γ. Phân hoạch β = {B1, B2, ..., Bk} có biểu diễn dãy chỉ số là B[1..n]
và phân hoạch γ = {C1, C2, ..., Cl} có biểu diễn dãy chỉ số là C[1..n]. Ta phải chỉ ra rằng
B[1..n] 6= C[1..n].
Xét hai trường hợp:
• k 6= l, hai phân hoạch trên có số khối khác nhau. Khi đó, các số lớn nhất trong mỗi dãy
B[1..n] và C[1..n] là khác nhau. Vậy hai dãy B[1..n] và C[1..n] là khác nhau.
• k = l, hai phân hoạch trên có chung số khối. Vì hai phân hoạch β, γ là khác nhau nên phải
tồn tại ít nhất một phần tử i ∈ X sao cho B[i] 6= C[i]. Vậy thì B[1..n] 6= C[1..n].
Bây giờ ta chỉ ra rằng ánh xạ f là một toàn ánh. Giả sử A[1..n] là một dãy số nguyên nào
đó thuộc tập Φ. Xây dựng họ η các tập con của tập X như sau
NGUYÊN LÝ KẾ THỪA VÀ MỘT SỐ BÀI TOÁN DÃY BỊ CHẶN 89
η = {A1, A2, ..., Ak}, trong đó k = max(A[i], i = 1, 2, ..., n),
và Aj = {i|i ∈ X, A[i] = j}, với j = 1, 2, ..., k. (5.2)
Theo nhận xét trên, các số nguyên 1, 2, ..., k đều xuất hiện trong dãy A[1..n], vậy các tập
con Aj đều khác rỗng. Mỗi phần tử i chỉ có một chỉ số A[i] nên nó chỉ thuộc vào một tập
con, nghĩa là các tập con trên đôi một rời nhau. Dãy số nguyên A[1..n] có độ dài n nên hợp
các tập con Aj lại phải cho ta tập X. Điều này chứng tỏ họ các tập con η = {A1, A2, ..., Ak}
là một phân hoạch của tập X nhận A[1..n] là biểu diễn dãy chỉ số của nó. Ánh xạ f là một
toàn ánh.
Vậy thì, f là một song ánh từ tập Π(X) lên tập Φ. 
Công thức (5.2) cho ta một cách đơn giản để xác định phân hoạch từ dãy chỉ số.
Định lý 5.1 chỉ ra rằng tập Φ bao gồm tất cả các dãy chỉ số của các phân hoạch trong
tập Π(X). Vậy để tìm các phân hoạch của tập n phần tử X ta chỉ cần tìm tất cả các dãy số
nguyên A[1..n] thuộc tập Φ được sắp tăng theo thứ tự từ điển.
Dùng mảng nguyên Maxi[1..n] để lưu dãy chỉ số lớn nhất có thể. Cụ thể là:
Maxi[1] = 0; Maxi[i] = max(A[1], A[2], ..., A[i− 1]), i = 2, 3, ..., n.
Hiển nhiên,
Maxi[i] = max(Maxi[i− 1], A[i− 1]) < i, i = 2, 3, ..., n. (5.3)
Xuất phát từ dãy chỉ số đầu tiên là: 1 1 1 ... 1 ta xây dựng vòng lặp để sinh ra các dãy
chỉ số còn lại.
Giả sử A[1..n] là một dãy chỉ số vừa tìm được. Ta cần phải tìm dãy chỉ số A′[1..n] kế tiếp
sau dãy chỉ số trên trong dãy được sắp tăng. Theo thứ tự từ điển, dãy chỉ số A′[1..n] được kế
thừa phần bên trái nhiều nhất có thể của dãy A[1..n]từ tọa độ 1 đến tọa độ thứ i− 1, với
i = max{j|A[j] ≤Maxi[j]}.
Khi đó, các tọa độ từ tọa độ đầu tiên đến tọa độ thứ i− 1 sẽ được giữ nguyên:
A′[j] = A[j], j = 1, 2, ..., i− 1.
Các tọa độ từ vị trí thay đổi i đến tọa độ cuối cùng được xác định như sau:
A′[i] = A[i] + 1, và A′[j] = 1, j = i+ 1, i+ 2, ..., n.
Việc sinh các dãy chỉ số kết thúc khi dãy chỉ số cuối cùng: 1 2 3 ... n− 1 n được sinh ra.
Khi đó thì
A[n] = n.
Đây cũng là điều kiện kết thúc của thuật toán.
Dựa vào các bất biến (5.1) và (5.3) của các dãy chỉ số và thứ tự từ điển, ta xây dựng thuật
toán lặp sinh các phân hoạch như sau.
Thuật toán 5.2. Sinh các phân hoạch của một tập hợp
90 HOÀNG CHÍ THÀNH
Đầu vào: Số nguyên dương n
Đầu ra: Dãy các phân hoạch của tập {1, 2, ..., n} mà các biểu diễn chỉ số của chúng được sắp
tăng theo thứ tự từ điển
1 Begin
2 input n;
3 A[1..n− 1]←− 1;
4 A[n]←−Maxi[1]←− 0;
5 repeat
6 for i←− 2 to n do
7 {Maxi[i]←−Maxi[i− 1];
8 if Maxi[i] < A[i− 1] then Maxi[i]←− A[i− 1]; }
9 i←− n;
10 while A[i] = Maxi[i] + 1 do {A[i]←− 1; i←− i− 1};
11 A[i]←− A[i] + 1;
12 print phân hoạch tương ứng với dãy chỉ số A[1..n];
13 until A[n] = n;
14 End.
Độ phức tạp của thuật toán:
Các câu lệnh 2-4 trong phần khởi tạo có độ phức tạp O(n).
Mỗi vòng lặp 6-12 sinh và in ra một phân hoạch:
- Chu trình 6-8 xây dựng mảng Maxi với độ phức tạp O(n).
- Các câu lệnh 9-11 tìm vị trí thay đổi i trên mảng chỉ số và xây dựng mảng chỉ số mới có độ
phức tạp O(n).
- Các câu lệnh 12 in phân hoạch có độ phức tạp O(n).
Vòng lặp 5-13 tìm hết Bn phân hoạch. Vậy độ phức tạp tổng thể của Thuật toán 5.2 là
O(n.Bn).
Thuật toán trên ngắn gọn và đơn giản hơn rất nhiều so với Thuật toán 1.19 trong [2] sinh
các phân hoạch bằng cách di chuyển một phần tử từ khối này sang khối khác nhờ các con trỏ
nguyên.
Thuật toán sinh các phân hoạch cùng các thuật toán trình bày ở trên có thể ứng dụng tốt
vào các bài toán khai phá dữ liệu và đặc biệt là bài toán phân lớp dữ liệu. Những ứng dụng
thuật toán sinh phân hoạch tập hợp vào các bài toán phân lớp dữ liệu, đặc biệt là các bài
toán phân lớp dữ liệu chuỗi theo thời gian (time-series data) cùng các ứng dụng trong y tế,
chứng khoán, môi trường,...
6. KẾT LUẬN
Bài báo đã đề xuất nguyên lý kế thừa để áp dụng trong việc thiết kế các thuật toán tối
ưu, đặc biệt là các thuật toán tổ hợp. Từ đó phát triển bài toán dãy bị chặn cùng ứng dụng
của nó và đề xuất hai dạng đặc biệt của bài toán trên là bài toán dãy đơn điệu bị chặn và bài
toán dãy bị chặn với ràng buộc. Đồng thời cũng chỉ ra rằng bốn bài toán tổ hợp quen thuộc
và có nhiều ứng dụng trong thực tế là: Bài toán tập con, bài toán tập con bội của tập bội, bài
toán tập con k-phần tử và bài toán phân hoạch đều có thể đưa về bài toán dãy bị chặn. Áp
dụng thuật toán của bài toán dãy bị chặn tổng quát để xây dựng các thuật toán cho bốn bài
NGUYÊN LÝ KẾ THỪA VÀ MỘT SỐ BÀI TOÁN DÃY BỊ CHẶN 91
toán tổ hợp trên. Các thuật toán này đều có thể song song hóa bằng kỹ thuật phân đoạn dãy
nghiệm như trình bày trong [6, 7]. Những kết quả nhận được góp phần phát triển các thuật
toán tổ hợp và có thể ứng dụng trong thực tế tính toán.
Việc nghiên cứu song song hóa các thuật toán đã xây dựng và phát triển bài toán dãy bị
chặn trong trường hợp các dãy biên thay đổi và áp dụng vào một số bài toán tính toán khác
là bài toán cần giải quyết.
TÀI LIỆU THAM KHẢO
[1] K.J. Batenburg and J. Sijbers, Generic iterative subset algorithms for discrete tomography,
Discrete Applied Mathematics 157 (3) (2009) 438–451.
[2] W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 1982.
[3] D. Singh, A. M. Ibrahim, T. Yohanna and J. N. Singh, An overview of the applications of
multisets, Novi Sad J. Math. 37 (2) (2007) 73–92.
[4] H.C. Thành, Giáo trình Tổ hợp, NXB ĐHQG Hà Nội, 1999.
[5] H.C. Thanh, Bounded sequence problem and some its applications, Proceedings of Japan -
Vietnam Workshop on Software Engineering, 2010 (74–83).
[6] H.C. Thanh and N.Q. Thanh, An efficient parallel algorithm for the set partition problem,
Studies in Computational Intelligence, Springer, Vol. 351 (2011) 25–32.
[7] H.C. Thanh, Parallel generation of permutations by inversion vectors, Proceedings of IEEE-
RIVF International Conference on Computing and Communication Technologies, IEEE,
2012 (129–132).
Ngày nhận bài 19 - 3 - 2012
Ngày lại sau sửa ngày 30 - 8 - 2012