Đề tài Tìm hiểu phương pháp quy hoạch động cho tính khoảng cách

Số trang: 78
Loại file: pdf
Lượt xem 66
Lượt tải 4

Thông tin tài liệu

Ngày đăng : 21/02/2018 14:59

Mô tả :Quy hoạch động (Dynamic Programming) là một phương pháp rất hiệu quả giải nhiều bài toán tin học, đặc biệt là những bài toán tối ưu. Những bài toán này thường có nhiều nghiệm chấp nhận được và mỗi nghiệm có một giá trị đánh giá. Mục tiêu đặt ra là tìm nghiệm tối ưu, đó là nghiệm có giá trị đánh giá lớn nhất hoặc nhỏ nhất (tối ưu). Ví dụ tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị, tìm chuỗi con chung dài nhất của hai chuỗi, tìm chuỗi con tăng dài nhất, Số lượng bài toán được giải bằng lập trình động cũng rất lớn. Ví dụ riêng kì thi Olympic quốc tế về Tin học 2004 có tới ba bài trong sáu bài có thể giải bằng quy hoạch động. Quy hoạch động 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”. Quy 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 k hi gặp lại bài toán cháu đó. Quy hoạch động được áp dụng cho những bài toán tối ưu hóa (optimization problem). Bốn bước của qui hoạch động : Đặc trưng hóa cấu trúc của lời giải tối ưu. + Định nghĩa giá trị của lời giải tối ưu một cách đệ quy. + Tính trị của lời giải tối ưu theo kiểu từ dưới lên. + Cấu tạo lời giải tối ưu từ những thông tin đã được tính toán. Các thành phần của quy hoạch động : + Tiểu cấu trúc tối ưu -Một bài toán có tính chất tiểu cấu trúc tối ưu nếu lời giải tối ưu chứa trong nó những lời giải tối ưu của những bài toán con. + Những bài toán con trùng lắp - Khi một giải thuật đệ quy gặp lại cùng một bài toán con nhiều lần, ta bảo rằng bài toán tối ưu hóa có những bài toá n con trùng lặp.

Vui lòng click vào nút TẢI XUỐNG bên dưới để tải tài liệu:

Đề tài Tìm hiểu phương pháp quy hoạch động cho tính khoảng cách