C++Góc thuật toán – Quy hoạch động nhập môn

Quy hoạch động là gì ?

• QHĐ là kĩ thuật được dùng khi có một công thức và một (hoặc 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 đã tìm ra trước đó.
• QHĐ có độ phức tạp đa thức nên sẽ chạy nhanh hơn quay lui và duyệt trâu (tuy nhiên, không phải vì QHĐ chạy nhanh hơn mà bạn bỏ qua quay lui và duyệt trâu, bởi sau này ta sẽ được làm quen với việc tạo ra thuật toán QHĐ từ việc Backtracking, điều này rất quan trọng khi bạn không thấy được công thức truy hồi của bài toán).

Khi nào thì dùng Quy hoạch động

• Có một số tính chất của bài toán mà bạn có thể nghĩ đến quy hoạch động. Dưới đây là hai tính chất nổi bật nhất trong số 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

Thường thì một bài toán có đủ cả hai tính chất này, chúng ta có thể dùng quy hoạch động được. Một câu hỏi rất thú vị là không dùng quy hoạch động có được không? Câu trả lời là có, nhưng nếu bạn đi thi code, bạn trượt là cái chắcccc. Để hiểu rõ hơn, chúng ta sẽ đi tìm hiểu các tính chất trong những phần dưới đây.

Bài toán con gối nhau

• Tương tự như thuật toán chia để trị, quy hoạch động cũng chia bài toán lớn thành các bài toán con nhỏ hơn. Quy hoạch động được sử dụng khi các bài toán con này được gọi đi gọi lại.
• Cơ bản là QHĐ sẽ lưu kết quả của các bài toán con này, và khi được gọi, nó sẽ không cần phải tính lại, do đó làm giảm thời gian tính toán.
• Quy hoạch động sẽ không thể áp dụng được (hoặc nói đúng hơn là áp dụng cũng không có tác dụng gì) khi các bài toán con không gối nhau.
• Ví dụ với thuật toán tìm kiếm nhị phân, quy hoạch động cũng không thể tối ưu được gì cả, bởi vì mỗi khi chia nhỏ bài toán lớn thành các bài toán con, mỗi bài toán cũng chỉ cần giải một lần mà không bao giờ được gọi lại.
• 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. Bài toán quá nổi tiếng rồi, chúng ta có thể tính toán số Fibonacci theo đúng công thức như sau:

  function fib (n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
  }

• Nếu tính toán như trên, chúng ta rất nhiều bài toán con sẽ được tính đi tính lại, điển hình là các số $fib(0)$ và $fib(1)$. Và quy hoạch động chính là một trong số những phương pháp có thể giúp chúng ta tối ưu hóa quá trình tính toán này. Mỗi bài toán con (số fib) sẽ được lưu lại trước khi tính những bài toán con lớn hơn. Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần.

  int fib(n) {
  dp[1] = 1;
  for (int i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
  }

Cấu trúc con tối ưu

• Cấu trúc con tối ưu là một tính chất là lời giải của bài toán lớn sẽ là tập hợp lời giải từ các bài toán nhỏ hơn. Ví dụ như bài toán tính số fibonacci, bài toán tính số thứ $i$ được tính bằng tổng của số thứ $i - 1$ và số thứ $i - 2$.

Nguồn bài đăng