TIN TỨC CẬP NHẬT
Bài toán dãy con tăng – giảm dài nhất
2 posters
Trang 1 trong tổng số 1 trang
Bài toán dãy con tăng – giảm dài nhất
Nguồn: [You must be registered and logged in to see this link.]
1. Bài toán dãy con tăng – giảm dài nhất
Bài toán tìm dãy con tăng-giảm dài nhất được phát biểu như sau: cho một dãy số nguyên (hoặc 1 dãy số, một xâu ..) gồm n phần tử. Hãy tìm một dãy con gồm các phần tử của dãy ban đầu (giữ nguyên thứ tự) sao cho các phần tử của dãy con đó tạo thành một dãy tăng-giảm dần và dài nhất có thể được. Các phần tử của dãy con dài nhất tìm được (nghiệm của bài toán) không nhất thiết phải là các phần tử liên tiếp trong dãy ban đầu. Vì việc tìm một dãy con tăng dài nhất cũng tương tự như việc tìm một dãy con giảm dài nhất nên chúng ta sẽ chỉ xem xét bài toán tìm dãy con dài nhất. Các kiến thức tương tự cũng sẽ được áp dụng cho bài toán tìm dãy con giảm dài nhất.
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:
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:
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:
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:
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:
1. Bài toán dãy con tăng – giảm dài nhất
Bài toán tìm dãy con tăng-giảm dài nhất được phát biểu như sau: cho một dãy số nguyên (hoặc 1 dãy số, một xâu ..) gồm n phần tử. Hãy tìm một dãy con gồm các phần tử của dãy ban đầu (giữ nguyên thứ tự) sao cho các phần tử của dãy con đó tạo thành một dãy tăng-giảm dần và dài nhất có thể được. Các phần tử của dãy con dài nhất tìm được (nghiệm của bài toán) không nhất thiết phải là các phần tử liên tiếp trong dãy ban đầu. Vì việc tìm một dãy con tăng dài nhất cũng tương tự như việc tìm một dãy con giảm dài nhất nên chúng ta sẽ chỉ xem xét bài toán tìm dãy con dài nhất. Các kiến thức tương tự cũng sẽ được áp dụng cho bài toán tìm dãy con giảm dài nhất.
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:
- Code:
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 *
}
- Code:
qsort(a, n,sizeof(int), cmp_function); // sizeof(int) là kích thước 1 phần tử của mảng a.
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:
- 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);
}
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:
- 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);
}
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:
- 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] << " ";
}
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:
- 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] << " ";
}
Trang_Pham- THƯỢNG TƯỚNG V
- Tổng số bài gửi : 616
Join date : 18/09/2010
Age : 32
Đến từ : Vietnam
Similar topics
» Bài toán tìm cặp điểm gần nhất
» Sự liên hệ giữa bài toán LCA và bài toán RMQ
» Phần mềm giảm dung lượng cho các file nhạc MP3
» he toan phim dom a.vo day download toan phim HAY ne.
» Một bài toán về bàn cờ.
» Sự liên hệ giữa bài toán LCA và bài toán RMQ
» Phần mềm giảm dung lượng cho các file nhạc MP3
» he toan phim dom a.vo day download toan phim HAY ne.
» Một bài toán về bàn cờ.
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết