.png)
QUY HOẠCH ĐỘNG
I. Quy hoạch động là gì?
1. Đệ quy và quy hoạch động :
- Như các bạn đã biết đến phương pháp đệ quy ở chương trước, phương pháp đệ quy tính toán các bài toán bằng cách giải quyết các bài toán nhỏ hơn thông qua lời gọi hàm đến chính nó. Tuy nhiên phương pháp đệ quy thường sử dụng bộ nhớ lớn và thời gian tính toán khổng lồ. Và quy hoạch động là một kỹ thuật nhằm cải thiện hai nhược điểm lớn trên của đệ quy là sử dụng bộ nhớ lớn và thời gian tính toán rất lớn.
- Quy hoạch động là một phương pháp khó, vì mỗi bài toán tối ưu đều có một đặc thù riêng, nên cách giải quyết hoàn toàn khác nhau đòi hỏi người lập trình phải nắm vững bản chất của quy hoạch động.
2. Quy hoạch động là gì ?
- Trạng thái là gì? Trạng thái là một trường hợp, một bài toán con của 1 bài toán lớn.
- Quy hoạch động : Quy hoạch động là kĩ thuật được dùng khi có một công thức hoặc một (một vài) trạng thái bắt đầu. Một bài toán được tính bởi các bài toán nhỏ hơn đã được tìm ra từ trước, và kết quả các bài toán sẽ được lưu lại để những lần tính toán tiếp theo nếu cần đến những kết quả đó thì không cần tốn thêm thời gian thực hiện lại những bài toán này nữa. Nói cách khác, quy hoạch động bắt đầu từ việc giải các bài toán nhỏ, để từ đó từng bước giải quyết bài toán lớn hơn , và cuối cùng là bài toán lớn nhất ( bài toán ban đầu).
QHĐ có độ phức tạp đa thức nên sẽ chạy nhanh hơn quay lui và duyệt trâu.
3. Ưu nhươc điểm :
- Ưu điểm : chương trình chạy nhanh, mang tính tối ưu hóa cao
- Nhược điểm : + Sự kết hợp giữa các bài toán con chưa chắc cho ta bài toán lớn.
+ Số lượng các bài toán con cần giải quyết có thể rất lớn.
II. Hai cách tiếp cận quy hoạch động.
Bài toán ví dụ : Tìm số Fibonacci thứ n: xây dựng hàm tính trực tiếp dãy Fibo thứ n theo định nghĩa toán học với công thức truy hồi : F[k] = F[k-1] + F[k-2] , F[0] = 1 , F[1] =1. Cho n tìm F[n]. Chúng ta sẽ tìm cách giải quyết bài toán này bằng các cách tiếp cận dưới đây.
Cách giải thông thường khi dùng đệ quy, quay lui : Độ phức tạp cho phương pháp này là O(2^n) vì mỗi lần gọi hàm tính F[k] ta phải gọi đến hai bài toán con, và phải đi sâu tính lại các bài toán con đó. Ví dụ : Fibo(4) = Fibo(3)+Fibo(2) , Fibo(3) = Fibo(2)+Fibo(1) : ở đây Fibo(3) phải thực hiện tính 2 lần và với n bài toán đều phải tính lại 2 lần sẽ khiến độ phức tạp là O(2^n), tuy nhiên quy hoạch động có lưu trữ các bài toán và có thể giải quyết điều này.
Quy hoạch động thường dùng một trong hai cách tiếp cận :
1. Top-down (Từ trên xuống):
Bài toán được chia thành các bài toán con, các bài toán con này được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại chúng, và các bài toán con này tiếp tục gọi đến bài toán con của chúng đến khi đủ dữ kiện để lấy ra kết quả tính toán.
Đây là kỹ thuật đệ quy và lưu trữ được kết hợp với nhau, quy hoạch động giải quyết.
Áp dụng với bài toán ví dụ : Ta sẽ thực hiện lời gọi tính toán trực tiếp đến bài toán gốc Fibo (n) và bài toán này sẽ được chia nhỏ và sau khi tính được kết quả sẽ được lưu trữ vào mảng, và khi gặp lại bài toán đã được tính toán rồi ta sẽ không cần thực hiện đệ quy đi sâu vào để giải quyết của bài toán con đó nữa.
Phân tích độ phức tạp : So với phương pháp đệ quy –quay lui, cách tiếp cận này lưu trữ lại những bài toán đã được tính và khi cần không cần phải đi sâu vào nữa, bài toán Fibo(k) gọi đến hai bài toán nhỏ hơn nên số lượng bài toán tối đa là n +1 bài toán Fibo(0) … Fibo(n) và khi tính được đến đâu ta lưu trữ kết quả mỗi bài toán lại đến đó nên bài toán tương đương với tối đa n+1 lần lưu trữ nên độ phức tạp của thuật toán chỉ là O(n). Và đương nhiên quy hoạch động có thể chạy với n lên đến hàng triệu trong khi đệ quy quay lui chỉ chạy với n rất nhỏ (n < 25).
Từ đó cho ta thấy cách giải quyết của quy hoạch động cho ta độ phức tạp chỉ là số lượng bài toán và có thể nhân thêm với chi phí chuyển bài toán (ở những bài toán khác) ở đây là phép tính trực tiếp nên độ phức tạp là O(n*1) ~ O(n).
2. Bottom-up (Từ dưới lên):
Tất cả các bài toán con có thể cần đến đều được giải trước (từ bài toán cơ sở trở đi) , sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn.
Cách tiếp cận này tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khi việc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trước không được trực quan như Top-down.
Cách tiếp cận này cho ta thấy rõ độ phức tạp của thuật toán quy hoạch động : một vòng for O(n). Ở đây ta thực hiện chuẩn bị sẵn các bài toán đã tính được : đầu tiên là F[0] và F[1] sau đó sẽ lần lượt tính các F[2] -> F[3] … và cuối cùng sẽ được F[n] là kết quả bài toán. Cách tiếp cận này code sẽ ngắn gọn hơn nhiều nhưng với nhiều bài toán phức tạp hơn thì sẽ không trực quan như Top-down do phải điều chỉnh thứ tự gọi các bài toán cho lần lượt ở vòng for để đúng với quy trình đi từ nhỏ đến lớn. Tuy nhiên các tiếp cận này luôn tốt hơn khi cài đặt chính xác do đây là giải thuật khử đệ quy cho bài toán Top-down.
3. Phương pháp giải bài toán quy hoạch động :
Để giải quyết bài toán quy hoạch động ta chỉ cần xác định được hai vấn đề :
Và để có được công thức truy hồi, ta phải xác định được bài toán với đủ dữ kiện để có thể xây dựng được công thức truy hồi đi đến bài toán lớn nhất.
Do mỗi bài toán quy hoạch động đều có đặc thù riêng nên để hiểu rõ cách xác định bài toán và xây dựng bài toán cơ sở và công thức truy hồi, các bạn sẽ được xem ví dụ cụ thể cho một số bài toán quy hoạch động ở bài viết "Một số bài toàn, ví dụ về quy hoạch động" tại Nhanduccc's Blog.
I. Quy hoạch động là gì?
1. Đệ quy và quy hoạch động :
- Như các bạn đã biết đến phương pháp đệ quy ở chương trước, phương pháp đệ quy tính toán các bài toán bằng cách giải quyết các bài toán nhỏ hơn thông qua lời gọi hàm đến chính nó. Tuy nhiên phương pháp đệ quy thường sử dụng bộ nhớ lớn và thời gian tính toán khổng lồ. Và quy hoạch động là một kỹ thuật nhằm cải thiện hai nhược điểm lớn trên của đệ quy là sử dụng bộ nhớ lớn và thời gian tính toán rất lớn.
- Quy hoạch động là một phương pháp khó, vì mỗi bài toán tối ưu đều có một đặc thù riêng, nên cách giải quyết hoàn toàn khác nhau đòi hỏi người lập trình phải nắm vững bản chất của quy hoạch động.
2. Quy hoạch động là gì ?
- Trạng thái là gì? Trạng thái là một trường hợp, một bài toán con của 1 bài toán lớn.
- Quy hoạch động : Quy hoạch động là kĩ thuật được dùng khi có một công thức hoặc một (một vài) trạng thái bắt đầu. Một bài toán được tính bởi các bài toán nhỏ hơn đã được tìm ra từ trước, và kết quả các bài toán sẽ được lưu lại để những lần tính toán tiếp theo nếu cần đến những kết quả đó thì không cần tốn thêm thời gian thực hiện lại những bài toán này nữa. Nói cách khác, quy hoạch động bắt đầu từ việc giải các bài toán nhỏ, để từ đó từng bước giải quyết bài toán lớn hơn , và cuối cùng là bài toán lớn nhất ( bài toán ban đầu).
QHĐ có độ phức tạp đa thức nên sẽ chạy nhanh hơn quay lui và duyệt trâu.
3. Ưu nhươc điểm :
- Ưu điểm : chương trình chạy nhanh, mang tính tối ưu hóa cao
- Nhược điểm : + Sự kết hợp giữa các bài toán con chưa chắc cho ta bài toán lớn.
+ Số lượng các bài toán con cần giải quyết có thể rất lớn.
II. Hai cách tiếp cận quy hoạch động.
Bài toán ví dụ : Tìm số Fibonacci thứ n: xây dựng hàm tính trực tiếp dãy Fibo thứ n theo định nghĩa toán học với công thức truy hồi : F[k] = F[k-1] + F[k-2] , F[0] = 1 , F[1] =1. Cho n tìm F[n]. Chúng ta sẽ tìm cách giải quyết bài toán này bằng các cách tiếp cận dưới đây.
Cách giải thông thường khi dùng đệ quy, quay lui : Độ phức tạp cho phương pháp này là O(2^n) vì mỗi lần gọi hàm tính F[k] ta phải gọi đến hai bài toán con, và phải đi sâu tính lại các bài toán con đó. Ví dụ : Fibo(4) = Fibo(3)+Fibo(2) , Fibo(3) = Fibo(2)+Fibo(1) : ở đây Fibo(3) phải thực hiện tính 2 lần và với n bài toán đều phải tính lại 2 lần sẽ khiến độ phức tạp là O(2^n), tuy nhiên quy hoạch động có lưu trữ các bài toán và có thể giải quyết điều này.
Quy hoạch động thường dùng một trong hai cách tiếp cận :
1. Top-down (Từ trên xuống):
Bài toán được chia thành các bài toán con, các bài toán con này được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại chúng, và các bài toán con này tiếp tục gọi đến bài toán con của chúng đến khi đủ dữ kiện để lấy ra kết quả tính toán.
Đây là kỹ thuật đệ quy và lưu trữ được kết hợp với nhau, quy hoạch động giải quyết.
Áp dụng với bài toán ví dụ : Ta sẽ thực hiện lời gọi tính toán trực tiếp đến bài toán gốc Fibo (n) và bài toán này sẽ được chia nhỏ và sau khi tính được kết quả sẽ được lưu trữ vào mảng, và khi gặp lại bài toán đã được tính toán rồi ta sẽ không cần thực hiện đệ quy đi sâu vào để giải quyết của bài toán con đó nữa.
Phân tích độ phức tạp : So với phương pháp đệ quy –quay lui, cách tiếp cận này lưu trữ lại những bài toán đã được tính và khi cần không cần phải đi sâu vào nữa, bài toán Fibo(k) gọi đến hai bài toán nhỏ hơn nên số lượng bài toán tối đa là n +1 bài toán Fibo(0) … Fibo(n) và khi tính được đến đâu ta lưu trữ kết quả mỗi bài toán lại đến đó nên bài toán tương đương với tối đa n+1 lần lưu trữ nên độ phức tạp của thuật toán chỉ là O(n). Và đương nhiên quy hoạch động có thể chạy với n lên đến hàng triệu trong khi đệ quy quay lui chỉ chạy với n rất nhỏ (n < 25).
Từ đó cho ta thấy cách giải quyết của quy hoạch động cho ta độ phức tạp chỉ là số lượng bài toán và có thể nhân thêm với chi phí chuyển bài toán (ở những bài toán khác) ở đây là phép tính trực tiếp nên độ phức tạp là O(n*1) ~ O(n).
2. Bottom-up (Từ dưới lên):
Tất cả các bài toán con có thể cần đến đều được giải trước (từ bài toán cơ sở trở đi) , sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn.
Cách tiếp cận này tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khi việc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trước không được trực quan như Top-down.
Cách tiếp cận này cho ta thấy rõ độ phức tạp của thuật toán quy hoạch động : một vòng for O(n). Ở đây ta thực hiện chuẩn bị sẵn các bài toán đã tính được : đầu tiên là F[0] và F[1] sau đó sẽ lần lượt tính các F[2] -> F[3] … và cuối cùng sẽ được F[n] là kết quả bài toán. Cách tiếp cận này code sẽ ngắn gọn hơn nhiều nhưng với nhiều bài toán phức tạp hơn thì sẽ không trực quan như Top-down do phải điều chỉnh thứ tự gọi các bài toán cho lần lượt ở vòng for để đúng với quy trình đi từ nhỏ đến lớn. Tuy nhiên các tiếp cận này luôn tốt hơn khi cài đặt chính xác do đây là giải thuật khử đệ quy cho bài toán Top-down.
3. Phương pháp giải bài toán quy hoạch động :
Để giải quyết bài toán quy hoạch động ta chỉ cần xác định được hai vấn đề :
- Thứ nhất là : Bài toán cơ sở.
- Thứ hai là : Công thức truy hồi.
Và để có được công thức truy hồi, ta phải xác định được bài toán với đủ dữ kiện để có thể xây dựng được công thức truy hồi đi đến bài toán lớn nhất.
Do mỗi bài toán quy hoạch động đều có đặc thù riêng nên để hiểu rõ cách xác định bài toán và xây dựng bài toán cơ sở và công thức truy hồi, các bạn sẽ được xem ví dụ cụ thể cho một số bài toán quy hoạch động ở bài viết "Một số bài toàn, ví dụ về quy hoạch động" tại Nhanduccc's Blog.
Không có nhận xét nào:
Đăng nhận xét