Fibonacci và quy hoạch động

Nhờ máy tính tính số Fibonacci thứ 40 theo cách hiển nhiên nhất, nó sẽ tạo ra hơn 331 triệu lời gọi. Nhờ nó tính bằng một bảng, chỉ cần 39 phép cộng. Sự khác biệt đó chính là quy hoạch động, và dãy Fibonacci là nơi hầu như ai cũng gặp nó lần đầu.

Một hàng ô bảng chứa các số Fibonacci, ô đang được điền màu cam và hai ô được cộng lại màu xanh lam
Một hàng ô bảng chứa các số Fibonacci, ô đang được điền màu cam và hai ô được cộng lại màu xanh lam

Bài toán

Dãy Fibonacci bắt đầu bằng 0, 1, và mỗi số sau đó bằng tổng hai số đứng trước: 0, 1, 1, 2, 3, 5, 8, 13, 21, v.v. Viết thành quy tắc: F(0) = 0, F(1) = 1 và F(n) = F(n − 1) + F(n − 2). Quy tắc này mang tính đệ quy, và chuyển thẳng nó thành một chương trình đệ quy thì rất dễ, nhưng chương trình đó hóa ra lại rất chậm.

Vì sao đệ quy cứ lặp lại

Để tìm F(5), chương trình gọi F(4) và F(3). F(4) lại gọi F(3) và F(2), nên F(3) bị tính hai lần, F(2) ba lần và F(1) năm lần. Vẽ thành cây, số lời gọi gần như tăng gấp đôi ở mỗi tầng, và tổng số lời gọi cho F(n) là 2·F(n + 1) − 1. Các bài toán nhỏ gối lên nhau: cùng những bài toán đó quay lại hết lần này đến lần khác. Đó là dấu hiệu cho thấy quy hoạch động sẽ có ích.

Hai cách ghi nhớ

Ghi nhớ giữ nguyên đệ quy nhưng ghi mọi đáp án vào bảng, và mỗi lời gọi đều tra bảng trước khi làm bất cứ việc gì. Lập bảng điền bảng từ dưới lên: F(0) và F(1) trước, rồi F(2) từ hai số đó, F(3) từ F(2) và F(1), cứ thế đến F(n). Dù theo cách nào, mỗi số hạng cũng chỉ được tính một lần, nên F(n) tốn n − 1 phép cộng thay vì một số lời gọi tăng theo hàm mũ.

Một ví dụ

Từ dưới lên cho F(7): bắt đầu với 0 và 1. Sau đó 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 và 5 + 8 = 13, vậy F(7) = 13 sau sáu phép cộng. Đệ quy thuần sẽ cần 2·F(8) − 1 = 41 lời gọi cho cùng đáp án. Với từ trên xuống, các lời gọi đầu tiên đi thẳng xuống F(1) dọc theo mép trái của cây; trên đường quay lên, gần như cứ hai lời gọi thì có một lời gọi thấy đáp án đã có sẵn trong bảng.

Nguồn gốc của cái tên

Richard Bellman đặt tên cho quy hoạch động vào đầu những năm 1950, khi đang làm việc tại RAND Corporation. Sau này ông viết rằng ông chọn chữ programming theo nghĩa cũ là lập kế hoạch, còn dynamic vì nó nghe ấn tượng và khó ai phản đối. Bản thân phương pháp này, tức là giải một bài toán thông qua đáp án của những phiên bản nhỏ hơn của nó, ngày nay được dùng trong trình kiểm tra chính tả, công cụ tìm đường và so sánh DNA.

Richard Bellman năm 1962, do Alfred Eisenstaedt chụp. Ông đặt tên cho quy hoạch động vào đầu những năm 1950 khi làm việc tại RAND Corporation.
Richard Bellman năm 1962, do Alfred Eisenstaedt chụp. Ông đặt tên cho quy hoạch động vào đầu những năm 1950 khi làm việc tại RAND Corporation.

Tự khám phá

Mở ứng dụng và nhấn Bước. Với từ dưới lên, ô màu cam là ô đang được điền, còn hai ô màu xanh lam là các số hạng được cộng lại. Chuyển sang từ trên xuống và quan sát ngăn xếp lời gọi dưới bảng tăng lên đến n, rồi thu nhỏ lại khi các đáp án trả về; dòng gợi ý dưới ô Phép cộng đếm xem có bao nhiêu lời gọi được trả lời ngay từ bảng.

Câu hỏi thường gặp

Bài toán con gối nhau là gì?

Là những bài toán nhỏ mà lời giải cần đến nhiều hơn một lần. Cả F(n) và F(n − 1) đều cần F(n − 2), nên đệ quy thuần tính nó hai lần, và sự lãng phí còn nhân lên ở các tầng thấp hơn. Quy hoạch động giải mỗi bài toán con một lần và ghi nhớ đáp án.

Ghi nhớ có nhanh hơn lập bảng không?

Cả hai làm cùng những phép cộng. Lập bảng thường nhanh hơn một chút vì không tạo lời gọi nào, và không thể bị hết bộ nhớ ngăn xếp; ghi nhớ tiện lợi khi chỉ cần một vài đáp án nhỏ, vì nó chỉ tính những đáp án đó.

Có thể tính số Fibonacci nhanh hơn nữa không?

Có. Dùng F(2k) = F(k)·(2·F(k + 1) − F(k)) và F(2k + 1) = F(k)² + F(k + 1)², phương pháp nhân đôi nhanh (fast doubling) chỉ cần khoảng log₂ n bước. Công thức Binet với tỉ lệ vàng cũng cho ra cùng các số đó, nhưng sai số làm tròn khiến nó không đáng tin cậy khi n lớn.

Bảng cần bao nhiêu bộ nhớ?

Một bảng đầy đủ chứa n + 1 số, nhưng mỗi số hạng mới chỉ cần hai số hạng đứng trước, nên một vòng lặp chỉ giữ hai số cũng làm được việc tương tự với bộ nhớ không đổi. Giữ cả bảng sẽ hữu ích khi bạn muốn có tất cả các số hạng, hoặc muốn thấy phương pháp hoạt động ra sao.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử Fibonacci với quy hoạch động