DANH SÁCH BÀI VIẾT Tìm hiểu thuật toán Quy hoạch động Tìm hiểu về Hàm đệ quy Thuật toán tìm kiếm nhị Tìm hiểu về Thuật toán quay lui (Backtracking) Tìm hiểu thuật toán Loang Tìm hiểu thuật toán chia để trị Tìm hiểu thuật toán tham lam trong lập trình Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search) Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search) Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)
Trong bài viết này các bạn sẽ cùng blog tuicocachcom tìm hiểu về thuật toán quy hoạch động thần thánh. Đây là một thuật toán rất hay và nếu bạn tham gia các cuộc thi code như ICPC, olympic tin học hay các cuộc thi liên quan tới lập trình bạn nhất định phải biết thuật toán này.
Thuật toán Quy hoạch động
Thuật toán Quy hoạch động sẽ được áp dụng khi chúng ta muốn giải quyết một bài toán nào đó một cách tối ưu nhất về thời gian xử lý bài toán. Quy hoach động là một kĩ thuật thiết kế thuật toán theo kiểu chia bài toán lớn thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu.
Khác với chia để trị, quy hoạc động, thay vì gọi đệ quy, sẽ tính trước lời giải của các bài toán con và lưu vào bộ nhớ (thường là một mảng), và sau đó lấy lời giải của bài toán con ở trong mảng đã tính trước để giải bài toán lớn theo một công thức nào đó và ta gọi là công thức truy hồi trong quy hoạch động.
Mẫu chốt nhất trong thuật toán quy hoạch động thì cũng là việc mà chúng ta có thể tìm ra được công thức truy hồi trong từng bài toán hay không, mỗi bài toán thì có muôn hình vạn trạng thế nên ta không thể có một công thức chung nào cho tất cả các bài toán đó cả.
Vậy, khi nào thì ta nên và cần áp dụng thuật toán quy hoạch động?
Tất nhiên với một số bài toán khi đưa ra có thể sẽ có rất nhiều cách giải khác nhau, và bài toán đó có thể sẽ giải được bằng quy hoạch động nhưng cũng chưa hoàn toàn có thể khẳng định là tối ưu nhất, mà ta cũng có thể giải bằng cách khác tối ưu hơn. Thế nhưng cũng sẽ có một vài bài toán bắt buộc ta chỉ có thể giải được bằng quy hoạch động. Vậy khi nhìn vào bài toán thì khi nào nên áp dụng quy hoạch động?
- Bài toán có các bài toán con gối nhau.
- Bài toán có cấu trúc con tối ưu.
Câu trả lời là khi bài toán có đủ cả hai tính chất trên thì ta nên áp dụng quy hoạch động.
Thế nào là bài toán con gối nhau, một ví dụ rất điển hình của bài toán con gối nhau là bài toán tính số Fibonacci. Với số fibonacci thứ n sẽ được tính bằng cách cộng fibonacci thứ n-1 với n-2, và bài toán tính fibonacci n-1 và n-2 chính là bài toán con của tính fibonacci thứ n.
Thế nào là Bài toán có cấu trúc con tối ưu, thì cũng với số fibonaci như bạn đã biết thì fibonacci thứ 1 và 2 đều có giá trị bằng 1, như vậy với 2 bài toán con đó ta còn chưa cần tính đã có sẵn kết quả. Như vậy một bài toán có cấu trúc con tối ưu tức là một bài toán mà có bài toán con tối giản có thể dễ dàng tính toán được kết quả hoặc thậm chí không cần tính toán. Và như vậy từ bài toán con tối giản có thể áp dụng công thức truy hồi đưa vào quy hoạch động để đưa ra kết quả cuối cùng cho bài toán.
Áp dụng thuật toán quy hoạch động vào giải quyết một số bài toán đơn giản
Sau đây mình sẽ áp dụng thuật toán quy hoạch động vào 2 bài toán đơn giản đó là tính số fibonaci và tính giai thừa của một số, đây chỉ là các ví dụ để bạn hiểu rõ hơn về thuật toán quy hoạch động.
Giải quyết bài toán tính số fibonacci với quy hoạch động
Như đã nói ở trên thì để tính F(n) công thức là:
F(n) = F(n-1)+ F(n-2)
Và đây sẽ là công thức truy hồi sẽ được áp dụng trong quy hoạch động cho bài toán tính fibonacci, vậy ta viết chương trình quy hoạch động như sau
/*
//Thư viện này chỉ có những người lười ms dùng như vậy thôi :)) =>
Thư viện này bao gồm hầu hết các thư viện trong c/c++ ngoại trừ 1 số thư viện như conio.h, windows.h.....
Vì vậy nên quá trình biên dịch sẽ lâu hơn một chut :))(mà vẫn nhanh vãi đ** thôi hahah) tất nhiên là biên dịch chứ kg ảnh hưởng thời gian chạy của chương trình
*/
#include <bits/stdc++.h>
using namespace std;
//Hàm quy hoạch động
int QHD(int n)
{
int fibo[100];
//gắn 2 kết quả tối giản nhất của bài toán
fibo[0] = 1;
fibo[1] = 1;
int i;
for(i = 2; i<n;i++)
{
fibo[i] = fibo[i-1] + fibo[i-2] ; //công thức truy hồi
}
//Trả về kết quả
return fibo[n];
}
int main()
{
int n = 15;
cout<<"Fibonacci n la: "<<QHD(n);
}
Giải quyết bài toán tính giai thừa của 1 số với quy hoạch động
Công thức truy hồi trong bài toán này sẽ là Giai thừa (n) = n * Giai thừa(n-1).
Vậy ta sẽ viết hàm quy hoạch động như sau:
#include <bits/stdc++.h>
using namespace std;
int QHD(int n)
{
int gt[100];
gt[0] = 1;
gt[1] = 1;
for(int i = 2; i<n;i++)
{
gt[i] = i * gt[i-1] ; //Công thức truy hồi
}
return gt[n-1];
}
int main()
{
int n = 7;
cout<<"Giai thua n la: "<<QHD(n);
}
Đây là 2 bài toán rất cơ bản có thể áp dụng quy hoạch động, ngoài ra bạn nên thăm khảo thêm một bài toán kinh điển áp dụng thuật toán quy hoạc động đó là bài toán Tìm xâu con chung lớn nhất, ở trong các bài viết tiếp theo mình sẽ có bài hướng dẫn cụ thể cho bài toán này.
[Xem tất cả bài viết chủ đề C/C++ tại đây]
