lehang_gb1
11-12-2011, 22:52
Quy hoạch động là kĩ thuật đi từ dưới lên (bottom - up). Chúng ta xuất phát từ những trường hợp riêng đơn giản nhất của bài toán, thường thấy ngay nghiệm của chúng. Sau đó kết hợp nghiệm của chúng, ta được nghiệm của bài toán con lớn hơn. Rồi lại kết hợp nghiệm của các bài toán con này để nhận được nghiệm của bài toán lớn hơn nữa, và cứ thế cho đến khi nhận được nghiệm của bài toán đã cho.
Tư tưởng cơ bản của phương pháp quy hoạch động là trong quá trình đi từ dưới lên", ta sử dụng một bảng để lưu giữ lời giải của các bài toán con đã giải. Khi giải một bài toán con cần đến nghiệm của bài toán con cỡ nhỏ hơn, ta chỉ cần tìm ở trong bảng, không cần giải lại. Chính vì thế mà các thuật toán được thiết kế bằng quy hoạch động sẽ rất có hiệu quả.
Tư tưởng cơ bản của phương pháp quy hoạch động là trong quá trình đi từ dưới lên", ta sử dụng một bảng để lưu giữ lời giải của các bài toán con đã giải. Khi giải một bài toán con cần đến nghiệm của bài toán con cỡ nhỏ hơn, ta chỉ cần tìm ở trong bảng, không cần giải lại. Chính vì thế mà các thuật toán được thiết kế bằng quy hoạch động sẽ rất có hiệu quả.