Bài toán dãy con tăng – giảm dài nhất

by **pkt_zz** 13/6/2010, 4:17 am

Nguồn: [You must be registered and logged in to see this link.]
1. Bài toán dãy con tăng – giảm dài nhất

Bài toán tìm dãy con tăng-giảm dài nhất được phát biểu như sau: cho một dãy số nguyên (hoặc 1 dãy số, một xâu ..) gồm n phần tử. Hãy tìm một dãy con gồm các phần tử của dãy ban đầu (giữ nguyên thứ tự) sao cho các phần tử của dãy con đó tạo thành một dãy tăng-giảm dần và dài nhất có thể được. Các phần tử của dãy con dài nhất tìm được (nghiệm của bài toán) không nhất thiết phải là các phần tử liên tiếp trong dãy ban đầu. Vì việc tìm một dãy con tăng dài nhất cũng tương tự như việc tìm một dãy con giảm dài nhất nên chúng ta sẽ chỉ xem xét bài toán tìm dãy con dài nhất. Các kiến thức tương tự cũng sẽ được áp dụng cho bài toán tìm dãy con giảm dài nhất.

Bài toán tìm dãy con tăng dài nhất là một trong các bài toán được nghiên cứu nhiều trong các lĩnh vực như toán học, thuật toán, lý thuyết vật lý.

Ví dụ: Dãy ban đầu gồm các phần tử: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

Dãy con tăng dài nhất sẽ là: 0, 2, 6, 9, 13, 15.

Có thể thấy rằng nghiệm của bài toán không là duy nhất, trong ví dụ trên chúng ta có hai nghiệm khác là: 0, 4, 6, 9, 11, 15 và 0, 2, 6, 9, 11, 15.

Cách tiếp cận đầu tiên và không hiệu quả đối với bài toán này là duyệt qua các tập con của dãy ban đầu và kiểm tra các điều kiện: dãy tăng và dài nhất. Với một dãy n phần tử bạn sẽ cần duyệt hết 2n tập con của dãy và điều này là không thể dù với những giá trị n khá nhỏ. Cách tiếp cận đúng đắn với bài toán này là sử dụng kỹ thuật qui hoạch động.

Trong bài báo này tôi sẽ trình bày với các bạn 3 thuật toán qui hoạch động để giải quyết bài toán LIS-LDS với độ phức tạp thời gian giảm dần.
2.Sắp xếp mảng với hàm qsort() trong C/C++

Trước hết là việc thực hiện sắp xếp một mảng (chúng ta sẽ cần dùng tới kiến thức này ở thuật toán thứ nhất) bằng hàm qsort() của C/C++. Để sắp xếp một mảng các phần tử có kiểu bất kỳ chúng ta chỉ cần cài đặt một hàm so sánh thứ tự giữa hai phần tử đó và gọi tới hàm qsort() (cài đặt thuật toán Quick sort) được cung cấp sẵn bởi C/C++.

Ví dụ để sắp xếp một mảng số nguyên ta cần khai báo hàm so sánh hai số nguyên như sau:

