Tự học Quy hoạch động hiệu quả từ cơ bản

Theo kinh nghiệm dạy học của cá nhân mình, các chiến lược thiết kế thuật toán là những nội dung nâng cao, là các nội dung khó đối với nhiều giáo viên cũng như học sinh. 

Giả sử giai đoạn lập trình cơ bản, các học sinh có khả năng sử dụng ngôn ngữ lập trình nào đó để biểu diễn các thuật toán cơ bản tốt rồi, học sinh có thể vận dụng tư duy để đưa ra thuật toán cho các bài toán cơ bản rồi. Vậy mà khi chuyển qua nội dung các chuyên đề nâng cao là đa số học sinh bị tụt lại 😆 Và trên thực tế, số lượng này không hề nhỏ. Vậy điều gì làm cho nội dung này là một nội dung quá khó, không thể học được với nhiều học sinh?

Đối với các học sinh giỏi về Quy hoạch động, chắc là các HS đội tuyển Quốc Gia, Quốc Tế thì họ nghĩ thế nào về chủ đề này? Người ta có thấy chủ đề này "dễ" ngay từ đầu không? Và con đường để họ giỏi về nội dung này là gì? Nếu mình theo con đường đó, mình có giỏi được như họ không?

Hihi, câu trả lời tôi nghĩ sẽ rất chung chung, đại khái là đọc sách chuyên đề QHĐ, đại khái là phải làm thật nhiều bài tập, đừng nghĩ bài ấy là Quy hoạch động hay gì... nhưng mà tôi làm theo tôi cũng không khá mấy 😓 Chắc là tôi không năng khiếu bẩm sinh như họ hihi

Tôi còn nghĩ, hay là mình cứ đọc các bài được gắn tag Quy hoạch động, rồi xem lời giải, rồi xem code mẫu chắc là sẽ học được cách nghĩ của Quy hoạch động. Hình như đây cũng không phải là một con đường đúng đắn. Tôi chẳng hiểu, trong lời giải, tại sao người ta lại nghĩ ra công thức QHĐ như thế, chỉ thấy định nghĩa hoặc đưa ra luôn công thức ấy; Tại sao mảng lưu trữ là 1 chiều hay 2, 3 chiều; tại sao??? Tại sao?? Cứ như kiểu họ đọc đề một cái là tự dưng các thứ ấy có sẵn trong đầu vậy 😖

Tôi vẫn nghĩ, chắc là phải có con đường, và nghĩ tại sao người ta lại gọi đó là "mô hình thiết kế thuật toán". Đã là mô hình, chắc phải là chỉ dẫn cụ thể, để có thể theo đó mà nghĩ thì có thể "ra" được một thuật toán QHĐ chứ.

Không dài dòng nữa, mình nói cụ thể các bước thực hành có thể đưa ra một thuật toán Quy hoạch động nhé. Quy hoạch động là một mô hình thiết kế thuật toán, nghĩa là nó gồm các chỉ dẫn cụ thể để nếu theo đó mà nghĩ, có thể đưa ra được một thuật toán tốt bao gồm: Một định nghĩa hàm quy hoạch động, một công thức quy hoạch động, rồi cách thức lưu trữ các kết quả trung gian, và cách triển khai code cho bài toán đó.

Mình thực hành các bước trên một bài toán đơn giản để các bạn rút ra được các bước và ý nghĩa của mỗi bước. Bài toán "Bậc thang - STAIRCASE" được gắn thẻ QHĐ, nội dung đại khái thế này:

Có một cầu thang N bậc, và một người đứng ở chân cầu thang. Mỗi lần nhảy, người này có thể nhảy lên 1 hoặc 2 bậc thang. Hỏi rằng: có bao nhiêu cách khác nhau để người đó tới được bậc N?

Bước 1: Định nghĩa hàm cần tìm. Ở đây ta cần tính số cách khác nhau để người đó tới được bậc N. Vậy ta gọi luôn F(n) là số cách khác nhau để người có thể tới được bậc N. Vậy tại sao chỉ là 1 tham số n mà không phải là hai hay nhiều tham số khác nữa? Bởi vì, theo phân tích bài toán ta thấy, tại một bậc i bất kì, số cách đi tới nó chỉ phụ thuộc vào i mà không, không còn bị ảnh hưởng bởi tham số nào khác.

Bước 2: Tìm công thức quy hoạch động. Công thức QHĐ được xem như là một công thức đệ quy. Ta có thể tính được các trạng thái (giá trị hàm) phía sau nhờ các giá trị đã tính ở các bước trước đó. Ở bài toán này, giả sử người đó đang đứng ở bậc i; như thế, trước đó họ có thể đang đứng ở bậc (i-1) hoặc (i-2) (vì mỗi lần họ chỉ có thể đi 1 hoặc 2 bước); khi đó số cách đến được bậc i sẽ bằng số cách đến bậc (i-1) cộng với số cách đến bậc (i-2); Như vậy: F(i)=F(i-1)+F(i-2)

