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

Để 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
Nội dung trích xuất từ tài liệu:
Lập trình quy hoạch động Dynamic programingLập trình quy hoạch độngdynamic programingNộ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;iLập trình qui hoạch độngLập trình quy hoạch động (dynamic programming) giải cácbài toán bằng cách kết hợp các lời giải của các bài toáncon 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 độclập đối với nhau, tức là khi các bài toán con có dùng chungnhữ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 trongmột bảng và sau đó khỏi phải tính lại khi gặp lại các bàitoán đó đó. 6Quy 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 độngSự 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 đã được4. tính toán. 9Mộ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ấtSequence 1: presidentSequence 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 10i j 0 p r o v i d e n c e0 0 0 0 0 0 0 0 0 0 0 01 p 0 1 1 1 1 1 1 1 1 1 12 r 0 1 2 2 2 2 2 2 2 2 23 e 0 1 2 2 2 2 2 3 3 3 34 s 0 1 2 2 2 2 2 3 3 3 35 i 0 1 2 2 2 3 3 3 3 3 36 d 0 1 2 2 2 3 4 4 4 4 47 e 0 1 2 2 2 3 4 5 5 5 58 n 0 1 2 2 2 3 4 5 6 6 69 t 0 1 2 2 2 3 4 5 6 6 6The backtracing algorithmprocedure 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 ai3 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 10i j 0 p r o v i d e n c e0 0 0 0 0 0 0 0 0 0 0 01 p 0 1 1 1 1 1 1 1 1 1 12 r 0 1 2 2 2 2 2 2 2 2 23 e 0 1 2 2 2 2 2 3 3 3 34 s 0 1 2 2 2 2 2 3 3 3 35 i 0 1 2 2 2 3 3 3 3 3 36 d 0 1 2 2 2 3 4 4 4 4 47 e 0 1 2 2 2 3 4 5 5 5 58 n 0 1 2 2 2 3 4 5 6 6 69 t 0 1 2 2 2 3 4 5 6 6 6 Output: priden