Quy hoạch động

Trong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure).Nhà toán học Richard Bellman đã phát minh phương pháp quy hoạch động vào năm1953. Ngành này đã được thành lập như là một chủ đề về kỹ nghệ và phân tích hệthống đã được tổ chức IEEE thừa nhận....
Nội dung trích xuất từ tài liệu:
Quy hoạch độngquy hoach dongTrong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gianchạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau(overlapping subproblem) và cấu trúc con tối ưu (optimal substructure).Nhà toán học Richard Bellman đã phát minh phương pháp quy hoạch động vào năm1953. Ngành này đã được thành lập như là một chủ đề về kỹ nghệ và phân tích hệthống đã được tổ chức IEEE thừa nhận.Mục lục [ẩn]1 Tổng quan2 Ví dụ2.1 Dãy Fibonacci2.2 Bàn cờ3 Các thuật toán sử dụng quy hoạch động4 Liên kết ngoài5 Tham khảo[sửa] Tổng quanHình 1. Tìm đường đi ngắn nhất sử dụng cấu trúc con tối ưu; một đường lượn sóngđại diện cho một đường đi ngắn nhất giữa hai đỉnh mà nó nốiCấu trúc con tối ưu cónghĩa là các lời giải tối ưu cho các bài toán con có thể được sử dụng để tìm các lờigiải tối ưu cho bài toán toàn cục. Ví dụ, đường đi ngắn nhất tới một đỉnh trong mộtđồ thị có thể được tìm thấy bằng cách: trước hết tính đường đi ngắn nhất tới đích từtất cả các đỉnh kề nó, rồi dùng kết quả này để chọn đường đi toàn cục tốt nhất, nhưtrong hình 1. Nói chung, ta có thể giải một bài toán với cấu trúc con tối ưu bằng mộtquy trình ba bước:Chia bài toán thành các bài toán con nhỏ hơn.Giải các bài toán này một cách tối ưu bằng cách sử dụng đệ quy quy trình ba bướcnày.Sử dụng các kết quả tối ưu đó để xây dựng một lời giải tối ưu cho bài toán ban đầu.Các bài toán con được giải bằng cách chia chúng thành các bài toán nhỏ hơn, và cứtiếp tục như thế, cho đến khi ta đến được trường hợp đơn giản dễ tìm lời giải.Hình 2. Đồ thị bài toán con cho dãy Fibonacci. Đây không phải là một cấu trúc cây màlà một đồ thị có hướng phi chu trình mô tả quan hệ giữa các bài toán con gối nhau.Nóirằng một bài toán có các bài toán con trùng nhau có nghĩa là mỗi bài toán con đó đượcsử dụng để giải nhiều bài toán lớn hơn khác nhau. Ví dụ, trong dãy Fibonacci, F3 = F1+ F2 and F4 = F2 + F3 - khi tính mỗi số đều phải tính F2. Vì tính F5 cần đến cả F3 vàF4, một cách tính F5 một cách ngây thơ có thể sẽ phải tính F2 hai lần hoặc nhiều hơn.Điều này áp dụng mỗi khi có mặt các bài toán con gối nhau: một cách tiếp cận ngâythơ có thể tốn thời gian tính toán lại lời giải tối ưu cho các bài toán con mà nó đã giải.Để tránh việc đó, ta lưu trữ lời giải của các bài toán con đã giải. Do vậy, nếu sau nàyta cần giải lại chính bài toán đó, ta có thể lấy và sử dụng kết quả đã được tính toán.Hướng tiếp cận này được gọi là lưu trữ (trong tiếng Anh được gọi là memoization,không phải memorization, dù từ này cũng hợp nghĩa). Nếu ta chắc chắn rằng một lờigiải nào đó không còn cần thiết nữa, ta có thể xóa nó đi để tiết kiệm không gian bộnhớ. Trong một số trường hợp, ta còn có thể tính lời giải cho các bài toán con mà tabiết trước rằng sẽ cần đến.Tóm lại, quy hoạch động sử dụng:Các bài toán con gối nhauCấu trúc con tối ưuMemoizationQuy hoạch động thường dùng một trong hai cách tiếp cận:top-down (Từ trên xuống): Bài toán được chia thành các bài toán con, các bài toán connày được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại chúng. Đâylà đệ quy và lưu trữ được kết hợp với nhau.bottom-up (Từ dưới lên): Tất cả các bài toán con có thể cần đến đều được giải trước,sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn. Cách tiếp cận này hơitốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khiviệc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trướckhông được trực giác lắm.Một số ngôn ngữ lập trình hàm, nổi tiếng nhất là Haskell, có thể tự động lưu trữ kếtquả của một lời gọi hàm với một tập đối số (argument) cụ thể, để tăng tốc cách đánhgiá call-by-name (cơ chế này được gọi là call-by-need). Việc này chỉ có thể đối với cáchàm không có hiệu ứng phụ, tính chất này luôn luôn đúng trong ngôn ngữ Haskellnhưng ít khi đúng trong các ngôn ngữ lập trình mệnh lệnh, chẳng hạn Pascal, C, C++,Java...[sửa] Ví dụ[sửa] Dãy FibonacciMột cài đặt đơn giản của một hàm tính phần tử thứ n của dãy Fibonacci, trực tiếp dựatheo định nghĩa toán học. Cài đặt này thực hiện rất nhiều tính toán thừa.:function fib(n)if n = 0 or n = 1return nelsereturn fib(n − 1) + fib(n − 2)Lưu ý rằng nếu ta gọi, chẳng hạn, fib(5), ta sẽ tạo ra một cây các lời gọi hàm, trongđó các hàm của cùng một giá trị được gọi nhiều lần:fib(5)fib(4) + fib(3)(fib(3) + fib(2)) + (fib(2) + fib(1))((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))Cụ thể, fib(2) được tính hai lần. Trong các ví dụ lớn hơn, sẽ có nhiều giá trị của fib,hay các bài toán con được tính lại, dẫn đến một thuật toán có thời gian lũy thừa.Bây giờ, giả sử ta có một đối tượng ánh xạ đơn giản, nó ánh xạ mỗi giá trị của fib đãđược tính tới kết quả của giá trị đó. Ta sửa đổi hàm trên như sau để sử dụng và cậpnhật ánh xạ trên. H ...