Quy hoạch động

Quy hoạch động (QHĐ; tiếng Anh: dynamic programming, DP) — là phương pháp giải các bài toán tối ưu phức tạp, dựa trên việc phân chia bài toán gốc thành một chuỗi các bài toán con đơn giản hơn. Phương pháp được áp dụng cho các quá trình ra quyết định nhiều bước, trong đó nghiệm tối ưu của toàn bộ bài toán có thể được xây dựng từ các nghiệm tối ưu của các bài toán con.

Thuật ngữ này được giới thiệu bởi nhà toán học người Mỹ Richard Bellman vào những năm 1950. Trong ngữ cảnh này, từ "programming" (lập trình) được dùng với nghĩa "lập kế hoạch" hoặc "xây dựng kế hoạch hành động tối ưu", chứ không phải viết mã máy tính.

Các tính chất và định lý then chốt

Khả năng áp dụng quy hoạch động cho một bài toán được xác định bởi sự tồn tại của hai tính chất cơ bản.

Nguyên lý tối ưu Bellman

Khái niệm trung tâm của phương pháp là nguyên lý tối ưu Bellman (tiếng Anh: Bellman's principle of optimality). Nguyên lý phát biểu rằng: bất kể trạng thái ban đầu và quyết định ban đầu là gì, các quyết định tiếp theo phải tạo thành một chiến lược tối ưu đối với trạng thái thu được từ quyết định đầu tiên.

Nói cách khác, bất kỳ đoạn nào của quỹ đạo tối ưu tự nó cũng là tối ưu. Tính chất này cho phép phân chia bài toán tổng thể thành một chuỗi các bài toán con đơn giản hơn và giải chúng một cách đệ quy.

Bài toán con chồng lấp

Một bài toán có tính chất bài toán con chồng lấp (tiếng Anh: overlapping subproblems) nếu khi giải đệ quy, các bài toán con giống nhau xuất hiện nhiều lần. QHĐ cho phép tránh các phép tính lặp lại bằng cách lưu trữ các nghiệm của các bài toán con đã gặp (kỹ thuật này được gọi là memoization hoặc tabulation), qua đó tăng đáng kể hiệu quả so với duyệt đệ quy ngây thơ.

Phương trình Bellman

Từ nguyên lý tối ưu suy ra quan hệ truy hồi cơ bản của phương pháp — phương trình Bellman. Nó liên kết "giá trị" (phần thưởng hoặc chi phí tối ưu) của trạng thái hiện tại với các giá trị của các trạng thái tiếp theo. Dạng tổng quát cho quá trình nhiều bước tất định với hàm mục tiêu cộng tính như sau:

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

trong đó:

• $k$ — số thứ tự bước (từ $m$ đến 1);
• $x$ — trạng thái của hệ thống tại bước $k-1$;
• $y$ — quyết định điều khiển được đưa ra tại bước $k$;
• ${\phi }_k(x,y)$ — phần thưởng (hoặc chi phí) tại bước thứ k;
• $f_k(x,y)$ — hàm xác định trạng thái mới của hệ thống;
• $V_k(s)$ — giá trị tối ưu của hàm mục tiêu cho bài toán con bắt đầu từ bước $k$ tại trạng thái $s$.

Phương trình được giải tuần tự, thông thường là "từ cuối", tiến từ bước cuối cùng về bước đầu tiên.

Các ví dụ áp dụng

• Bài toán đường đi ngắn nhất trong đồ thị: Bài toán này có tính chất cấu trúc con tối ưu, vì bất kỳ đoạn nào của đường đi ngắn nhất cũng tự nó là ngắn nhất. Các thuật toán Bellman-Ford và Floyd-Warshall là những ví dụ kinh điển về áp dụng QHĐ để giải bài toán này.
• Bài toán cái túi (knapsack): Bài toán về việc lấp đầy tối ưu một chiếc túi có dung lượng giới hạn bằng các vật phẩm có giá trị và trọng lượng khác nhau. QHĐ cho phép giải bài toán này bằng cách xét các vật phẩm lần lượt và tính toán tại mỗi bước giá trị tối đa cho tất cả các giá trị có thể của dung lượng còn lại.
• Bài toán phân bổ tài nguyên: Phân bổ tài nguyên giới hạn (ví dụ: vốn đầu tư) giữa nhiều dự án nhằm tối đa hóa hiệu quả tổng thể.

Hạn chế

Hạn chế chính của phương pháp là 'lời nguyền chiều (tiếng Anh: curse of dimensionality) — thuật ngữ do Bellman đặt ra để chỉ sự tăng trưởng theo hàm mũ của số lượng trạng thái và do đó là độ phức tạp tính toán khi số biến mô tả trạng thái của hệ thống tăng lên. Điều này hạn chế việc áp dụng thực tế của QHĐ chính xác cho các bài toán có kích thước rất lớn.

Các khái niệm liên quan

• Nghiên cứu vận trù học
• Lý thuyết điều khiển tối ưu
• Quá trình quyết định Markov (tổng quát hóa ngẫu nhiên)
• Phương trình Hamilton – Jacobi – Bellman (tương tự cho thời gian liên tục)

Ghi chú

</references>