Bài toán tìm dãy con tăng dài nhất là một trong các bài toán được nghiên cứu nhiều trong các lĩnh vực như toán học, thuật toán, lý thuyết vật lý.

Ví dụ: Dãy ban đầu gồm các phần tử: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

Dãy con tăng dài nhất sẽ là: 0, 2, 6, 9, 13, 15.

Có thể thấy rằng nghiệm của bài toán không là duy nhất, trong ví dụ trên chúng ta có hai nghiệm khác là: 0, 4, 6, 9, 11, 15 và 0, 2, 6, 9, 11, 15.

Cách tiếp cận đầu tiên và không hiệu quả đối với bài toán này là duyệt qua các tập con của dãy ban đầu và kiểm tra các điều kiện: dãy tăng và dài nhất. Với một dãy n phần tử bạn sẽ cần duyệt hết 2n tập con của dãy và điều này là không thể dù với những giá trị n khá nhỏ. Cách tiếp cận đúng đắn với bài toán này là sử dụng kỹ thuật qui hoạch động.

Trong bài báo này tôi sẽ trình bày với các bạn 3 thuật toán qui hoạch động để giải quyết bài toán LIS-LDS với độ phức tạp thời gian giảm dần.

2.Sắp xếp mảng với hàm qsort() trong C/C++

Trước hết là việc thực hiện sắp xếp một mảng (chúng ta sẽ cần dùng tới kiến thức này ở thuật toán thứ nhất) bằng hàm qsort() của C/C++. Để sắp xếp một mảng các phần tử có kiểu bất kỳ chúng ta chỉ cần cài đặt một hàm so sánh thứ tự giữa hai phần tử đó và gọi tới hàm qsort() (cài đặt thuật toán Quick sort) được cung cấp sẵn bởi C/C++.

Ví dụ để sắp xếp một mảng số nguyên ta cần khai báo hàm so sánh hai số nguyên như sau:

int cmp_function(const void *x, const void *y)

{

return (*(int*)(x)) - *((int*)(y)); // chuyển các con trỏ x và y thành con trỏ int *

}

Sau đó khi cần sắp xếp mảng a có n phần tử chúng ta sẽ gọi hàm qsort() theo cú pháp sau:

qsort(a, n,sizeof(int), cmp_function); // sizeof(int) là kích thước 1 phần tử của mảng a.

Việc cung cấp hàm so sánh để có thể làm việc với các kiểu dữ liệu khác dành lại cho các bạn độc giả như một bài tập nhỏ.

3.Bài toán tìm dãy con chung (LCS) của hai dãy

Đây là một bài toán khá phổ biến trong tin học, nhất là khi chúng ta học về qui hoạch động. Mục đích của bài toán là đi tìm dãy con chung (gồm 1 số phần tử) của hai dãy ban đầu có độ dài lớn nhất. Gọi hay dãy ban đầu là a gồm n phần tử và b gồm m phần tử (đánh chỉ số từ 0), chúng ta sẽ sử dụng các mảng hai chiều ret[][] và path[][] để lưu độ dài lớn của dãy con tìm được và giá trị truy hồi (mảng path) để tính ngược lại dãy con kết quả theo công thức sau:

Mỗi phần tử ret[i][j] sẽ là độ dài xâu con lớn nhất tương ứng với các dãy ban đầu a[0..i-1] và b[0..j-1], ban đầu các phần tử của mảng ret[][] sẽ được khởi tạo bằng 0.

Giá trị độ dài dãy con LCS lớn nhất được lưu tại biến ret[n][m] và đường đi sẽ được tính lại dựa trên giá trị của các biến path[i][j].

Để tìm hiểu kỹ hơn về thuật toán cho bài toán LCS các bạn có thể tham khảo trên các bài báo của tạp chí “Tin học và Nhà trường” các số trước đây.

Ở đây tôi xin đưa ra cài đặt cụ thể với ngôn ngữ C++ và dữ liệu demo cho bài toán LCS như sau:

include

using namespace std;

const int MAXMN = 100;

int ret[MAXMN][MAXMN];

int path[MAXMN][MAXMN];

int lcs(int a[], int n, int b[], int m);

void print_lcs(int a[], int i, int j);

int main()

{

int a[] = {1, 8, 2, 3, 18, 2, 6, 9};

int n = sizeof(a)/sizeof(int);

int b[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};

int m = sizeof(b)/sizeof(int);

cout << lcs(a, n, b, m) << endl;

print_lcs(b, n, m);

system("pause");

return 0;

}

