Dynamic Programming-Quy hoạch động trong lập trình

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

Dynamic programming là một phương pháp được sử dụng trong lĩnh vực tối ưu toán học và lập trình máy tính. Được phát triển bởi nhà toán học ứng dụng nổi tiếng người Mỹ Richard E. Bellman trong những năm 1950

Dynamic Programming có ý tưởng tương tự phương pháp “chia để trị” chia bài toán ban đầu phức tạp thành các bài toán con đơn giản hơn. Bước này sẽ lặp lại cho đến khi bài toán con có thể giải được một cách đơn giản. Tổng hợp kết quả của bài toán con để suy ra kết quả của bài toán ở mức trên. Từ đây ta có thể thấy phương pháp quy hoạch động có thể cái đặt được bằng đệ quy (recursive)

Các đặc điểm của một bài toán có thể giải bằng Dynamic Programming

Đầu tiên tôi xin nhắc lại nguyên lý tối ưu Bellman như sau:

Một chính sách tối ưu bào gồm một dãy các quyết định có đặc tính là dù trạng thái và quyết định ban đầu có như thế nào đi nữa thì các quyết định còn lại luôn là một dãy các quyết định tối ưu (tạo ra chính sách tối ưu) với kết quả đạt được liên quan đến kết quả của quyết định ban đầu.

Bài toán P có thể giải được bằng giải thuật quy hoạch động nếu thỏa mãn các đặc điểm sau:

• Bài toán P thỏa mãn nguyên lý tối ưu Bellman hay bài toán P có cấu trúc con tối ưu nghĩa là có thể dùng lời giãi tối ưu của các bài toán con ở mức thấp nhất tìm dần lời giải tối ưu cho các bài toán con ở mức cao hơn và cuối cùng là lời giải tối ưu cho bài toán toàn thể
• Bài toán P có các bài toán con gối lên nhau hay nói cách khác không gian bài toán con hẹp và không tạo thành cây. Nếu hai bài toán con được sinh ra cùng mức (được sinh ra từ một bài toán) thì lời giải hai bài toán con này đòi hỏi lời giải của cùng một số bài toán con ở mức dưới

Hệ thức truy hồi

Như đã phát biểu ở trên trong lập trình động khi giải bài toán con ở mức trên ta cần tổng hợp kết quả của bài toán con ở mức dưới. Vậy chúng ta cần phải xây dựng một hệ thức để biểu thị mối quan hệ này. Hơn nữa trong trường hợp bài toán đòi hỏi kết quả là tối ưu ta cần tìm hệ thức để đạt được điều này. Hệ thức như vậy được gọi là hệ thức truy hồi. Để rõ hơn điều này chúng ta xem ví dụ về một bài toán nỗi tiếng trên thế giới sau:

Bài toán Tháp Hà nội: có 3 cọc A, B và C. Cọc A chứa N chiếc đĩa theo nguyên tắc đĩa to ở dưới và đĩa nhỏ ở trên, cọc B và C rỗng. Cần chuyển N chiếc đĩa này từ A sang C có thể sử dụng B làm trung gian, mỗi lần chuyển chỉ được một đĩa và đĩa trên các cọc đều phải tuân theo nguyên tắc đĩa nhỏ ở trên, đĩa to ở dưới.

Để hoàn thành trò chơi này chúng ta cần ít nhất bao nhiêu lần chuyễn đĩa. Gọi  là số lần cần thiết để chuyển N đĩa từ cột A sang cột C. Để thực hiện điều này đầu tiên ta chuyển N-1 đĩa từ cột A sang cột B sau đó chuyển đĩa to nhất từ cột A sang cột C sau đó ta chuyển N-1 đĩa còn lại từ B sang C ta có công thức truy hồi như sau:

 dựa vào công thức tính tổng n số hạng đầu tiên của cấp số nhân có công bội là 2 chúng ta dễ dàng chứng minh được 

Hướng tiếp cận giải một bài toán bằng Dynamic Programming

Có hai hướng tiếp cận để giải quyết một bài toán bằng quy hoặc động:

• Top-Down
• Bottom-Up

Theo hướng tiếp cận Top-Down chúng ta sẽ bắt đầu bằng bài toán lớn nhất hay là bài toán ở mức trên cùng sau đó dùng phương pháp đệ quy để gọi lời giải cho các bài toán con ở mức thấp hơn tiếp theo. Qúa trình tiếp tục cho đến khi gặp bài toán nhỏ nhất. Đệ quy sẽ tự động tổ hợp kết quả của các bài toán con để được kết quả bài toán ban đầu. Cách này đòi hỏi tốn nhiều tài nguyên để ghi nhớ tất cả kết quả của các bài toán con.

Hướng tiếp cận Bottom-Up đầu tiên chúng ta giải các bài toán con ở mức thấp nhất sau đó dùng các kết quả này để tính bài toán ở mức trên. Quá trình tiếp tục cho đến khi chúng ta tìm được kết quả bài toán mức cao nhất. Hướng này không đòi hỏi phải lưu lại kết quả của tất cả các bài toán con

Các bước giải một bài toán tối ưu bằng quy hoạch động

• Bước 1: Xem xét bài toán có thể chia thành các bài toán con thỏa mãn nguyên lý Bellman không hoặc thỏa mãn các đặc điểm đã nêu ở trên
• Bước 2: Xác định hệ thưc truy hồi cho bài toán tối ưu
• Bước 3: Tìm nghiệm tối ưu của bài toán bằng hai phương pháp Top-Down hoặc Bottom-Up

Trên đây là một số vấn đề cơ bản về Dynamic Programming: các khái niệm liên quan cũng như các bước giải một bài toán bằng quy hoạch động. Trong bài tiếp theo mình sẽ trình bày một số ví dụ cụ thể để thấy rõ hơn việc áp dụng Dynamic Programming vào giải một số bài toán trong thực tế. Chúc các bạn một ngày làm việc vui vẻ.