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

Cấu trúc con tối ưu (tiếng Anh: Optimal substructure) là một khái niệm quan trọng trong quy hoạch động. Nó đề cập đến tính chất của một bài toán trong đó một giải pháp tối ưu cho bài toán lớn có thể được xây dựng từ các giải pháp tối ưu của các bài toán con nhỏ hơn. Thuộc tính này được sử dụng để xác định tính hữu ích của các thuật toán tìm tối ưu tổng thể từ các tối ưu cục bộ cho một bài toán.^[1]

Trong một bài toán có optimal substructure, giải pháp tối ưu của bài toán lớn có thể được phân tích thành các bước nhỏ hơn, và mỗi bước nhỏ đều là một bài toán con tối ưu trong đó giải pháp tối ưu của nó có thể được xây dựng từ các bài toán con con nhỏ hơn hơn nữa. Quá trình này tiếp tục cho đến khi đạt được các bài toán con cỡ nhỏ nhất mà có thể được giải trực tiếp.

Sự tồn tại của optimal substructure làm cho quy hoạch động trở thành một kỹ thuật hiệu quả để giải quyết các bài toán tổng quát và phức tạp bằng cách tận dụng tính chất này. Bằng cách lưu trữ và sử dụng các kết quả của các bài toán con đã được giải quyết trước đó, chúng ta có thể xây dựng giải pháp tối ưu cho bài toán lớn một cách hiệu quả.

Bài toán với cấu trúc con tối ưu

Bài toán chuỗi con chung dài nhất
Bất kỳ bài toán toán nào có thể giải quyết bằng quy hoạch động

Xem thêm

Tham khảo

^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (ấn bản thứ 3). MIT Press. ISBN 978-0-262-03384-8.

[cormen-1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (ấn bản thứ 3). MIT Press. ISBN 978-0-262-03384-8.

[1]