int lcs(int a[], int n, int b[], int m)

{

int i, j;

int v;

memset(ret, 0, sizeof(ret));

for(i=1;i<=n;++i)

for(j=1;j<=m;++j)

{

if(a[i-1]==b[j-1])

{

v = ret[i-1][j-1] + 1;

path[i][j] = 0; // DIAG

}else if(ret[i-1][j]>ret[i][j-1])

{

v = ret[i-1][j];

path[i][j] = 1; // UP

}else

{

v = ret[i][j-1];

path[i][j] = 2; // LEFT

}

ret[i][j] = v;

}

return ret[n][m];

}

void print_lcs(int a[], int i, int j)

{

if(i==0||j==0)

return;

if(path[i][j]==0)

{

print_lcs(a, i-1, j-1);

cout << a[i-1] <<" ";

}else

if(path[i][j]==1)

print_lcs(a, i-1, j);

else

print_lcs(a, i, j-1);

}

Cài đặt trên của bài toán LCS có 2 vòng lặp chính nên dễ thấy độ phức tạp thuật toán là T(n, m) = O(n*m).

4.Thuật toán 1: tìm dãy LIS-LDS dựa vào bài toán LCS

Chúng ta sẽ xem xét thuật toán thứ nhất cho bài toán, thuật toán này dựa trên ý tưởng sau: nếu a là dãy ban đầu và b là kết quả của việc sắp xếp dãy a thì LIS của dãy a chính là LCS của dãy a và dãy b.

Cụ thể với cài đặt của bài toán LCS ở phần 3 chúng ta sẽ có thêm các hàm sau phục vụ cho việc tìm LIS của mảng a:

int cmp_function(const void *x, const void *y)

{

return (*(int*)(x)) - *((int*)(y));

}

int get_lis1(int a[], int n)

