Chapter 5: CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT- Quy hoạch động

Chia sẻ: No Comment | Ngày: | Loại File: PPT | Số trang:79

Thêm vào BST

Báo xấu

340
lượt xem 40
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Quy hoạch động (dynamic programming) giải các bài toán bằng cách kết hợp các lời giải của các bài toán con của bài toán đang xét.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chapter 5: CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT- Quy hoạch động

1 CHƯƠNG 5 CÁC CHIẾN LƯỢC THIẾT KẾ GIẢI THUẬT
Nội dung 2 Qui hoạch động  Giải thuật tham lam  Giải thuật quay lui (backtracking)  Giải thuật nhánh và cận 
Qui hoạch động • Quy hoạch động (dynamic programming) giải các bài toán bằng cách kết hợp các lời giải của các bài toán con của bài toán đang xét. • Phương pháp này khả dụng khi các bài toán con không độc lập đối với nhau, tức là khi các bài toán con có dùng chung những bài toán “cháu” (subsubproblem). • Qui hoạch động giải các bài toán “cháu” dùng chung này một lần và lưu lời giải của chúng trong một bảng và sau đó khỏi phải tính lại khi gặp lại bài toán cháu đó. • Qui hoạch động được áp dụng cho những bài toán tối ưu hóa (optimization problem).
Qui hoạch động Quy hoạch động là một kỹ thuật thiết kế thuật toán trong đó: • Bài toán được chia thành những bài toán con kích thước nhỏ hơn và giải chúng một cách độc lập, ghi lại các kết quả, để tổng hợp thành lời giải của bài toán ban đầu Khác với chia để trị: Trong giải thuật chia để trị: • Các bài toán con độc lập, sau đó các bài toán con này đ ược giải một cách đệ quy. Trong giải thuật quy hoạch động: • Các bài toán con là không độc lập với nhau, nghĩa là các bài toán con cùng có chung các bài toán con nhỏ hơn.
Ba giai đoạn của quy hoạch động Phân rã: Chia bài toán cần giải thành những bài toán con  nhỏ hơn có cùng dạng với bài toán ban đầu sao cho bài toán con kích thước nhỏ nhất có thể giải một cách trực tiếp. Bài toán xuất phát có thể coi là bài toán con có kích thước lớn nhất Giải các bài toán con và ghi nhận lời giải: Lưu trữ lời giải  của các bài toán con vào một bảng để sử dụng lại nhiều lần do đó không phải giải lặp lại cùng một bài toán. Tổng hợp lời giải: Lần lượt từ lời giải của các bài toán  con kích thước nhỏ hơn xây dựng lời giải của bài toán kích thước lớn hơn, cho đến khi thu được lời giải của bài toán xuất phát (là bài toán con có kích thước lớn nhất).
Lược đồ quy hoạch động Kỹ thuật giải các bài toán con của quy Phân rã hoạch động là quá Giải và ghi nhận lời trình đi từ dưới lên giải các bài toán (bottom – up) là điểm con khác quan trọng với phương pháp chia để Tổng hợp trị, trong đó các bài lời giải toán con được trị một Bottom- cách đệ quy (top – Up down).
Các yếu tố của một giải thuật quy hoạch động giải bài toán tối ưu Cơ sở của quy hoạch động: Những trường hợp  đơn giản có thể tính trực tiếp Cấu trúc con tối ưu: Phương pháp chia nhỏ các  bài toán cho đến khi gặp được bài toán cơ sở. Tổng hợp: hệ thức truy hồi tính giá trị tối ưu của  hàm mục tiêu của bài toán lớn qua giá trị tối ưu của các bài toán con thành phần.
Bốn bước của qui hoạch động 1. Đặc trưng hóa cấu trúc của lời giải tối ưu. 2. Định nghĩa giá trị của lời giải tối ưu một cách đệ quy. 3. Tính trị của lời giải tối ưu theo kiểu từ dưới lên. 4. Cấu tạo lời giải tối ưu từ những thông tin đã được tính toán.
Hiệu quả của quy hoạch động Khi có các bài toán con lồng nhau, phương pháp chia  để trị sẽ tỏ ra không hiệu quả, khi nó phải lặp đi lặp lại việc giải các bài toán con chung đó. Quy hoạch động sẽ giải mỗi bài toán con một lần và  lời giải của các bài toán con sẽ được ghi nhận, để thoát khỏi việc giải lại bài toán con mỗi khi ta đòi hỏi lời giải của nó. Quy hoạch động thường được áp dụng để giải các bài  toán tối ưu. Trong các bài toán tối ưu, ta có một tập các lời giải, và một hàm mục tiêu nhận giá trị số. Ta cần tìm một lời giải để hàm mục tiêu đạt giá trị nhỏ nhất hoặc lớn nhất.
Lược đồ thuật giải Dynamic_Pro(A, x) 1. Chia bài toán cần giải thành nhiều bài toán con kích thước tăng dần 2. Sử dụng một bảng, lần lượt giải và lưu trữ lời giải x1, …,xn của các bài toán con A1, …, An từ kích thước nhỏ đến lớn vào bảng sao cho việc giải các bài toán có thể sử dụng kết quả các bài toán con trước đó 3. Lời giải bài toán đã cho A được tính toán cu ối cùng là x=xn
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ụ về bài toán con lồng nhau Tính số Fibonaci thứ n Tính theo đệ quy {top down}: Function Fibonaci(n); Begin 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)  Để tính F(5): F(2)=F(1)+F(0) =1   2 lần tính F(3) F(3)=1+ 2 1=   3 lần tính F(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) =1  F(3)=1+ = 12  F(4) =1+ = 23  Tổng hợp F(5) =2+ = 35  
Tính F5 F5 F3 F4 F2 F3 F1 F2 F2 F0 F1 F1 F0 F1 F0 F1 2 lần tính F(3) 3 lần tính F(2)  
Dùng Qui hoạch động để tính số Fibonacy thứ n Tính theo qui hoạch động {bottom down}: Func tio n Fibo nac i(n); If n
Thí dụ 2: Một cặp thỏ khi được sinh ra sau 2 tháng thì bắt đầu sinh một cặp thỏ con, nhưng sau đó thì cứ 1 tháng thì chúng sinh thêm một cặp thỏ con nữa. Hỏi nếu bắt đầu từ tháng thứ nhất ta có một cặp thỏ thì sau n tháng ta có bao nhiêu cặp thỏ.
Thí dụ 2: Gỉai: Gọi số cặp thỏ có được sau n tháng là f(n) Các cặp thỏ được sinh ra ở tháng thứ n1 không sinh, nhưng mỗi cặp thỏ ở tháng thứ n2 đều sinh thêm một cặp Vì vậy có hệ thức truy hồi f(n) = f(n1) + f(n2), f(1) = 1, f(2) = 1 Dễ dàng có một lời giải bằng kỹ thuật đệ qui để tính f(n) f(n) if n=1 or n=2 1 then return1 2 else if n > 2 3 then return f(n1) + f(n2) 4
Thí dụ2:
Thí dụ 2: Lời giải bằng kỹ thuật qui hoạch động để tính f(n) F_Dynamic_Programming(n) 1 f[1] ←1 // tạo ra một bảng (danh sách) để lưu trữ 2 f[2] ←1 // kết quả các bài toán con 3 For i ←3 to n 4 do f[i] ←f[i-1] +f[i-2] // Giải các bài toán lớn hơn Return f[n] // Kết quả 5
Thí dụ 3: