Bài toán "Dãy con đơn điệu tăng dài nhất"

Hướng dẫn từng bước trong quá trình phân tích, thiết kế và cài đặt thuật toán để giải bài toán "Dãy con đơn điệu tăng dài nhất" bằng phương pháp quy hoạch động.

 

1. Phát biểu bài toán

Cho dãy A gồm n số nguyên, ký hiệu [a0, a1,..., an-1] . Tìm một dãy con đơn điệu tăng dài nhất của dãy A, biết một dãy con của A là dãy có được từ A bằng cách xóa đi một số phân tử của A. Ví dụ: dãy [1, 5, 9, 2, 3, 11, 8, 10, 4] có dãy con đơn điệu tăng dài nhất là [1, 2, 3, 8, 10].

2. Nhận định ban đầu

Số dãy con của a

Chúng ta có thể xem mỗi dãy con a của A tương ứng với một chuỗi nhị phân b độ dài n, trong đó,  bi = 0 nghĩa là ai không thuộc a và ngược lại bi = 1 nghĩa là ai thuộc a. Ví dụ nếu A = [1, 3, 2, 3] thì dãy con tương ứng với chỗi nhị phân b = 1010[1, 3]. Như vậy, số dãy con của A cũng chính là số chuỗi nhị phân có độ dài n chính là 2n. Mặc dù có thể với 2 chuỗi nhị phân khác nhau sẽ tương ứng với cùng một dãy con (với mảng A = [1, 3, 2, 3], hai chuỗi 11001001 cùng tương ứng với dãy con [1, 3]), nhưng nếu lập trình bình thường để duyệt tất cả các dãy con của A thì phải duyệt 2n phần tử. Với n = 100 thì có đến 2100 ≈ 1030 dãy con.

Phương án khả thi

Phương án duyệt tất cả các dãy con để tìm kết quả tối ưu có độ phức tạp là O(2n), rõ ràng là không khả thi khi n lớn. Có cách nào khác để tìm được dãy con tối ưu mà không phải duyệt tất cả? Chúng ta thử cân nhắc phương pháp Quy hoạch động hay Đệ quy xem thử thế nào, nghĩa là tìm cách chia bài toán ban đầu thành các bài toán con :-?

3. Ý tưởng

Tìm cách chia nhỏ bài toán

Suy nghĩ đầu tiên khi cân nhắc phương pháp Quy hoạch động hay Đệ quy luôn là "Làm sao để chia bài toán lớn thành các bài toán con đây?". Có thể có nhiều cách chia bài toán lớn thành các bài toán con. Để cho tiện, ta gọi bài toán ban đầu là Bt(n) - tìm dãy con đơn điệu tăng dài nhất của n phần tử trong dãy A. Thử "chia" theo cách này xem sao: gọi Bt(k), với k < n, là bài toán tìm dãy con đơn điệu tăng dài nhất của k phần tử đầu tiên trong dãy A mà dãy con này có chứa phần tử ak. Có thể tìm ra ngay kết quả của Bt(k) - chỉ đơn giản là dãy con gồm 1 phần tử: a0 (cơ sở quy hoạch động).

Tìm cách "ghép" các bài toán nhỏ để giải bài toán lớn hơn

Giả sử đã giải được k bài toán đầu tiên Bt(0), Bt(1),... ,Bt(k-1). Làm sao sử dụng các kết quả này để giải được bài toán Bt(k)? Một cách đơn giản là sẽ thử cho ak lần lượt "kết hợp" với tất cả các kết quả tối ưu của k bài toán này, sau đó chọn phương án kết hợp tối ưu nhất (cho dãy con dài nhất). Việc kết hợp ak với 1 dãy con phía trước chỉ đơn giản là: nếu ak lớn hơn hoặc bằng phần tử cuối cùng của dãy thì ak sẽ được "gắn" vào, còn nếu ngược lại thì ak không thể "gắn" vào.

