Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Công Nghệ Thông Tin
Kỹ thuật lập trình
Bài giảng Phân tích và thiết kế thuật toán: Bài toán quy hoạch động (Dynamic Programming) - Phạm Thế Bảo
Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Phân tích và thiết kế thuật toán: Bài toán quy hoạch động (Dynamic Programming) - Phạm Thế Bảo
Như Ngọc
197
8
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Trong thuật toán, quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu). Cùng tìm hiểu thêm về bài toán quy hoạch động thông qua bài giảng sau đây. | 14 04 2008 BÀI TOÁN QUY HOẠCH ĐỘNG DYNAMIC PROGRAMMING Phạm Thế Bảo Khoa Toán - Tin học Trường Đại học Khoa học Tự nhiên Tp.HCM Nội dung Kỹ thuật chia để trị thường dẫn tới giải thuật đệ quy có giải thuật có thời gian mũ và giải bài toán con nhiều lần. Để tránh giải bài toán con nhiều lần - tạo một bảng lưu trữ kết quả các bài toán con để khi cần sẽ sử dụng lại kết quả. Lấp đầy kết quả các bài toán con theo quy luật nào đó để có kết quả của bài toán ban đầu - quy hoạch động Phạm Thế Bảo 1 14 04 2008 Thuật giải 1. Tạo bảng bằng cách a. Gán giá trị một số ô nào đó. b. Gán giá trị cho các ô khác nhờ vào giá trị của các ô trước. 2. Tra bảng và xác định kết quả của bài toán ban đầu Phạm Thế Bảo Đánh giá Ưu điểm Chương trình thực thi nhanh do không tốn thời gian giải lại bài toán con. - Vận dụng để giải các bài toán tối ưu có công thức truy hoi Nhược điểm - Không tìm được công thức truy hồi. - Số lượng bài toán con cần giải và lưu trữ kết quả rất lớn. - Việc kết hợp lời giải của các bài toán con chưa chắc cho lời giải của bài toán ban đầu. Phạm Thế Bảo 2 14 04 2008 r l A J r A . Ẳ 1 Bài toán tính sô tô hợp Tính Cnk bằng công thức truy hồi. k 0 nếu k 0 hay k n n I Cnk-Ỉ Ct nếu 0 k n n-1 n 1 Thuật giải long Comb int n int k Phạm Thế Bảo Đánh giá Gọi T n là thời gian tính Cnk ta có T 1 C1 và T n giải ta có T n O - bài toán con được giải nhiều lần Comb 4 2 Comb 3 1 Comb 2 0 Comb 2 1 Comb 3 2 Comb 2 1 Comb 2 2 Phạm Thế Bảo
TÀI LIỆU LIÊN QUAN
Bài giảng Thiết kế và đánh giá thuật toán: Phân tích thuật toán - TS. Lê Nguyên Khôi
Bài giảng Thiết kế và đánh giá thuật toán: Phân tích đệ quy - TS. Lê Nguyên Khôi
Bài giảng Phân tích và thiết kế thuật toán: Bài toán quy hoạch động (Dynamic Programming) - Phạm Thế Bảo
Bài giảng Phân tích và thiết kế thuật toán
Bài giảng Phân tích và thiết kế thuật toán: Kỹ thuật Greedy (Tham lam) - Phạm Thế Bảo
Bài giảng Phân tích và thiết kế thuật toán: Các phương pháp giải quyết bài toán trên máy tính - Phạm Thế Bảo
Bài giảng Phân tích và thiết kế thuật toán: Tìm kiếm cục bộ (Local search) - Phạm Thế Bảo
Bài giảng Phân tích và thiết kế thuật toán: Tổng quan về thuật toán - Phạm Thế Bảo
Bài giảng Phân tích và thiết kế thuật toán: Đánh giá bằng công cụ toán học cơ bản - Phạm Thế Bảo
Bài giảng Phân tích và thiết kế thuật toán: Chia để trị - Phạm Thế Bảo
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.