Bước 3: Tìm cơ sở quy hoạch động. Cơ sở quy hoạch động là giá trị các hàm trong một số trường hợp đặc biệt ban đầu dễ dàng có ngay kết quả. Ở ví dụ trên, có thể nghĩ tới trạng thái đầu tiên là trạng thái F(0) tức là người đang đứng ở bậc 0 và như vậy chỉ có duy nhất 1 cách đến được bậc 0 là ở tại đó F(0)=1; F(1)=F(0)=1 do chỉ có 1 cách là nhảy một bước từ bậc 0 lên bậc 1; F(2)=F(0)+F(1)=2 (để tới được bậc 2, người đó có thể nhảy từ bậc 0 thêm 2 bậc hoặc nhảy từ bậc 1 lên 1 bậc. Thường thì các bạn cứ giảm giá trị tham số về đầu, và xem trạng thái nào có ngay kết quả, tính một vài giá trị ban đầu là được. Ví dụ, với công thức truy hồi như ở trên F(i)=F(i-1)+F(i-2) thì nếu bạn có F(0), F(1) hay F(1), F(2) thì hoàn toàn có thể tính ra mọi F(i) với i từ 3 tới N.

Bước 4: Lập bảng phương án. Bảng phương án ở đây được hiểu là cách thức lưu trữ các giá trị hàm trung gian thế nào cho phù hợp với việc tính lại kết quả sau này. Ở ví dụ trên, khi cần tính F(i) với i=2 tới N; ta có thể lưu các F() vào mảng 1 chiều F[i]; giá trị cơ sở ban đầu được điền trước vào mảng là F[0]=F[1]=1. Sau đó, dùng công thức QHĐ ở trên lần lượt điền đầy bảng phương án.

Bước 5: Cài đặt thuật toán. Ở bước này, các bạn viết chương trình để tính ra được bảng phương án. Sau đó thông báo kết quả cần tìm; Nếu có yêu cầu truy vết (tìm một cách cụ thể) thì sử dụng bảng phương án, kết hợp với công thức quy hoạch động, chúng ta có thể lần tìm lại một phương án đúng nào đó (bài này sẽ được nói kĩ ở một mục khác các bạn nhé. Ở post này chỉ cơ bản thôi)

Luyện tập: Các bạn thử áp dụng các bước tư duy ở trên vào các bài toán cơ bản tương tự sau để khắc ghi các bước suy nghĩ:

• VSTEPS  Đây là cách nghĩ Quy hoạch động bài VSTEPS
• FROG1  Đây là cách nghĩ Quy hoạch động bài FROG1
• FROG2  Đây là cách nghĩ Quy hoạch động bài FROG2

Vận dụng, mở rộng: Tiếp theo, bạn hãy thử dùng chỉ dẫn suy nghĩ ở trên, nghĩ lại các bài toán Quy hoạch động điển hình thường xuất hiện trong các cuốn sách Cấu trúc dữ liệu, giải thuật xem sao nhé. Ở giai đoạn này, bạn có thể theo trình tự sau: Ban đầu bạn thử áp dụng cách nghĩ trên với bài đó; Nếu bạn có vướng mắc, hãy xem qua hướng dẫn giải và dò xét lại, với mỗi bước ta sẽ nên nghĩ thế nào để giải được bài này. Các bạn lần lượt trả lời các câu hỏi sau:

1. Hàm quy hoạch động là gì? Hàm tính giá trị gì? Gồm bao nhiêu tham số? Tại sao lại cần các tham số đó? Có thể bỏ bớt tham số đi được không?
2. Công thức Quy hoạch động là gì? Giả sử đang ở một trạng thái x nào đó, để tới được trạng thái x ta có thể đang ở các trạng thái nào ngay phía trước x?
3. Cơ sở quy hoạch động là gì? Thử nhẩm tính các giá trị hàm ở giá trị nhỏ nhất, lớn nhất có thể có của các tham số; tại sao lại tính được như vậy?
4. Bảng phương án là mảng 1,2 hay 3 chiều? Nếu muốn xây dựng mảng đó theo công thức QHĐ thì nên tính theo thứ tự nào? Tính được bảng phương án rồi thì kết quả cần tìm sẽ được rút ra từ bảng phương án thế nào?
5. Cài đặt thế nào để xây dựng được bảng phương án? Còn có thể cải tiến gì về tốc độ khi xây dựng bảng phương án không? Có cần phải tính và lưu toàn bộ bảng phương án không?

Một số bài tiêu biểu như:

• Dãy con tăng dài nhất (bản dễ) Bài này bạn có thể tạm bỏ qua yêu cầu truy vết, cái này khó, sau này khi thành thạo QHĐ rồi bạn quay lại sau cũng tốt.
• Đường đi có tổng lớn nhất (qbmax) 
• Đường đi trên lưới (nkpath)
• Bài toán đổi tiền (Coin Change) tham khảo phần QHĐ sách CP-handbook
• Bài toán cái túi (Knapsacks) tham khảo phần QHĐ sách CP-handbook
• Bài Edit Distance tham khảo phần QHĐ sách CP-handbook
• Bài toán xếp gạch tham khảo phần QHĐ sách CP-handbook

Rèn kĩ năng: Sau khi quen với cách nghĩ các bài toán có thể giải bằng Quy hoạch động, bạn có thể thử sức với các bài từ đơn giản tới cơ bản trên các trang chấm bài online như: VNOJ, LQDOJ, ATCODER, CSES. Thứ tự đề nghị là bạn hãy làm các bài phần Dynamic Programming theo thứ tự liệt kê ở CSES trước (nếu cần bản dịch Tiếng Việt thì ở đây), rồi ATCODER. Sau đó bạn tùy ý bơi lội giữa biển bài tập gắn thẻ (tag) DP, Quy hoạch động ở các trang chấm bài online khác.

Mong rằng những chia sẻ ở trên có thể giúp bạn bước đầu làm quen với mô hình thiết kế thuật toán Quy hoạch động. Chúc bạn ngày cảng học tốt.