Ví dụ với dãy A ở trên, giả sử đã có được: Bt(0) → [1], Bt(1) → [1, 5], Bt(2) → [1, 5, 9]. Với k = 3, Bt(3) → [?]. Rõ ràng không thể ghép a3 sau [1, 5, 9]a3 = 2 < 9. Ta chỉ có thể ghép a3 sau [1]. Như vậy, Bt(3) → [1, 2].

Xuất phát từ Bt(0), theo cách "ghép" trên, ta cứ lần lượt tìm kết quả cho các bài toán Bt(1), Bt(2), ... , Bt(n-1). Một chú ý rằng, kết quả của Bt(n-1) chưa chắc là kết quả cuối cùng của bài toán vì dãy con đơn điệu tăng dài nhất của A chưa chắc đã chứa an-1. Do vậy, để tìm dãy con đơn điệu tăng dài nhất của A, ta phải duyệt tất cả n bài toán con vừa giải để chọn ra dãy con dài nhất.

Ví dụ với dãy A [1, 5, 9, 2, 3, 11, 8, 10, 4], ta có thể tìm ra được kết quả của n bài toán con như sau:

Bt(0) → [1] Bt(3) → [1, 2] Bt(6) → [1, 2, 3, 8]
Bt(1) → [1, 5] Bt(4) → [1, 2, 3] Bt(7) → [1, 2, 3, 8, 10]
Bt(2) → [1, 5, 9] Bt(5) → [1, 5, 9, 11] Bt(8) → [1, 2, 3, 4]

Với ví dụ trên, ta có một số nhận xét sau:

  • Bt(5) có thể có một kết quả khác tương đương: [1, 2, 3, 11], nghĩa là dù kết quả nào được chọn cũng không ảnh hưởng đến kết quả cuối cùng của bài toán.
  • Kết quả của Bt(8) không phải là kết quả tối ưu, mà là kết quả của Bt(7).

Công thức truy hồi

Từ ý tưởng trên, ta có được công thức truy hồi để giải bài toán này như sau:

4. Phương pháp

Lập bảng phương án

 Dựa vào công thức truy hồi ở trên, ta sẽ xây dựng mảng L như sau:

  • Đầu tiên, l0 = 1 (cơ sở quy hoạch động)
  • Tiếp theo, lần lượt tính các lk với k = 1..n-1  theo các bước sau:
    1. Đặt max = 0
    2. Cho một biết i chạy từ 1 đến k-1, với mỗi i:
      • Nếu ai < akmax < li + 1 thì cập nhật giá trị của max = li + 1.
      • Nếu aiakmax < li  thì cập nhật giá trị của max = li .
    3. lk = max

Sau khi tính xong mảng L, độ dài của dãy con đơn điệu tăng dài nhất (lmax) chỉ đơn giản là giá trị lớn nhất của các phần tử trong mảng L:

Truy vết

Từ mảng L ta chỉ mới biết được độ dài của dãy con tối ưu ứng với mỗi bài toán con. Từ L, ta khó mà "lần ra" được dãy con tối ưu cụ thể và do đó chưa thể đưa ra được dãy con tối ưu của dãy A. Như ở ví dụ ban đầu, khi tính được L = [1, 2, 3, 2, 3, 4, 4, 5, 4] ta chỉ mới biết lmax = 5 (tại vị trí k = 7) và dãy con đơn điệu tăng dài nhất sẽ có phần tử cuối là a7 = 10. Để tìm được các phần tử còn lại trong dãy con tối ưu, ta gần như phải làm như ở bước Lập bảng phương án. Điều này tương đối mất công.

Do vậy, để đơn giản và tiết kiệm công sức, trong quá trình xây dựng bảng phương án, ta chỉ cần tạo thêm một bảng T gồm n phần tử, trong đó tk sẽ lưu vị trí của phần tử ngay phía trước phần tử ak trong dãy con tối ưu của Bt(kk). Có thể nhận ra được rằng chính là vị trí i mà ta có được max (trong phần lập bảng phương án).

