Phương pháp lập trình động tương tự như phân chia và chinh phục trong việc chia nhỏ vấn đề thành các vấn đề nhỏ hơn và nhỏ hơn có thể có. Nhưng không giống như phân chia và chinh phục, những vấn đề phụ này không được giải quyết một cách độc lập. Thay vào đó, kết quả của các vấn đề phụ nhỏ hơn này được ghi nhớ và sử dụng cho các vấn đề phụ tương tự hoặc chồng chéo.
Lập trình động được sử dụng khi chúng ta gặp vấn đề, có thể chia thành các vấn đề phụ tương tự, để kết quả của chúng có thể được sử dụng lại. Hầu hết, các thuật toán này được sử dụng để tối ưu hóa. Trước khi giải bài toán phụ trong tay, thuật toán động sẽ cố gắng kiểm tra kết quả của các bài toán con đã giải quyết trước đó. Các giải pháp của các vấn đề phụ được kết hợp để đạt được giải pháp tốt nhất.
Vì vậy, chúng ta có thể nói rằng -
- Vấn đề sẽ có thể được chia thành vấn đề phụ chồng chéo nhỏ hơn.
- Một giải pháp tối ưu có thể đạt được bằng cách sử dụng một giải pháp tối ưu cho các vấn đề phụ nhỏ hơn.
- Các thuật toán động sử dụng Ghi nhớ.
So sánh
Trái ngược với các thuật toán tham lam, nơi giải quyết tối ưu hóa cục bộ, các thuật toán động được thúc đẩy để tối ưu hóa tổng thể vấn đề.
Ngược lại để phân chia và chinh phục các thuật toán, trong đó các giải pháp được kết hợp để đạt được một giải pháp tổng thể, các thuật toán động sử dụng đầu ra của một vấn đề nhỏ hơn và sau đó cố gắng tối ưu hóa một vấn đề phụ lớn hơn. Các thuật toán động sử dụng Ghi nhớ để ghi nhớ đầu ra của các vấn đề phụ đã được giải quyết.
Thí dụ
Các vấn đề máy tính sau đây có thể được giải quyết bằng phương pháp lập trình động -
- Chuỗi số Fibonacci
- Vấn đề về chiếc ba lô
- Tháp Hà Nội
- Tất cả các cặp đường ngắn nhất của Floyd-Warshall
- Con đường ngắn nhất của Dijkstra
- Lập kế hoạch dự án
Lập trình động có thể được sử dụng theo cả cách từ trên xuống và từ dưới lên. Và tất nhiên, hầu hết các lần, đề cập đến đầu ra giải pháp trước đó rẻ hơn so với tính toán lại theo chu kỳ CPU.
Được cập nhật: 14 tháng 4 lúc 7:21:02 | Lượt xem: 356
