Quy hoạch động là một trong những thuật toán được sử dụng phổ biến trong các cuộc thi lập trình. Hầu hết các bài thi trong cuộc thi lập trình sẽ áp dụng thuật toán này để giải quyết nhanh chóng. Nếu bạn chuẩn bị tham gia vào cuộc thi này, hãy không bỏ lỡ bài viết này. Hãy cùng tìm hiểu rõ hơn về thuật toán này!
Khái niệm về quy hoạch động
Quy hoạch động là một kỹ thuật trong lập trình giúp giải quyết hiệu quả việc chia bài toán lớn thành các bài toán con khác nhau và tìm ra cấu trúc con tối ưu. Các bài toán thường có nhiều lời giải đúng và mỗi lời giải có một giá trị đánh giá khác nhau. Do đó, ta cần tính toán nhiều lần và sử dụng lời giải của các bài toán con để tìm ra đáp án cho bài toán ban đầu.
Bạn đang xem: Quy hoạch động là gì? Tìm hiểu chi tiết về thuật toán quy hoạch động
Khi bạn muốn giải quyết một bài toán một cách nhanh nhất, thuật toán quy hoạch động là một phương pháp giúp tối ưu thời gian. Quy hoạch động bao gồm bốn bước sau:
- Bước 1: Đặc trưng hóa cấu trúc của lời giải tối ưu.
- Bước 2: Định nghĩa giá trị của lời giải tối ưu bằng cách đệ quy.
- Bước 3: Tính giá trị của lời giải tối ưu bằng cách lặp từ dưới lên hoặc từ trên xuống.
- Bước 4: Xây dựng lời giải tối ưu từ các thông tin đã được tính toán.
Thay vì sử dụng đệ quy, thuật toán sẽ tính toán lời giải của các bài toán con trước đó và lưu vào một mảng. Sau đó, ta sẽ sử dụng lời giải của các bài toán con trong mảng đã tính trước đó để giải bài toán lớn thông qua công thức truy hồi. Công thức truy hồi là công thức mô tả mối quan hệ giữa các bước trong một bài toán và kết quả của bước sau dựa trên kết quả của các bước trước.
Thuật toán này có ưu điểm lớn là tiết kiệm thời gian tính toán, tuy nhiên cũng có một số nhược điểm. Đầu tiên, việc tìm ra công thức truy hồi hoặc phân rã bài toán lớn đòi hỏi sự suy nghĩ và phân tích cẩn thận. Điều này giúp tránh sai sót và rủi ro phải tính lại từ đầu. Thứ hai, khó xử lý dữ liệu khi bảng lưu trữ yêu cầu mảng hai hoặc ba chiều. Cuối cùng, không phải bài toán tối ưu nào cũng có thể áp dụng quy hoạch động để giải quyết.
Ngoài ra, một bài toán tối ưu cũng có những đặc điểm cần lưu ý sau:
- Cần phải chia bài toán lớn thành nhiều bài toán con nhỏ hơn và kết hợp lời giải của các bài toán con để giải quyết bài toán lớn.
- Bản chất của thuật toán là giải quyết tất cả các bài toán con. Quy hoạch động không thể thực hiện được nếu không có đủ không gian lưu trữ để phối hợp các bài toán con.
Khi nào nên sử dụng thuật toán quy hoạch động?
Điểm quan trọng khi áp dụng thuật toán này là cần tìm ra công thức truy hồi cho từng trường hợp của bài toán. Một số bài toán dễ dàng có nhiều cách giải và có thể áp dụng quy hoạch động nhưng chưa chắc là tối ưu. Mỗi bài toán có một đặc điểm khó khác nhau, không có một công thức chung dành cho tất cả các bài toán.
Xem thêm : Tên tiếng Anh của Công an nhân dân các Tỉnh, thành phố
Vậy khi nào chúng ta nên áp dụng thuật toán quy hoạch động? Thường thì có hai tính chất sau đây đối với bài toán mà ta có thể áp dụng quy hoạch động:
Bài toán con gối nhau
Bài toán con gối nhau là bài toán nhỏ hơn được chia ra từ bài toán ban đầu. Bằng cách lặp lại nhiều lần, thuật toán sẽ lưu trữ kết quả đã tính toán để không cần tính lại, giúp tiết kiệm rất nhiều thời gian. Việc giải một bài toán con nhiều lần khiến ta không tránh khỏi việc trùng lặp các lời giải của bài toán con.
Khi các bài toán con không gối nhau, áp dụng thuật toán quy hoạch động sẽ không mang lại hiệu quả. Thuật toán tìm kiếm nhị phân không thể được tối ưu với quy hoạch động. Điều này xảy ra vì khi chia nhỏ bài toán lớn thành các bài toán con và mỗi bài toán chỉ cần giải một lần mà không được gọi lại nữa.
Ví dụ điển hình cho bài toán con gối nhau là bài toán tính dãy Fibonacci. Bằng cách cộng số Fibonacci thứ n-1 và n-2, ta có thể tính được số Fibonacci thứ n. Bài toán con của số Fibonacci thứ n chính là bài toán tính Fibonacci n-1 và n-2. Công thức tính số Fibonacci được mô tả như sau:
def fib(n):
if n <= 1:
return n
return fib(n – 1) + fib(n – 2)
Xem thêm : Infinitive là gì? Cách sử dụng và nhận biết to-infinitive và bare infinitive
Quy hoạch động là một trong những giải pháp hiệu quả nhất để tối ưu quá trình tính toán này. Trước khi tính toán các bài toán lớn, ta sẽ lưu trữ mỗi bài toán con. Nhờ đó, quá trình tính toán giảm đáng kể, mỗi bài toán con chỉ cần tính một lần. Điều này giúp thuật toán này được sử dụng rộng rãi trong các cuộc thi lập trình, giúp thí sinh tiết kiệm thời gian tính toán.
Cấu trúc con tối ưu
Bài toán có cấu trúc con tối ưu là bài toán có tập hợp các lời giải tối ưu từ các bài toán con, giúp tìm ra lời giải tối ưu cho bài toán lớn. Bài toán có cấu trúc con tối ưu có thể dễ dàng tính toán hoặc có thể không cần tính toán lại. Các bài toán con tối ưu có thể sử dụng công thức truy hồi trong thuật toán để tìm ra lời giải cuối cùng cho bài toán.
Cấu trúc con tối ưu với ba bước quy trình mà bạn nên biết để giải quyết một bài toán nhanh chóng nhất:
- Bước 1: Chia bài toán lớn thành các bài toán con nhỏ hơn.
- Bước 2: Sử dụng phương pháp đệ quy để giải các bài toán con tối ưu.
- Bước 3: Sử dụng kết quả tối ưu đã tính toán để dễ dàng tìm ra lời giải tối ưu cho bài toán lớn.
Bài toán có cấu trúc con tối ưu rất quan trọng, vì nó cho phép ta dựa vào lời giải của các bài toán con để tìm lời giải cho bài toán lớn. Ta không thể áp dụng thuật toán quy hoạch động nếu bài toán không có tính chất này.
Các phương pháp trong quy hoạch động
Trong quy hoạch động, ta có thể sử dụng một trong hai phương pháp sau để dễ dàng lưu trữ kết quả đã tính:
Phương pháp từ trên xuống (phương pháp memoization)
Với phương pháp này, ta bắt đầu giải bài toán từ trên xuống. Bằng cách lặp đệ quy để giải bài toán lớn hơn, ta có thể tìm ra lời giải cho các bài toán con. Các bài toán con này sẽ được giải và kết quả sẽ được lưu vào bộ nhớ. Lưu kết quả này sẽ giúp ta giải quyết các vấn đề con mà không tốn quá nhiều thời gian.
Phương pháp từ dưới lên (phương pháp tabulation)
Phương pháp tabulation hoàn toàn ngược lại so với phương pháp memoization. Phương pháp này không sử dụng đệ quy và giải bài toán con từ dưới lên. Ta giải trực tiếp tất cả các bài toán con và điền vào một bảng có hàng và cột. Sau đó, ta sử dụng kết quả trong bảng để tìm dần lời giải cho bài toán ban đầu. Phương pháp này hiệu quả hơn và được sử dụng nhiều hơn phương pháp memoization vì nó không tốn bộ nhớ và số lần gọi hàm.
Từ bài viết trên, chúng ta đã khám phá được khái niệm và hiểu được bản chất của thuật toán quy hoạch động. Nếu bạn muốn tìm hiểu thêm về kiến thức lập trình hoặc muốn trở thành một lập trình viên trong tương lai, hãy liên hệ với FPT Aptech nhé!
