Quy hoạch động (Dynamic Programming)

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ t&igrave;m hiểu về kh&aacute;i niệm của quy hoạch động. Ngo&agrave;i ra, ta sẽ so s&aacute;nh giữa quy hoạch động v&agrave; c&aacute;c thuật to&aacute;n tham lam trong việc giải quyết c&aacute;c b&agrave;i to&aacute;n.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Quy hoạch động l&agrave; một kỹ thuật trong lập tr&igrave;nh gi&uacute;p giải quyết một c&aacute;ch hiệu quả một lớp vấn đề c&oacute; c&aacute;c b&agrave;i to&aacute;n con chồng ch&eacute;o v&agrave; thuộc t&iacute;nh cấu tr&uacute;c con tối ưu. Những b&agrave;i to&aacute;n như vậy li&ecirc;n quan đến việc t&iacute;nh to&aacute;n nhiều lần gi&aacute; trị của c&aacute;c b&agrave;i to&aacute;n con giống nhau để t&igrave;m ra giải ph&aacute;p tối ưu.</p> <ul style="text-align: justify;"> <li>C&aacute;c b&agrave;i to&aacute;n con chồng ch&eacute;o: B&agrave;i to&aacute;n con l&agrave; c&aacute;c b&agrave;i to&aacute;n nhỏ hơn của b&agrave;i to&aacute;n ban đầu. Bất kỳ b&agrave;i to&aacute;n n&agrave;o cũng c&oacute; c&aacute;c b&agrave;i to&aacute;n con tr&ugrave;ng nhau nếu việc t&igrave;m lời giải của n&oacute; li&ecirc;n quan đến việc giải c&ugrave;ng một b&agrave;i to&aacute;n con nhiều lần.</li> <li>Thuộc t&iacute;nh cấu tr&uacute;c con tối ưu: Bất kỳ b&agrave;i to&aacute;n n&agrave;o cũng c&oacute; thuộc t&iacute;nh cấu tr&uacute;c con tối ưu nếu giải ph&aacute;p tối ưu tổng thể của n&oacute; c&oacute; thể được x&acirc;y dựng từ c&aacute;c giải ph&aacute;p tối ưu của c&aacute;c b&agrave;i to&aacute;n con của n&oacute;.</li> </ul> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. C&aacute;c phương ph&aacute;p quy hoạch động</h2> <p style="text-align: justify;">C&oacute; hai c&aacute;ch kh&aacute;c nhau để lưu trữ c&aacute;c gi&aacute; trị m&agrave; ch&uacute;ng ta đ&atilde; t&iacute;nh để ch&uacute;ng c&oacute; thể được sử dụng lại.</p> <h3 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">2.1. Phương ph&aacute;p tiếp cận từ tr&ecirc;n xuống hay phương ph&aacute;p ghi nhớ</h3> <p style="text-align: justify;">Trong c&aacute;ch tiếp cận n&agrave;y, ch&uacute;ng ta sẽ cố gắng giải b&agrave;i to&aacute;n lớn hơn bằng c&aacute;ch lặp đệ quy để t&igrave;m lời giải cho c&aacute;c b&agrave;i to&aacute;n con nhỏ hơn. Bất cứ khi n&agrave;o ch&uacute;ng ta giải quyết một vấn đề con, ch&uacute;ng ta sẽ lưu kết quả của n&oacute; v&agrave;o bộ nhớ để kh&ocirc;ng phải giải quyết n&oacute; lặp đi lặp lại nếu n&oacute; được gọi nhiều lần. Thay v&agrave;o đ&oacute;, ch&uacute;ng ta chỉ cần trả về kết quả đ&atilde; được lưu. Kỹ thuật lưu trữ kết quả của c&aacute;c b&agrave;i to&aacute;n con đ&atilde; được giải quyết n&agrave;y được gọi l&agrave; kỹ thuật ghi nhớ.</p> <h3 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">2.2. Phương ph&aacute;p từ dưới l&ecirc;n hay phương ph&aacute;p lập bảng</h3> <p style="text-align: justify;">Lập bảng ngược lại với c&aacute;ch tiếp cận từ tr&ecirc;n xuống v&agrave; kh&ocirc;ng sử dụng đệ quy. Trong c&aacute;ch tiếp cận n&agrave;y, ch&uacute;ng ta giải quyết vấn đề &ldquo;từ dưới l&ecirc;n&rdquo; (tức l&agrave; bằng c&aacute;ch giải quyết tất cả c&aacute;c vấn đề con li&ecirc;n quan trước). Điều n&agrave;y thường được thực hiện bằng c&aacute;ch điền v&agrave;o một bảng với N chiều. Dựa tr&ecirc;n kết quả trong bảng, giải ph&aacute;p cho vấn đề ban đầu sẽ được t&iacute;nh to&aacute;n.</p> <p style="text-align: justify;">Lập bảng tr&aacute;i ngược với kỹ thuật ghi nhớ, v&igrave; trong kỹ thuật ghi nhớ, ch&uacute;ng ta sẽ giải quyết vấn đề v&agrave; duy tr&igrave; một bản đồ c&aacute;c vấn đề con đ&atilde; được giải quyết. N&oacute;i c&aacute;ch kh&aacute;c, trong kỹ thuật ghi nhớ, ch&uacute;ng ta thực hiện từ tr&ecirc;n xuống theo nghĩa l&agrave; ch&uacute;ng ta giải quyết vấn đề tr&ecirc;n c&ugrave;ng trước (thường lặp lại xuống để giải quyết c&aacute;c vấn đề phụ).</p> <h2 id="ftoc-heading-5" class="ftwp-heading" style="text-align: justify;">3. V&iacute; dụ về thuật to&aacute;n</h2> <p style="text-align: justify;">B&agrave;i to&aacute;n tạo chuỗi fibonacci.</p> <p style="text-align: justify;">Nếu d&atilde;y l&agrave; F(1) F(2) F(3)&hellip;&hellip;..F(50), n&oacute; sẽ tu&acirc;n theo quy tắc F(n) = F(n-1) + F(n-2 )</p> <pre class="language-cpp"><code>F(50) = F(49) + F(48) F(49) = F(48) + F(47) F(48) = F(47) + F(46) ...</code></pre> <p style="text-align: justify;">C&oacute; thể thấy rằng c&aacute;c b&agrave;i to&aacute;n con bị chồng ch&eacute;o lẫn nhau. Ch&uacute;ng ta cần t&iacute;nh F(48) để t&iacute;nh cả F(50) v&agrave; F(49). Đ&acirc;y ch&iacute;nh x&aacute;c l&agrave; loại thuật to&aacute;n m&agrave; quy hoạch động sẽ đạt hiệu quả.</p> <h2 id="ftoc-heading-6" class="ftwp-heading" style="text-align: justify;">4. C&aacute;ch thức hoạt động của thuật to&aacute;n quy hoạch động</h2> <p style="text-align: justify;">Quy hoạch động hoạt động bằng c&aacute;ch lưu trữ kết quả của c&aacute;c b&agrave;i to&aacute;n con để khi cần đến c&aacute;c giải ph&aacute;p của ch&uacute;ng, ch&uacute;ng c&oacute; thể được sử dụng v&agrave; ch&uacute;ng ta kh&ocirc;ng cần phải t&iacute;nh to&aacute;n lại. Kỹ thuật lưu trữ gi&aacute; trị của c&aacute;c b&agrave;i to&aacute;n con n&agrave;y được gọi l&agrave; ghi nhớ. Bằng c&aacute;ch lưu c&aacute;c gi&aacute; trị trong mảng, ch&uacute;ng ta c&oacute; thể tiết kiệm thời gian t&iacute;nh to&aacute;n c&aacute;c b&agrave;i to&aacute;n con m&agrave; ch&uacute;ng ta đ&atilde; gặp phải.</p> <pre class="language-cpp"><code>m = map(0 &rarr; 0, 1 &rarr; 1) H&agrave;m fib(n) Nếu kh&oacute;a n kh&ocirc;ng nằm trong m m[n] = fib(n &minus; 1) + fib(n &minus; 2) Trả về m[n]</code></pre> <p style="text-align: justify;">Quy hoạch động bằng c&aacute;ch ghi nhớ l&agrave; một c&aacute;ch tiếp cận từ tr&ecirc;n xuống. Bằng c&aacute;ch đảo ngược hướng m&agrave; thuật to&aacute;n hoạt động, tức l&agrave; bắt đầu từ trường hợp cơ sở v&agrave; hướng tới giải ph&aacute;p cần t&igrave;m, ch&uacute;ng ta cũng c&oacute; thể triển khai quy hoạch động theo c&aacute;ch từ dưới l&ecirc;n.</p> <pre class="language-cpp"><code>H&agrave;m fib(n) Nếu n = 0 Trả về 0 Nếu kh&ocirc;ng, Khởi tạo biến prevFib = 0, currFib = 1 Lặp lại n &ndash; 1 lần Khởi tạo newFib = prevFib + currFib prevFib = currFib currFib = newFib Trả về currentFib</code></pre> <h2 id="ftoc-heading-7" class="ftwp-heading" style="text-align: justify;">5. So s&aacute;nh thuật to&aacute;n đệ quy v&agrave; quy hoạch động</h2> <ul style="text-align: justify;"> <li>Quy hoạch động hầu hết được &aacute;p dụng cho c&aacute;c thuật to&aacute;n đệ quy. Đ&acirc;y kh&ocirc;ng phải l&agrave; sự ngẫu nhi&ecirc;n, hầu hết c&aacute;c b&agrave;i to&aacute;n tối ưu h&oacute;a đều y&ecirc;u cầu đệ quy v&agrave; quy hoạch động được sử dụng để tối ưu h&oacute;a.</li> <li>Nhưng kh&ocirc;ng phải b&agrave;i to&aacute;n n&agrave;o sử dụng đệ quy cũng c&oacute; thể sử dụng quy hoạch động. Trừ khi c&oacute; sự xuất hiện của c&aacute;c b&agrave;i to&aacute;n con chồng ch&eacute;o như trong b&agrave;i to&aacute;n d&atilde;y fibonacci, một ph&eacute;p đệ quy chỉ c&oacute; thể đạt được giải ph&aacute;p bằng c&aacute;ch sử dụng thuật to&aacute;n chia để trị. Đ&oacute; l&agrave; l&yacute; do tại sao một thuật to&aacute;n đệ quy như Merge Sort kh&ocirc;ng thể sử dụng quy hoạch động, bởi v&igrave; c&aacute;c b&agrave;i to&aacute;n con kh&ocirc;ng chồng ch&eacute;o nhau.</li> </ul> <h2 id="ftoc-heading-8" class="ftwp-heading" style="text-align: justify;">6. So s&aacute;nh thuật to&aacute;n tham lam so với quy hoạch động</h2> <ul style="text-align: justify;"> <li>Thuật to&aacute;n tham lam tương tự như quy hoạch động theo nghĩa cả hai đều l&agrave; c&ocirc;ng cụ để tối ưu h&oacute;a.</li> <li>Tuy nhi&ecirc;n, c&aacute;c thuật to&aacute;n tham lam t&igrave;m kiếm c&aacute;c giải ph&aacute;p tối ưu cục bộ hay n&oacute;i c&aacute;ch kh&aacute;c, một sự lựa chọn tham lam, với hy vọng t&igrave;m ra giải ph&aacute;p tối ưu to&agrave;n cục. Do đ&oacute;, c&aacute;c thuật to&aacute;n tham lam c&oacute; thể đưa ra một dự đo&aacute;n c&oacute; vẻ tối ưu v&agrave;o thời điểm đ&oacute; nhưng lại trở n&ecirc;n tốn k&eacute;m v&agrave; kh&ocirc;ng đảm bảo mức tối ưu to&agrave;n cục.</li> <li>Mặt kh&aacute;c, quy hoạch động t&igrave;m ra giải ph&aacute;p tối ưu cho c&aacute;c b&agrave;i to&aacute;n con v&agrave; sau đ&oacute; đưa ra lựa chọn s&aacute;ng suốt để kết hợp c&aacute;c kết quả của c&aacute;c b&agrave;i to&aacute;n con đ&oacute; để t&igrave;m ra giải ph&aacute;p tối ưu nhất.</li> </ul> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về thuật to&aacute;n quy hoạch động. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>