Cấu trúc dữ liệu - Phần 7

Tài liệu tham khảo bài giảng môn Cấu trúc dữ liệu - Phần 7 Phương pháp quy hoạch động
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu - Phần 7Phương pháp quy hoạch động (dynamic programming) GVGD: Trương Phước Hải Nội dung 1. Nguyên lý quy hoạch động 2. Công thức truy hồi 3. Phương pháp quy hoạch động 4. Một số bài toán ứng dụngTrương Phước Hải 2 Nguyên lý quy hoạch động  Chia để trị là phương pháp chủ đạo trong việc thiết kế các thuật toán có tính chất đệ quy  Chia để trị phân nhỏ bài toán và giải quyết độc lập từng phần một cách đệ quy  Tư tưởng đệ quy dễ hiểu và dễ cài đặt nhưng tiêu tốn nhiều bộ nhớ (stack lưu trữ các lời gọi)Trương Phước Hải 3 Nguyên lý quy hoạch động  Xét bài toán Tìm phần tử thứ N của dãy Fibonacci  Dãy được định nghĩa FN = FN-1 + FN-2 với F0 = F1 = 1   Giải bằng phương pháp chia để trị Chia: Fn được chia thành FN-1 và FN-2  Trị: tính FN-1 và FN-2 một cách đệ quy  Gộp: tính tổng FN-1 + FN-2 để được FN Trương Phước Hải 4 Nguyên lý quy hoạch động  Giải thuật chia để trị cho bài toán F(N) If (N = 0) Or (N = 1) Then Return 1 End If Return F(N - 1) + F(N - 2) End FTrương Phước Hải 5 Nguyên lý quy hoạch động  Minh họa sơ đồ giải bài toán tính F(5) 8 F(5) 5 3 F(4) F(3) 3 2 2 1 F(3) F(2) F(2) F(1) 2 1 1 1 1 1 F(2) F(1) F(1) F(0) F(1) F(0) 1 1 F(1) F(0)Trương Phước Hải 6 Nguyên lý quy hoạch động  Xây dựng lời giải của một bài toán thông qua lời giải của các bài toán con  Các bài con tiếp tục được chia nhỏ để giải quyết nhưng không sử dụng kỹ thuật đệ quy  Sử dụng bảng tra cứu để lưu lại kết quả đã tính được và tính dần đến nghiệm của bài toán bằng một công thức xác địnhTrương Phước Hải 8 Nội dung 1. Nguyên lý quy hoạch động 2. Công thức truy hồi 3. Phương pháp quy hoạch động 4. Một số bài toán ứng dụngTrương Phước Hải 9 Công thức truy hồi  Trong quá trình quay lui, đệ quy sẽ gọi lại nhiều lần các bài toán con đã được gọi ở các bước trước Gây tiêu tốn thời gian thực hiện lặp lại và tài nguyên bộ  nhớ Lưu trữ nghiệm của tất cả bài toán con và kết hợp chúng  theo một công thức xác định để tìm nghiệm cho bài toán ban đầu  Công thức kết hợp nghiệm của các bài toán con để tìm nghiệm của bài toán lớn hơn gọi là công thức truy hồiTrương Phước Hải 10 Công thức truy hồi  Ví dụ 1 Xét lại bài toán tìm phần tử thứ N của dãy Fibonacci   Giải bài toán ở một cách nhìn khác Sử dụng bảng tra lưu lại giá trị các số Fibonacci nhằm tính  dần cho các số Fibonacci tiếp theoTrương Phước Hải 11 Công thức truy hồi  Tạo mảng lưu kết quả để tra cứu Gọi F[i] là giá trị của phần tử Fibonacci thứ i, vậy phần tử  thứ N của dãy Fibonacci là F[N]. Ta có F[0] = F[1] = 1  Công thức truy hồi  F[i] = F[i-1] + F[i-2], với 2 ≤ i ≤ N  ? ? 1 1 ...