Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Chương 3: Quy hoạch động

Bài giảng Chương 3: Quy hoạch động sẽ cung cấp cho các bạn những kiến thức về các bài toán con chung lồng nhau và giải thuật quy hoạch động; giải thuật quy hoạch động giải bài toán tập độc lập lớn nhất, cái túi, dãy con lớn nhất, dãy con chung dài nhất, nhân dãy ma trận. | Chương 3. Quy hoạch động 9.1. Các bài toán con chung lồng nhau và giải thuật quy hoạch động 9.2. Giải thuật quy hoạch động giải bài toán tập độc lập lớn nhất. 9.3. Giải thuật quy hoạch động giải bài toán cái túi 9.4. Giải thuật quy hoạch động giải bài toán dãy con lớn nhất 9.5. Giải thuật quy hoạch động giải bài toán dãy con chung dài nhất. 9.6. Giải thuật quy hoạch động giải nhân dãy ma trận. 9.1. Các bài toán con chung lồng nhau và giải thuật quy hoạch động 9.1.1. Ví dụ về bài toán con chung lồng nhau 9.1.2. Quy hoạch động là gì? 9.1.3. Ba giai đoạn của bài toán quy hoạch động 9.1.1. Các bài toán con chung lồng nhau trong giải thuật chia để trị Khi chia bài toán thành các bài toán con, trong nhiều trường hợp, các bài toán con khác nhau lại chứa các bài toán con hoàn toàn giống nhau. Ta nói rằng chúng chứa các bài toán con chung giống nhau Ví dụ: Ví dụ về bài toán con lồng nhau Tính số Fibonaci thứ n Định nghĩa số Fibonaci F(n): F(0)=0 F(1)=1 F(n)=F(n-2)+F(n-1) với n>1 Ví dụ: F(2)=1, F(3)= 2, F(4) = 3 , F(5)=5, F(6)=8 Ví dụ: Tính số Fibonaci thứ n Tính theo đệ quy {top down}: Function R_Fibonaci(n); If n So sánh hai giải thuật Khi tính F(5): Giải thuật đệ quy tính F(5) = F(3)+F(4) Tính F(3) F(3)= F(2)+F(1) F(2)=F(1)+F(0) = 1 F(3)= 1+1= 2 Tính F(4) F(4)= F(2)+F(3) F(2)= F(0)+F(1) = 1 F(3)=F(1)+F(2) = 1+F(2) F(2)= F(0)+F(1) = 2 F(3)= 1+2 =3 F(4) = 2+3 = 5 Tổng hợp F(5) = 3+5 =8 Để tính F(5): 2 lần tính F(3) 3 lần tính F(2) Tính F5 2 lần tính F(3) 3 lần tính F(2) F5 F3 F4 F1 F2 F0 F1 F2 F3 F1 F2 F0 F1 F0 F1 Dùng Quy hoạch động để tính số Fibonacy thứ n Function Fibonaci(n); If n 9.1.2. Quy hoạch động là gì? Quy hoạch động là một ký thuật thiết kế thuật | Chương 3. Quy hoạch động 9.1. Các bài toán con chung lồng nhau và giải thuật quy hoạch động 9.2. Giải thuật quy hoạch động giải bài toán tập độc lập lớn nhất. 9.3. Giải thuật quy hoạch động giải bài toán cái túi 9.4. Giải thuật quy hoạch động giải bài toán dãy con lớn nhất 9.5. Giải thuật quy hoạch động giải bài toán dãy con chung dài nhất. 9.6. Giải thuật quy hoạch động giải nhân dãy ma trận. 9.1. Các bài toán con chung lồng nhau và giải thuật quy hoạch động 9.1.1. Ví dụ về bài toán con chung lồng nhau 9.1.2. Quy hoạch động là gì? 9.1.3. Ba giai đoạn của bài toán quy hoạch động 9.1.1. Các bài toán con chung lồng nhau trong giải thuật chia để trị Khi chia bài toán thành các bài toán con, trong nhiều trường hợp, các bài toán con khác nhau lại chứa các bài toán con hoàn toàn giống nhau. Ta nói rằng chúng chứa các bài toán con chung giống nhau Ví dụ: Ví dụ về bài toán con lồng nhau Tính số Fibonaci thứ n Định nghĩa số Fibonaci F(n): .