Code:: int cmp_function(const void *x, const void *y) { return (*(int*)(x)) - *((int*)(y)); // chuyển các con trỏ x và y thành con trỏ int * }

Sau đó khi cần sắp xếp mảng a có n phần tử chúng ta sẽ gọi hàm qsort() theo cú pháp sau:

Code:: qsort(a, n,sizeof(int), cmp_function); // sizeof(int) là kích thước 1 phần tử của mảng a.

Việc cung cấp hàm so sánh để có thể làm việc với các kiểu dữ liệu khác dành lại cho các bạn độc giả như một bài tập nhỏ.
3.Bài toán tìm dãy con chung (LCS) của hai dãy

Đây là một bài toán khá phổ biến trong tin học, nhất là khi chúng ta học về qui hoạch động. Mục đích của bài toán là đi tìm dãy con chung (gồm 1 số phần tử) của hai dãy ban đầu có độ dài lớn nhất. Gọi hay dãy ban đầu là a gồm n phần tử và b gồm m phần tử (đánh chỉ số từ 0), chúng ta sẽ sử dụng các mảng hai chiều ret[][] và path[][] để lưu độ dài lớn của dãy con tìm được và giá trị truy hồi (mảng path) để tính ngược lại dãy con kết quả theo công thức sau:
Bài toán dãy con tăng – giảm dài nhất Baitoandaycontanggiam1

Bài toán dãy con tăng – giảm dài nhất Baitoandaycontanggiam1

Mỗi phần tử ret[i][j] sẽ là độ dài xâu con lớn nhất tương ứng với các dãy ban đầu a[0..i-1] và b[0..j-1], ban đầu các phần tử của mảng ret[][] sẽ được khởi tạo bằng 0.

Giá trị độ dài dãy con LCS lớn nhất được lưu tại biến ret[n][m] và đường đi sẽ được tính lại dựa trên giá trị của các biến path[i][j].

Để tìm hiểu kỹ hơn về thuật toán cho bài toán LCS các bạn có thể tham khảo trên các bài báo của tạp chí “Tin học và Nhà trường” các số trước đây.

Ở đây tôi xin đưa ra cài đặt cụ thể với ngôn ngữ C++ và dữ liệu demo cho bài toán LCS như sau:

Code:: #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); }

Cài đặt trên của bài toán LCS có 2 vòng lặp chính nên dễ thấy độ phức tạp thuật toán là T(n, m) = O(n*m).
4.Thuật toán 1: tìm dãy LIS-LDS dựa vào bài toán LCS

Chúng ta sẽ xem xét thuật toán thứ nhất cho bài toán, thuật toán này dựa trên ý tưởng sau: nếu a là dãy ban đầu và b là kết quả của việc sắp xếp dãy a thì LIS của dãy a chính là LCS của dãy a và dãy b.

Cụ thể với cài đặt của bài toán LCS ở phần 3 chúng ta sẽ có thêm các hàm sau phục vụ cho việc tìm LIS của mảng a:

Code:: 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 của bài toán chúng ta gọi tới hàm print_lcs() với các tham số là mảng a và n như sau: print_lcs(a, n, n);

Do thuật toán sắp xếp Quick sort có độ phức tạp là O(nlogn) và thuật toán cho bài toán LCS cho hai mảng a, b có độ phức tạp là O(n*n) = O(n2) nên thuật toán 1 có độ phức tạp là O(n2).
5.Thuật toán 2: tìm dãy LIS-LDS với độ phức tạp O(n2)

Chúng ta sẽ xem xét một thuật toán qui hoạch động tốt hơn cho bài toán LIS, lần này chúng ta sẽ sử dụng một mảng 1 chiều d[] để lưu độ dài dãy LIS của mảng a theo công thức truy hồi sau:
Bài toán dãy con tăng – giảm dài nhất Baitoandaycontanggiam2

Bài toán dãy con tăng – giảm dài nhất Baitoandaycontanggiam2

d[i] lưu giá trị LIS của mảng a[0..i], ban đầu d[i] = 1 với mọi i, nghiệm của bài toán sẽ là giá trị max của mảng d sau khi đã tính toán xong cho các giá trị i=0..n-1.

Để có thể tìm lại được nghiệm chúng ta dùng một mảng prev[] để dánh dấu mỗi điểm mà d[i] = d[j] + 1, khi đó prev[i] = j, ban đầu các phần tử của mảng prev[] đều bằng -1. Việc in nghiệm được thực hiện bằng 1 hàm đệ qui dựa trên giá trị của mảng prev[] và vị trí cuối cùng của nghiệm (phần tử cuối cùng của dãy LIS tìm được) được lưu ở biến lasti.

Cài đặt cụ thể bằng C++ như sau:

Code:: #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] << " "; }

Đoạn thực hiện chính của thuật toán là vòng lặp for với biến i và vòng lặp for với biến j nên độ phức tạp của thuật toán là T(n) = O(n2). Tuy nhiên có thể thấy rõ là thuật toán thứ hai này nhanh hơn và hiệu quả hơn về bộ nhớ so với thuật toán thứ nhất.
6.Thuật toán 3: tìm dãy LIS-LDS với độ phức tạp O(nlogn)

Chúng ta sẽ xem xét thuật toán tốt hơn cho bài toán LIS với độ phức tạp O(nlogn). Thuật toán sử dụng mảng d[] để lưu các phần tử của nghiệm (chính là LIS tìm được ở mỗi bước), d[k] sẽ là giá trị nhỏ nhất của dãy LIS gồm k phần tử tìm được ở một bước của bài toán, một mảng ind[] sẽ được sử dụng để lưu chỉ số của các phần tử của mảng d[] trong mảng a[] ban đầu, một mảng lasti[] sẽ được sử dụng để lưu giá trị nhỏ hơn đứng ngay trước a[i] trong mỗi bước của thuật toán.

Ví dụ với mảng ban đầu a[] = {9, 2, 5, 3, 7, 11, 8, 10, 13, 6} chúng ta sẽ có:
Bài toán dãy con tăng – giảm dài nhất Baitoandaycontanggiam3

Bài toán dãy con tăng – giảm dài nhất Baitoandaycontanggiam3

Tiếp theo chúng ta sẽ có:
Bài toán dãy con tăng – giảm dài nhất Baitoandaycontanggiam4

Có thể thấy nghiệm trong trường hợp này là 2, 3, 7, 8, 10, 13. Thuật toán sẽ có một vòng lặp với biến i chạy từ phần tử đầu tiên của mảng ban đầu cho tới hết, mỗi bước chúng ta sẽ sử dụng thuật toán tìm kiếm nhị phân để tìm vị trí của phần tử a[i] trong mảng d, sau đó cập nhật lại các giá trị của các phần tử trong mảng ind và lasti. Cụ thể thuật toán được cài đặt như sau:

Code:: #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] << " "; }

Vòng lặp chính của thuật toán chạy với n bước, mỗi bước thực hiện tìm kiếm nhị phân trên mảng d có không quá i phần tử nên thuật toán sẽ có độ phức tạp T(n) = O(nlogn). Đây là thuật toán hiệu quả nhất cho bài toán LIS-LDS.

by **Trang_Pham** 1/10/2010, 8:38 pm

Bài toán dãy con tăng – giảm dài nhất

Bài toán dãy con tăng – giảm dài nhất

Re: Bài toán dãy con tăng – giảm dài nhất