{

int * b = new int[n];

int i;

for(i=0;i

b[i] = a[i];

qsort(b, n,sizeof(int), cmp_function);

return lcs(a, n, b, n);

}

Để in ra nghiệm của bài toán chúng ta gọi tới hàm print_lcs() với các tham số là mảng a và n như sau: print_lcs(a, n, n);

Do thuật toán sắp xếp Quick sort có độ phức tạp là O(nlogn) và thuật toán cho bài toán LCS cho hai mảng a, b có độ phức tạp là O(n*n) = O(n2) nên thuật toán 1 có độ phức tạp là O(n2).

5.Thuật toán 2: tìm dãy LIS-LDS với độ phức tạp O(n2)

Chúng ta sẽ xem xét một thuật toán qui hoạch động tốt hơn cho bài toán LIS, lần này chúng ta sẽ sử dụng một mảng 1 chiều d[] để lưu độ dài dãy LIS của mảng a theo công thức truy hồi sau:

d[i] lưu giá trị LIS của mảng a[0..i], ban đầu d[i] = 1 với mọi i, nghiệm của bài toán sẽ là giá trị max của mảng d sau khi đã tính toán xong cho các giá trị i=0..n-1.

Để có thể tìm lại được nghiệm chúng ta dùng một mảng prev[] để dánh dấu mỗi điểm mà d[i] = d[j] + 1, khi đó prev[i] = j, ban đầu các phần tử của mảng prev[] đều bằng -1. Việc in nghiệm được thực hiện bằng 1 hàm đệ qui dựa trên giá trị của mảng prev[] và vị trí cuối cùng của nghiệm (phần tử cuối cùng của dãy LIS tìm được) được lưu ở biến lasti.

Cài đặt cụ thể bằng C++ như sau:

include

using namespace std;

const int MAXN = 100;

int a[] = {9,2,5,3,7,11,8,10,13,2}; // data array

int prev[MAXN];

int lasti = 0;

int get_lis0(int a[], int n);

void print_lis(int a[], int n, int lasti);

int main()

{

int n = sizeof(a)/sizeof(int);

int i;

cout << "Mang ban dau: ";

for(i=0;i

cout << a[i] << " ";

cout << " So phan tu cua LIS:" << get_lis2(a, n) << endl;

print_lis(a, n, lasti);

system("pause");

return 0;

}

int get_lis2(int a[], int n)

{

int * d = new int [n]; // hold max lis length of i location

int i, j;

int temp;

for(i=0;i

{

prev[i] = -1;

d[i] = 1;

}

for(i=1;i

{

// recalculate d[i];

temp = d[i];

for(j=i-1;j>=0;--j)

if(a[i]>a[j]&&d[j]+1>temp)

{

prev[i] = j;

temp = d[j]+1;

}

d[i] = temp;

}

temp = d[0];

for(i=0;i

if(d[i]>temp)

{

lasti = i;

temp = d[i];

}

return temp;

}

void print_lis(int a[], int n, int lasti)

{

if(prev[lasti]!=-1)

print_lis(a, n, prev[lasti]);

cout << a[lasti] << " ";

}

Đoạn thực hiện chính của thuật toán là vòng lặp for với biến i và vòng lặp for với biến j nên độ phức tạp của thuật toán là T(n) = O(n2). Tuy nhiên có thể thấy rõ là thuật toán thứ hai này nhanh hơn và hiệu quả hơn về bộ nhớ so với thuật toán thứ nhất.

6.Thuật toán 3: tìm dãy LIS-LDS với độ phức tạp O(nlogn)

Chúng ta sẽ xem xét thuật toán tốt hơn cho bài toán LIS với độ phức tạp O(nlogn). Thuật toán sử dụng mảng d[] để lưu các phần tử của nghiệm (chính là LIS tìm được ở mỗi bước), d[k] sẽ là giá trị nhỏ nhất của dãy LIS gồm k phần tử tìm được ở một bước của bài toán, một mảng ind[] sẽ được sử dụng để lưu chỉ số của các phần tử của mảng d[] trong mảng a[] ban đầu, một mảng lasti[] sẽ được sử dụng để lưu giá trị nhỏ hơn đứng ngay trước a[i] trong mỗi bước của thuật toán.

Ví dụ với mảng ban đầu a[] = {9, 2, 5, 3, 7, 11, 8, 10, 13, 6} chúng ta sẽ có:

Tiếp theo chúng ta sẽ có:

Có thể thấy nghiệm trong trường hợp này là 2, 3, 7, 8, 10, 13. Thuật toán sẽ có một vòng lặp với biến i chạy từ phần tử đầu tiên của mảng ban đầu cho tới hết, mỗi bước chúng ta sẽ sử dụng thuật toán tìm kiếm nhị phân để tìm vị trí của phần tử a[i] trong mảng d, sau đó cập nhật lại các giá trị của các phần tử trong mảng ind và lasti. Cụ thể thuật toán được cài đặt như sau:

include

using namespace std;

const int MAXN = 100;

int get_lis3(int a[], int n);

void print(int i);

int last;

int ind[MAXN]; // backtrack array

int lasti[MAXN]; // backtrack array

int a[] = {9, 2, 5, 3, 7, 11, 8, 10, 13, 6}; // data array

int main()

{

int n = sizeof(a)/sizeof(int);

cout << "Do dai LIS tim duoc:" << get_lis3(a, n) << endl;

cout << "Nghiem: ";

print(last);

system("pause");

return 0;

}

int get_lis3(int a[], int n)

{

// mang d: luu mang gia tri cua day LIS/LDS

// mang ind: luu vi tri cua cac phan tu d[i] trong mang a

// mang lasti: luu vi tri phan tu nho hon dung ngay truoc a[i]

int i, l, r, m, len, index;

int * d = new int [n];

d[0] = a[0];

len = 1;

ind[0] = 0;

lasti[0] = -1;

last = 0;

for (i=1; i

if (a[i] > d[len-1]) {

index = len;

last = i;

len += 1;

} else {

l = 0;

r = len-1;

while(l<=r)

{

m = l+(r-l)/2;

if(d[m]>=a[i])

r = m-1;

else

l = m+1;

}

if (d[l] >= a[i])

index = l;

else

index = r;

}

d[index] = a[i];

ind[index] = i;

if(index==0)

lasti[i] = -1;

else

lasti[i] = ind[index-1];

}

delete []d;

return len;

}

void print(int i)

{

if(lasti[i]==-1)

{

cout << a[i] << " ";

return;

}

print(lasti[i]);

cout << a[i] << " ";

}

Vòng lặp chính của thuật toán chạy với n bước, mỗi bước thực hiện tìm kiếm nhị phân trên mảng d có không quá i phần tử nên thuật toán sẽ có độ phức tạp T(n) = O(nlogn). Đây là thuật toán hiệu quả nhất cho bài toán LIS-LDS.

Mặc dù đã hết sức thận trọng và xem xét kỹ lưỡng các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: [email protected].