YOMEDIA
Chuyên đề Quy hoạch động - Nguyễn Duy Dũng
Chia sẻ: Nguyen Tien Nhan
| Ngày:
| Loại File: PDF
| Số trang:16
181
lượt xem
36
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
Bài toán lớn có thể phân rã thành những bài toán con đồng dạng, những bài toán con đó có thể phân rã thành những bài toán nhỏ hơn nữa. Lời giải tối ưu của các bài toán con có thể sử dụng để tìm ra lời giải tối ưu của bài toán lớn.
AMBIENT/
Chủ đề:
Nội dung Text: Chuyên đề Quy hoạch động - Nguyễn Duy Dũng
- ề
Ạ Ộ
Trường THPT Chuyên Hà Tĩnh
ả Ễ
0913141823
Dungduyit83@gmail.com
ơ ị
Dungduyit83
ố
- Ạ Ộ
ể ị ạ ộ
ế ế ậ ậ ể ử
ạ
ự ấ ữ ệ
3
- Ạ Ộ
ấ ủ ố ư ể ả ằ ạ ộ
Bài toán lớn có thể phân rã thành những bài toán con đồng dạng, những bài
toán con đó có thể phân rã thành những bài toán nhỏ hơn nữa …(recursive
form).
Lời giải tối ưu của các bài toán con có thể sử dụng để tìm ra lời giải tối ưu
của bài toán lớn (optimal substructure)
Hai bài toán con trong quá trình phân rã có thể có chung một số bài toán
con khác (overlapping subproblems).
Có thể hiểu
Hai tính chất đầu tiên Có thể giải bằng chia để trị và đệ quy
Tính chất thứ ba Đặc trưng cho tính hiệu quả của quy hoạch động
4
- Ệ
Bài toán giải theo phương pháp quy hoạch động gọi là
bài toán quy hoạch động.
Công thức phối hợp nghiệm của các bài toán con để có
nghiệm của bài toán lớn gọi là công thức truy hồi của
quy hoạch động.
Tập các bài toán nhỏ nhất có ngay lời giải để từ đó giải
quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động.
Không gian luu trữ lời giải các bài toán con để tìm cách
phối hợp chúng gọi là bảng phương án của quy hoạch
động.
5
- ƯỚ Ả Ạ Ộ
Giải tất cả các bài toán cơ sở (thông thường rất dễ),
luu các lời giải vào bảng phương án.
Dùng công thức truy hồi phối hợp những lời giải của
những bài toán nhỏ đã lưu trong bảngphương án để
tìm lời giải của những bài toán lớn hơn và lưu chúng
vào bảng phuong án, chotới khi bài toán ban đầu tìm
được lời giải.
Dựa vào bảng phương án, truy vết tìm ra nghiệm tối
ưu.
6
- Nhập vào dãy số nguyên
A=(a1,a2 …an). n≤106, |ai |≤ 109
ộ ạ ồ ầ ử ế
Dòng 1: chứa số nguyên dương N
ổ ớ ấ
-
Dòng 2: chứa N số nguyên của dãy A
ữ ệ
-
- Ghi 1 giá trị duy nhất là tổng lớn nhất tìm được
ữ ệ
ươ
7
- ậ ầ
ậ
ọ ổ ầ ử ừ ớ
ơ ở ầ ử
ứ
ế ả
8
- ậ
ọ ổ ầ ử ừ ớ
ơ ở ỗ
ứ
ọ ị ỏ ấ ừ ớ
ế ả
9
- Nhập vào dãy số nguyên
A=(a1,a2 …an). n≤106, |ai |≤ 109
Nối a1 vào sau an ta được 1 vòng tròn số
ộ ạ ồ ầ ử ế
Dòng 1: chứa số nguyên dương N
ố ổ ớ ấ
-
Dòng 2: chứa N số nguyên của dãy A
ữ ệ
-
- Ghi 1 giá trị duy nhất là tổng lớn nhất tìm được
ữ ệ
ươ
10
- Ấ
Nhập vào dãy số nguyên
A=(a1,a2 …an). n≤103, |ai |≤ 109
Tìm dãy chỉ số = ( 1, 2, ... , ) dài nhất
1 1 < 2 < ... <
[ ] < [ ] < ... < [ ]
Ví dụ = (1, 2, 3, 8, 9, 4, 5, 6, 2, 3, 9, 10)
11
- Ấ
Thêm 2 phần tử a0 = - ; an+1 = +
Dãy con đơn điệu tăng dài nhất ắ ắ bắt đầu ở a0 và kết thúc ở an+1
Tổng quát hóa Làm thế nào xác định dãy con đơn điệu tăng dài nhất kết thúc tại ai?
Kiểm tra 3 tính chất của bài toán QHĐ
Dãy con tăng kết thúc tại ai được thành lập bằng cách lấy ai ghép vào sau một
dãy con tăng kết thúc tại aj nào đó đứng trước ai
Nếu xác định được ất cả các dãy con tăng dài nhất đứng trước ai thì có thể xác
định được dãy con tăng dài nhất kết thúc tại ai
aj a ai 12
- Ấ
ơ ở
ứ ồ
ế ư ầ ử ứ ề ướ
ấ
0 1 2 3 4 5 6 7 8 9
A - 11 22 66 33 44 99 55 77 +
ả
1 2 3
3 4 4 5 6 6 7 8 ả ế
0 1
1 2 2 4 5 5 7 8
13
- Ế
ể ế ổ ứ ố ế ị
ỗ ằ ổ ứ ộ ơ ướ ư
ẽ ộ ữ ậ ướ ượ ố ừ ế
ộ ượ ố ừ ế ố ượ ừ ố ướ ừ
ả ỗ ằ ủ ộ ượ ọ ộ ố
ươ ố ể ể ừ
ộ ộ ộ ả ặ ệ ộ
ầ ể ừ ộ ủ ộ ộ ấ
ế ộ ộ ộ ộ ổ ố ủ
ớ ấ ổ ố ượ ậ
ữ ệ ừ ả ầ ố ươ
ế ỗ ố ủ ữ
ậ
ế ả ả ồ
ứ ấ ổ ố ủ
ứ ố ỉ ố ừ ộ ế ộ
ụ
14
- Ế
ỹ ậ
ự ả ề
ớ
ế ầ ượ ế ả
15
- ả
ả ươ
16
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.98:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.98:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
