Lập trình quy hoạch động Dynamic programing

Chia sẻ: Huỳnh Ngọc Hiệp | Ngày: | Loại File: PPTX | Số trang:15

Thêm vào BST

Báo xấu

320
lượt xem 62
download

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

Để giải quyết một bài toán lớn, ta chia nó thành nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Khi không biết cần phải giải bài những toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn

Chủ đề:

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

Lưu

Nội dung Text: Lập trình quy hoạch động Dynamic programing

Lập trình quy hoạch động dynamic programing
Nội dung Giới thiệu.  Phương pháp thực hiện.  Ví dụ minh họa 
BÀI TOÁN
ĐỆ QUY int F(int i) int main()   { { if (i
Lưu lại lời giải của bước trước và được sử  dụng để tìm lời giải của bài toán mức khó hơn ? int main() { F[1]=1; F[2]=1; for (int i=3;i
Lập trình qui hoạch động Lập trình 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 con nhỏ hơn” (subsubproblem). Lập trình qui hoạch động giải các “bài toán con nhỏ hơn” 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 các bài toán đó đó. 6
Quy hoạch động Giải quyết bài toán tối ưu có tính chất đệ quy  Xuất phát từ bài toán con xác định đã được giải  để giải quyết bài toán lớn hơn dựa vào kết quả bài toán con.
Phạm vi áp dụng Các bài toán có thể phân rã thành các bài toán  con xác định. Có đủ không gian vật lý.  Hữu hạn các bước giải. 
Các bước của qui hoạch động Sự xây dựng một giải thuật qui hoạch động có thể được chia làm bốn bước: Đặc tả cấu trúc của lời giải tối ưu. 1. Mô tả lời giải tối ưu theo cách đệ quy. 2. Tính trị lời giải tối ưu theo kiểu bottom-up. 3. Xây dựng lời giải tối ưu từ những thông tin đã được 4. tính toán. 9
Một số bài toán qhđ Tìm dãy con chung dài nhất.  Bố trí phòng họp.  Cho thuê máy. 
Xâu con chung dài nhất Sequence 1: president Sequence 2: providence president providence
0 if i = 0 or j = 0,  c[i, j ] = c[i − 1, j − 1] + 1 if i, j > 0 and xi = y j , max( c[i − 1, j ], c[i, j − 1]) if i, j > 0 and x ≠ y .  i j
1 2 3 4 5 6 7 8 9 10 i j 0 p r o v i d e n c e 0 0 0 0 0 0 0 0 0 0 0 0 1 p 0 1 1 1 1 1 1 1 1 1 1 2 r 0 1 2 2 2 2 2 2 2 2 2 3 e 0 1 2 2 2 2 2 3 3 3 3 4 s 0 1 2 2 2 2 2 3 3 3 3 5 i 0 1 2 2 2 3 3 3 3 3 3 6 d 0 1 2 2 2 3 4 4 4 4 4 7 e 0 1 2 2 2 3 4 5 5 5 5 8 n 0 1 2 2 2 3 4 5 6 6 6 9 t 0 1 2 2 2 3 4 5 6 6 6
The backtracing algorithm procedure Output-LCS(A, prev, i, j) 1 if i = 0 or j = 0 then return Output − LCS ( A, prev, i − 1, j − 1) 2 if prev(i, j)=” “ then  print ai 3 else if prev(i, j)=” “ then Output-LCS(A, prev, i-1, j) 4 else Output-LCS(A, prev, i, j-1)
1 2 3 4 5 6 7 8 9 10 i j 0 p r o v i d e n c e 0 0 0 0 0 0 0 0 0 0 0 0 1 p 0 1 1 1 1 1 1 1 1 1 1 2 r 0 1 2 2 2 2 2 2 2 2 2 3 e 0 1 2 2 2 2 2 3 3 3 3 4 s 0 1 2 2 2 2 2 3 3 3 3 5 i 0 1 2 2 2 3 3 3 3 3 3 6 d 0 1 2 2 2 3 4 4 4 4 4 7 e 0 1 2 2 2 3 4 5 5 5 5 8 n 0 1 2 2 2 3 4 5 6 6 6 9 t 0 1 2 2 2 3 4 5 6 6 6 Output: priden