Bài giảng Lập trình động

"Bài giảng Lập trình động" tìm hiểu về quy hoạch động; đặc điểm của phương pháp chia để trị; một chiến lược tối ưu có đặc trưng; chuỗi con đơn điệu dài nhất. Mời các bạn cùng tham khảo bài giảng để nắm chi tiết nội dung kiến thức.
Nội dung trích xuất từ tài liệu:
Bài giảng Lập trình động DynamicProgrammingIntroductionQuy hoạch động: Thường dùng để giải các bài toán tối ưu; Phân rã bài toán thành các bài toán con; hình thành lời giải từ các bài toán con; Lưu trữ lời giải các bài toán con trong một bảng dữ liệu thay cho giải lại các bài toán con (đệ quy). Đặc điểm của phương pháp chia để trị: •Thường phát sinh các bài toán con “mới” •Lời giải các bài toán con thường được sử dụng nhiều lần (“phủ chồng”).2013-09-22 Dao Thanh Tinh 2Introduction (2)Ví dụ 1: Tính số Fibonacci thứ n Đệ quy: với f0=0 và f1 = 1 long f(int m) { if (n==0) return 0;Theo công thức: else if (n==1) return 1; n n 1 5  1 5  else return f(n-1) + f(n);      }  2   2 fn      Ví dụ, để tính f(n) phải tính f(2) n-1 lần! 5 Tiết kiệm bộ nhớ:Dùng mảng: f0 = 0; f1=1;f[0] = 0; f[1]=1; for (i=2; in;i++)for (i=2; in;i++) { tg = f1 + f0; f[i] = f[i-1] + f[i-2]; f0 = f1;output f[n]; f1 = tg; } output f1;2013-09-22 Dao Thanh Tinh 3Introduction (3)Số Fibonacci thứ nn=50F(n) =12,586,269,025Phương pháp đệ quy 650 800sCác phương pháp khác 1s2013-09-22 Dao Thanh Tinh 4Introduction (4) Tiếp cận theo hướng bottom-up 1. Xuất phát từ những bài toán cơ sở có lời giải (cách giải đơn giản hoặc có sẵn) 2. Từ tập lời giải các bài toán con tìm lời giải của bài toán lớn hơn.2013-09-22 Dao Thanh Tinh 5Introduction (5) PRINCIPLE OF OPTIMALITY “An optimal policy has the property that whatever the initial state and initial decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decisions.” Richard Bellman “The Theory of Dynamic Programming”, Bulletin of the American Mathematical Society, Vol. 60, No. 6, 1954 (503-515).2013-09-22 Dao Thanh Tinh 6Introduction (6)Một chiến lược tối ưu có đặc trưng: với mọi trạng thái khởi tạo và quyết định ban đầu, các quyết định tiếp theo phải thiết lập được chiến lược tối ưu đối với trạng thái được hình thành từ các quyết định trước đó. Chiến lược tối ưu: có thể trong một số bước đầu tiên lựa chọn dường như không tốt nhưng tổng hợp cả quá trình phải tốt nhất.2013-09-22 Dao Thanh Tinh 7Introduction (7) Kỹ thuật giải bài toán bằng phương pháp QHĐ: a) Bắt đầu với những trường hợp con nhỏ nhất (thường là đơn giải nhất và giải được ngay). b) Tổ hợp các kết quả đã có (không phải tính lại) của các trường hợp con, sẽ đạt đạt tới kết quả của trường hợp có kích thước lớn và tổng quát hơn, cho đến khi cuối cùng đạt tới lời giải của bài toán ban đầu.2013-09-22 Dao Thanh Tinh 8Introduction (8) Ví dụ 2: Xét bài toán: Cho túi T có sức chứa 10kg và 3 đồ vật: 1) 5kg, trị giá 4$ 2) 4kg, trị giá 10$ 3) 6kg, trị giá 3$ Xếp những đồ vật nào vào túi để có giá trị lớn nhất?2013-09-22 Dao Thanh Tinh 9 Introduction (9) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0!!!! đv 0 1 2 3 4 5 6 7 8 9 10Giá trị lớn nhất 0 0 0 0 0 0 0 0 0 0 0 0của túi: 2013-09-22 Dao Thanh Tinh 10 Introduction (10) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0Giá trị lớn nhất 1 0 0 0 0 0 4 4 4 4 4 4của túi: 2013-09-22 Dao Thanh Tinh 11 Introduction (11) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 4 4 4 4 4 4Giá trị lớn nhấtcủa túi: 2 0 0 0 0 10 10 10 10 10 14 14 2013-09-22 Dao Thanh Tinh 12 Introduction (12) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 4 4 4 4 4 4 ...