intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Lập trình động

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:69

Thêm vào BST
Báo xấu
51
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

"Bài giảng Lập trình động" tìm hiểu về quy hoạch động; đặc điểm của phương pháp chia để trị; một chiến lược tối ưu có đặc trưng; chuỗi con đơn điệu dài nhất. Mời các bạn cùng tham khảo bài giảng để nắm chi tiết nội dung kiến thức.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Lập trình động

  1. Dynamic Programming
  2. Introduction Quy hoạch động:  Thường dùng để giải các bài toán tối ưu;  Phân rã bài toán thành các bài toán con; hình thành lời giải từ các bài toán con;  Lưu trữ lời giải các bài toán con trong một bảng dữ liệu thay cho giải lại các bài toán con (đệ quy). Đặc điểm của phương pháp chia để trị: •Thường phát sinh các bài toán con “mới” •Lời giải các bài toán con thường được sử dụng nhiều lần (“phủ chồng”). 2013-09-22 Dao Thanh Tinh 2
  3. Introduction (2) Ví dụ 1: Tính số Fibonacci thứ n Đệ quy: với f0=0 và f1 = 1 long f(int m) { if (n==0) return 0; Theo công thức: else if (n==1) return 1; n n 1 5  1 5  else return f(n-1) + f(n);      }  2   2  fn      Ví dụ, để tính f(n) phải tính f(2) n-1 lần! 5 Tiết kiệm bộ nhớ: Dùng mảng: f0 = 0; f1=1; f[0] = 0; f[1]=1; for (i=2; in;i++) for (i=2; in;i++) { tg = f1 + f0; f[i] = f[i-1] + f[i-2]; f0 = f1; output f[n]; f1 = tg; } output f1; 2013-09-22 Dao Thanh Tinh 3
  4. Introduction (3) Số Fibonacci thứ n n=50 F(n) =12,586,269,025 Phương pháp đệ quy 650 800s Các phương pháp khác 1s 2013-09-22 Dao Thanh Tinh 4
  5. Introduction (4) Tiếp cận theo hướng bottom-up 1. Xuất phát từ những bài toán cơ sở có lời giải (cách giải đơn giản hoặc có sẵn) 2. Từ tập lời giải các bài toán con tìm lời giải của bài toán lớn hơn. 2013-09-22 Dao Thanh Tinh 5
  6. Introduction (5) PRINCIPLE OF OPTIMALITY “An optimal policy has the property that whatever the initial state and initial decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decisions.” Richard Bellman “The Theory of Dynamic Programming”, Bulletin of the American Mathematical Society, Vol. 60, No. 6, 1954 (503-515). 2013-09-22 Dao Thanh Tinh 6
  7. Introduction (6) Một chiến lược tối ưu có đặc trưng: với mọi trạng thái khởi tạo và quyết định ban đầu, các quyết định tiếp theo phải thiết lập được chiến lược tối ưu đối với trạng thái được hình thành từ các quyết định trước đó. Chiến lược tối ưu: có thể trong một số bước đầu tiên lựa chọn dường như không tốt nhưng tổng hợp cả quá trình phải tốt nhất. 2013-09-22 Dao Thanh Tinh 7
  8. Introduction (7) Kỹ thuật giải bài toán bằng phương pháp QHĐ: a) Bắt đầu với những trường hợp con nhỏ nhất (thường là đơn giải nhất và giải được ngay). b) Tổ hợp các kết quả đã có (không phải tính lại) của các trường hợp con, sẽ đạt đạt tới kết quả của trường hợp có kích thước lớn và tổng quát hơn, cho đến khi cuối cùng đạt tới lời giải của bài toán ban đầu. 2013-09-22 Dao Thanh Tinh 8
  9. Introduction (8) Ví dụ 2: Xét bài toán: Cho túi T có sức chứa 10kg và 3 đồ vật: 1) 5kg, trị giá 4$ 2) 4kg, trị giá 10$ 3) 6kg, trị giá 3$ Xếp những đồ vật nào vào túi để có giá trị lớn nhất? 2013-09-22 Dao Thanh Tinh 9
  10. Introduction (9) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0!!!! đv 0 1 2 3 4 5 6 7 8 9 10 Giá trị lớn nhất 0 0 0 0 0 0 0 0 0 0 0 0 của túi: 2013-09-22 Dao Thanh Tinh 10
  11. Introduction (10) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 Giá trị lớn nhất 1 0 0 0 0 0 4 4 4 4 4 4 của túi: 2013-09-22 Dao Thanh Tinh 11
  12. Introduction (11) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 4 4 4 4 4 4 Giá trị lớn nhất của túi: 2 0 0 0 0 10 10 10 10 10 14 14 2013-09-22 Dao Thanh Tinh 12
  13. Introduction (12) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 4 4 4 4 4 4 2 0 0 0 0 10 10 10 10 10 14 14 Giá trị lớn nhất của túi: 3 0 0 0 0 10 10 10 10 10 14 14 2013-09-22 Dao Thanh Tinh 13
  14. Introduction (12) Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 4 4 4 4 4 4 2 0 0 0 0 10 10 10 10 10 14 14 Giá trị lớn nhất của túi: 3 0 0 0 0 10 10 10 10 10 14 14 Lời giải: Xếp vật 1, 2; tổng trọng lượng đồ vật là 9, giá trị là 14. 2013-09-22 Dao Thanh Tinh 14
  15. Introduction (13) Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0!!!! đv 0 1 2 3 4 5 6 7 8 9 10 Giá trị lớn nhất 0 0 0 0 0 0 0 0 0 0 0 0 của túi: 2013-09-22 Dao Thanh Tinh 15
  16. Introduction (14) Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 Giá trị lớn nhất 1 0 0 0 0 0 0 5 5 5 5 5 của túi: 2013-09-22 Dao Thanh Tinh 16
  17. Introduction (15) Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 5 5 5 5 5 Giá trị lớn nhất của túi: 2 0 0 0 0 4 4 5 5 5 5 9 2013-09-22 Dao Thanh Tinh 17
  18. Introduction (16) Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 5 5 5 5 5 2 0 0 0 0 4 4 5 5 5 5 9 Giá trị lớn nhất của túi: 3 0 0 0 0 10 10 10 10 14 14 15 2013-09-22 Dao Thanh Tinh 18
  19. Introduction (17) Ví dụ 3: T = 10kg, a1={6kg, 5$}, a2={4kg, 4$}, a3={4kg, 10$} Túi có kích thước từ 0 đến 10, sử dụng đồ vật thứ 0,1,2,3 đv 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 5 5 5 5 5 2 0 0 0 0 4 4 5 5 5 5 9 Giá trị lớn nhất của túi: 3 0 0 0 0 10 10 10 10 14 14 15 Lời giải: Xếp vật 1, 3; tổng trọng lượng đồ vật là 10, giá trị là 15. 2013-09-22 Dao Thanh Tinh 19
  20. Introduction (18) Example 1. An Allocation Problem. Giả thiết x>0 là giá trị đầu tư ở thời điểm ban đầu. Chia x thành 2 phần: y0 và x-y 0 Khai thác: phần thứ nhất mang lại g(y), giá trị còn lại là ay, 0
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2