5. Đánh giá

Độ phức tạp của thuật toán là O(n2). Nói chung là tốt hơn rất nhiều so với O(2n) nhưng hình như vẫn còn chưa tốt lắm. Có một số cách để cải tiến thuật toán này. Có lẽ một ngày đẹp trời nào đó chúng ta sẽ tiếp tục tìm hiểu thêm.

6. Cài đặt

Dưới đây là mã nguồn đầy đủ của chương trình:

#include <stdio.h>
#include <conio.h>
#define m 8

void main()
{
	int a[m] = {1,4,5,9,2,6,7,10}; //dãy A
	int l[m]; //l[i]: độ dài DCĐĐTDN của dãy a[0],..,a[i] mà có chứa a[i]
	int t[m]; //t[i]: vị trí phần tử ngay phía trước a[i] trong DCĐĐTDN của dãy a[0],..,a[i]

	// Bước 1. Lập bảng phương án (tính mảng L và T)
	l[0] = 1; t[0] = -1; 
	for (int i=1; i<m; i++)
	{
		int max = 1; //độ dài DCĐĐTDN của dãy a[0],..,a[i]
		for (int j=0; j<i; j++)
			if (a[j] < a[i] && max < l[j] + 1)
			{
				max = l[j] + 1;
				t[i] = j; //để sau này truy vết: phần tử ngay phía sau a[i] là a[j]
			}
		l[i] = max;
	}

	//Bước 2. Tìm vị trí cuối của DCĐĐTDN
	int lMax = 0; //độ dài DCĐĐTDN của dãy A
	int viTriMax = 0; //a[viTriMax] sẽ là phần tử cuối cùng trong DCĐĐTDN của dãy A
	for (int i=1; i<m; i++)
		if (l[i] > lMax)
		{
			lMax = l[i];
			viTriMax = i;
		}

	//Bước 3. Truy vết để tìm DCĐĐTDN (kq): dựa vào T và viTriMax
	int kq[m]; 
	int k = lMax-1;
	do {
		kq[k] = a[viTriMax];
		k--;
		viTriMax = t[viTriMax];
	}while (k>=0);

	//Bước 4. Xuất kết quả
	printf("\n- Day A: "); //Hiển thị dãy A
	for (int i=0; i<m; i++) printf("%d ", a[i]);
	printf("\n- Day con don dieu tang dai nhat: "); //Hiển thị DCĐĐTDN
	for (int i=0; i<lMax; i++) printf("%d ", kq[i]);
	printf("\n  (gom %d phan tu)", lMax);
	getch(); //dừng màn hình để xem kết quả
}

Bình luận (5)

Viết Bình luận
  • danh idol
    tong quat

    tổng quát thì sao bạn.thanks nha

  • duong tl ln
    CHÁN ỨA

    chán ứa các bạn afk.mình được đi thi tỉnh nhưng chẳng biết giải mấy cái này

     

  • Binh
    Ok

    Không biết các bạn nói sao chứ, bài này text ok rồi mà!

  • @Đạt

    Đúng rồi, sai ở dòng 15:

    int max = 0; //đúng ra phải là int max=1;

    Nghĩa là dãy con xuất phát phải có độ dài là 1 (chính là phần tử đang xét, a[i]). Nếu để max=0 thì giống như "em bé đếm trâu" rồi, quên đếm con trâu đang cưỡi :-)

    Cám ơn bạn.

  • Đạt
    có lỗi!!!

    đoạn code trên của bạn có lỗi rồi. Khi bạn nhập dãy 10, 3, 2, 5, 7, 8, 19, 16. Thì thiếu mất số 3 hoặc 2. Mong bạn sửa lại. Dù sao cũng cám ơn bạn về bài phân tích trên.

Viết Bình luận

Họ tên Bắt buộc
Email Bắt buộc
Tiêu đề Bắt buộc
Kiểu bình luận
Nội dung
Nhập mã được hiển thị: