Quy hoạch động là gì? Các nội dung liên quan để hiểu thêm về thuật ngữ này? Đây là vấn đề khó hiểu cho mọi người. Tuy nhiên, thông qua tìm hiểu và tham khảo một số tài liệu, chúng tôi tóm tắt thông tin dưới đây. Hãy đọc bài viết này để hiểu thêm thuật ngữ trên nhé!
Quy hoạch động là gì?
Là phương pháp rất hiệu quả để sử dụng giải nhiều bài toán tin học, nhất là đối với những bài toán tối ưu. Một số bài toán bắt buộc phải sử dụng phương pháp này lại có hiệu quả hơn so với các phương pháp khác.
Nhờ có phương pháp này mà số lượng bài toán tin học được giải quyết đáng kể. Vì vậy, trong các kỳ thi giỏi môn tin học, phương pháp này được sử dụng khá phổ biến.
Nó được hiểu là một kỹ thuật trong lập trình nhằm giúp giải quyết sao cho hiệu quả đối với một lớp vấn đề. Bao gồm có các bài toán con chồng chéo và thuộc tính cấu trúc con tối ưu. Các bài toán trên liên quan đến việc tính toán nhiều lần giá trị của các bài toán con giống nhau để tìm ra giải pháp tối ưu. Cụ thể:
- Các bài toán con chồng chéo: Đây là các bài toán nhỏ hơn của bài toán ban đầu. Bất kể bài toán nào cũng có các bài toán con trùng nhau. Cho nên, việc tìm lời giải của nó liên quan đến giải cùng một bài toán con nhiều lần.
- Thuộc tính cấu trúc con tối ưu: Bài toán nào cũng có thuộc tính cấu trúc con tối ưu nếu giải pháp tối ưu tổng thể của nó. Đồng thời, có thể được xây dựng từ các giải pháp tối ưu của các bài toán con của nó.
Đặc điểm của quy hoạch động
Để hiểu rõ hơn về khái niệm trên, chúng ta tìm hiểu các đặc điểm của nó như thế nào?
- Là phương pháp bắt đầu giải quyết từ những bài toán nhỏ hay gọi là bài toán cơ sở. Thông qua đó từng bước giải quyết những bài toán lớn cho đến khi giải được bài toán ban đầu.
- Phương pháp cần đưa ra nhiều phương án khác nhau.
- Phương pháp này tránh tính toán lại những bài toán con đã xét.
- Đây là phương pháp được tiếp cận từ dưới lên.
Phương pháp quy hoạch động là gì?
Liên quan đến vấn đề này, mọi người sử dụng hai phương pháp phổ biến sau:
Phương pháp tiếp cận từ trên xuống hoặc phương pháp ghi nhớ
Với cách tiếp cận này, bạn sẽ cố gắng giải toán lớn hơn, được thực hiện bằng cách lặp đệ quy và tìm lời giải cho các bài toán con nhỏ hơn.
Bạn nên nhớ, bất cứ khi nào bạn muốn giải quyết vấn đề con, bạn sẽ lưu kết quả của nó vào trong bộ nhớ. Hạn chế tình trạng giải quyết nó lặp đi lặp lại nhiều lần. Nhờ lưu kết quả vào bộ nhớ, bạn chỉ cần trả lời về kết quả đã lưu. Vì vậy, kỹ thuật lưu trữ kết quả các bài toán con chính là kỹ thuật ghi nhớ.
Phương pháp từ dưới lên hoặc phương pháp lập bảng
Phương pháp từ dưới lên không sử dụng đệ quy. Mọi vấn đề được giải quyết “từ dưới lên, nghĩa là cách giải quyết vấn đề con được thực hiện trước tiên. Chúng được thực hiện bằng cách điền vào một bảng với N chiều. Sau đó, dựa trên kết quả trong bảng rồi giải pháp cho các vấn đề ban đầu sẽ được tính toán.
Ví dụ điển hình liên quan đến quy hoạch động là gì – Bài toán kinh điển với đồng xu
Với những kiến thức cung cấp trên có thể bạn chưa thể hiểu hết bản chất của thuật ngữ này. Hãy xem các ví dụ cụ thể sau đây:
Giả sử chúng ta có n đồng xu nặng lần lượt là w1, w2, w3, …,wn. Hãy tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị s và số lượng đồng xu là không giới hạn. Trong đó, n =3, S = 11, W = [1, 3, 5].
- Bạn bắt đầu giải bài toán con 0 ta có dp(0) = 0.
- Trường hợp bài toán con 1: Ta có 1 đồng xu (nặng 1) có thể thêm vào từ 0 đồng xu nào cả. Như vậy, dp(1) = dp(0) + 1 = 1.
- Tương tự với bài toán con 2: Ta cũng chỉ có 1 đồng xu (nặng 1) có thể thêm vào từ 1 đồng xu. Phép tính là: dp(2) = dp(1) + 1 = 2.
- Đối với bài toán con 3: Chúng ta có thể thêm 1 đồng xu 3 vào 0 đồng xu hoặc thêm 1 đồng xu 1 vào 2 đồng xu. Điều này cho thấy, cách đầu tiên cho kết quả nhỏ hơn. Ta có: dp(3) = min(dp(2) + 1, dp(0) + 1) = min(3, 1) = 1
- Tương tự với các bài toán con khác, cho đến bài toán s chính là đáp án chúng ta cần tìm.
Khi ta cài đặt trên máy tính, cách tính bằng phương pháp này thường lưu kết quả vào một bảng. Với minh họa trên, mảng dp[0..S] trên sẽ lưu kết quả cho từng bài toán con. Hay nói cách khác dp[P] = k nghĩa là cần ít nhất k đồng xu để có khối lượng là p. Tổng thể mảng này sẽ được tính bằng vòng lặp.
Hy vọng với các nội dung trên sẽ giúp bạn hiểu thêm về quy hoạch động là gì? Qua đó giúp bạn áp dụng một cách linh động hơn trong học tập cũng như thực tế.