Xem mẫu

Dynamic Programming 10.2.2004 Ch. 1: Dynamic Programming 1 Giới thiệu ° Dynamic programming — giải 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. — (ở đây “programming” không có nghĩa là lập trình). ° So sánh dynamic programming và “chia­và­trị” (divide­and­conquer) — Giải thuật chia­và­trị ° chia bài toán thành các bài toán con độc lập , ° giải chúng bằng đệ quy, ° kết hợp chúng để có lời giải cho bài toán ban đầu. — Giải thuật dynamic programming ° các bài toán con không độc lập với nhau: chúng có chung các bài toán con nhỏ hơn. ° giải mỗi bài toán con chỉ một lần, và ghi nhớ lời giải đó trong một bảng để truy cập khi cần đến. 10.2.2004 Ch. 1: Dynamic Programming 2 Bài toán tối ưu ° Bài toán tối ưu — có thể có nhiều lời giải — mỗi lời giải có một trị ° Tìm lời giải có trị tối ưu (cực tiểu hay cực đại). 10.2.2004 Ch. 1: Dynamic Programming 3 Nguyên tắc của dynamic programming ° Một giải thuật dynamic programming được xây dựng qua bốn bước: 1. Xác định cấu trúc của một lời giải tối ưu. 2. Định nghĩa đệ quy cho giá trị của một lời giải tối ưu. 3. Tính giá trị của một lời giải tối ưu từ dưới lên (“bottom­up”). 4. Xây dựng lời giải tối ưu từ các thông tin đã tính. 10.2.2004 Ch. 1: Dynamic Programming 4 Nhân một chuỗi ma trận ° Cho một chuỗi ma trận A1, A2,..., An . ° Xác định tích A1A2 An dựa trên giải thuật xác định tích của hai ma trận. ° Biểu diễn cách tính tích của một chuỗi ma trận bằng cách “đặt giữa ngoặc” (parenthesize) các cặp ma trận sẽ được nhân với nhau. ° Một tích của một chuỗi ma trận là fully parenthesized nếu nó là — một ma trận hoặc là — tích của hai tích của chuỗi ma trận fully parenthesized khác, và được đặt giữa ngoặc. Ví dụ: một vài tích của chuỗi ma trận được fully parenthesized — A — (AB) — ((AB)C). 10.2.2004 Ch. 1: Dynamic Programming 5 ... - tailieumienphi.vn
nguon tai.lieu . vn