Quy hoạch động

Giới thiệu

Phương pháp chia để trị, tức chia bài toán lớn thành từng bài toán con, lại chia các bài toán con thành bài toán con nhỏ hơn để giải quyết rồi gộp kết quả các bài toán con lại để cho ra kết quả của bài toán lơn, đã nói kỹ ở phần đễ quy.

Theo đó, các em cũng thấy là phương pháp này tuy đơn giản, nhưng sẽ gặp vấn đề lớn về mặt thời gian và không gian lưu trữ, vì trong quá trình phân rã, chúng ta sẽ gặp rất nhiều bài toán con giống hệt nhau và chương trình phải giải quyết hết và lưu trữ lại hết tất cả với cùng một cách giống hệt nhau.

Tư tưởng quy hoạch động

Tư tưởng chính của quy hoạch động là ta sẽ dùng một bảng lưu trữ lại kêt quả các bài toán con đã giải. Khi giải một bài toán con mà cần kết quả của bài toán con nhỏ hơn, ta chỉ việc lấy từ trong bảng ra mà không cần giải lại. Việc này tuy đơn giản nhưng lại hiệu quả vô cùng và là một điểm mạnh của quy hoạch động.

Mô hình tổng quát

B1: Tìm cách chặt nhỏ bài toán ( có thể theo một chiều hoặc nhiều chiều)

B2: Tìm neo - chặt đến khi nào thì dừng để đưa ra cách giải nghiệm cho bài toán con nhỏ nhất

B3: Tìm công thức hồi quy, để từ nghiệm của bài toán con đưa về nghiệm của bài toán lớn

B4: Tạo bảng lưu trữ kết quả các bài toán con, số chiều của bảng phụ thuộc vào số chiều mà ta chặt bài toán ra.

B5: Tìm ra nghiệm bài toán từ nghiệm của các bài toán con

Ví dụ

Chúng ta quay lại với bài toán dãy Fibonacci

Hãy xác định số Fibonacci thứ n

Cách 1: Theo cách chia để trị

Tính Fn dựa vào F_n-1 và Fn-2

Ví dụ với n=6, chương trình chính gọi F(6), như các em đã biết, nó sẽ gọi tiếp F(5) và F(4)....

\

Theo mô hình mô phỏng trên, các e dễ dàng thấy được là chương trình phải tính lại nhiều lần F(1), F(2) và F(3).

Cách 2: Quy hoạch động

Ta sẽ sử dụng một mảng S[0..MaxN] để lưu lại lời giải cho các bài toàn con, Si lưu kết quả bài toán tính số Fibonacci thứ i.

Các em sẽ thấy ngay mỗi bài toán con chỉ giải đúng một lần.

Thử cài cả hai cách và chạy với n = 40 sẽ thấy sự khác biệt.

Bài Tập

1. Dãy con đơn điệu tăng dài nhất. Trang 101 SGK chuyên Tin quyển 1 - HSD.

2. Dãy con chung dài nhất. Trang 104 SGK chuyên Tin quyển 1 - HSD.

3. Bài toán cái túi. Trang 106 SGK chuyên Tin quyển 1 - HSD