Bài giảng Thuật toán ứng dụng - Chương 5, Phần 1: Quy hoạch động - Phạm Quang Dũng
NộI dung
Tổng quan chia để trị
Dã y con cực đại
Dã y con tăng dần dài nhất
2
Quy hoạch động
Sơ đồ chung
Chia bài toá n xuất phá t thành cá c bài toá n con khô ng
nhất thiết độc lập với nhau
Giải cá c bài toá n con từ nhỏ đến lớn, lời giải được lưu trữ
lại vào 1 bảng
Bài toá n con nhỏ nhất phải được giải 1 cá ch trực tiếp
Xâ y dựng lời giải của bài toá n lớn hơn từ lời giải đã có
của cá c bài toá n con nhỏ hơn (truy hồi)
Số lượng bài toá n con cần được bị chặn bởi đa thức của kí ch
thước dữ liệu đầu vào
Phù hợp để giải hiệu quả một số bài toá n tối ưu tổ hợp
3
Bài toá n dã y con cực đại
Cho dã y số nguyên a = a1, a2,…, aN. Hã y tì m dã y con
bao gồm cá c phần tử liên tiếp của dã y a có tổng lớn
nhất
4
Bài toá n dã y con cực đại
Phâ n chia
Ký hiệu Pi là bài toá n tì m dã y con bao gồm cá c phần tử
liên tiếp có tổng cực đại mà phần tử cuối cùng là ai, với
mọi i = 1,…, n
Ký hiệu Si là tổng cá c phần tử của lời giải của Pi, i =
1,…, n
S1 = a1
Si =
Si -1 + ai, nếu Si-1 > 0
ai, nếu Si-1 0
Tổng cá c phần tử của dã y con cực đại của bài toá n xuất
phá t là
max{S1, S2, …, Sn}
5
Bài toá n dã y con cực đại
maxsubseq(a1,a2,. . ., aN){
s[1] = a[1];
res = s[1];
for i = 2 → N do{
if s[i-1] > 0 then {
s[i] = s[i-1] + a[i];
}else{
s[i] = a[i];
}
if s[i] > res then res = s[i];
}
return res;
}
6
Bài toá n dã y con tăng dần dài nhất
Cho dã y số nguyên a = a1, a2,…, aN. Hã y tì m dã y con
tăng dần bao gồm cá c phần tử khô ng nhất thiết liên
tiếp nhau của dã y a có số phần tử lớn nhất
7
Bài toá n dã y con tăng dần dài nhất
Ký hiệu Pi là bài toá n tì m dã y con cực đại mà phần tử
cuối cùng là ai, với mọi i = 1,…, n
Ký hiệu Si là số phần tử của lời giải của Pi, i = 1,…, n
S1 = 1
Si = max{1, max{Sj +1| j < i aj < ai }}
Số phần tử của dã y con cực đại của bài toá n xuất phá t
là
max{S1, S2, …, Sn}
8
Bài toá n dã y con tăng dần dài nhất
incsubseq(a1,a2,. . ., aN){
s[1] = 1;
res = s[1];
for i = 2 → N do{
s[i] = 1;
for j = 1 → i-1 do{
if a[j] < a[i] then{
if s[i] < s[j] + 1 then{
s[i] = s[j] + 1;
}
}
}
if s[i] > res then res = s[i];
}
return res;
}
9
Dã y con chung dài nhất
Ký hiệu X = X1, X2, …, Xn, một dã y con của X là dã y
được tạo ra bằng việc loại bỏ 1 số phần tử nào đó của
X đi
Đầu vào
Cho 2 dã y X = X1, X2, …, Xn và Y = Y1, Y2, …, Ym
Đầu ra
Tì m dã y con chung của X và Y có độ dài lớn nhất
10
Dã y con chung dài nhất
Phâ n rã
Ký hiệu S(i, j) là độ dài dã y con chung dài nhất của dã y X1, …, Xi
và Y1, …, Yj, với i = 1, …, n và j = 1, …, m
Bài toá n con nhỏ nhất
j = 0,1,…, m:
i = 0,1,…, n:
S(0, j) = 0
S(i, 0) = 0
Tổng hợp lời giải, với i = 1,...,n và j = 1,...,m
S(i, j) =
S(i-1, j-1) + 1, nếu Xi = Yj
max{S(i-1, j), S(i, j-1)}
11
Dã y con chung dài nhất
lcs([X1,…,Xn], [Y1,…,Ym]){
for i = 0 → n do S[i][0] = 0;
for j = 0 → m do S[0][j] = 0;
for i = 1 → n do{
for j = 1 → m do{
if Xi = Yj then{
S[i][j] = S[i-1][j-1] + 1;
}else{
if S[i-1][j] > S[i][j-1] then{
S[i][j] = S[i-1][j];
}else{
S[i][j] = S[i][j-1];
}
}
}
}
return S[n][m];
}
12
Truy vết
Mỗi bước xâ y dựng lời giải của một bài toá n con từ lời
giải của cá c bài toá n con nhỏ hơn ta thường quyết
định lựa chọn giữa cá c phương á n
→ ghi nhớ quyết định lựa chọn đó vào cấu trúc dữ liệu
để truy vết và dẫn ra lời giải đầy đủ cho bài toá n ban đầu
13
Truy vết
Bài toá n dã y con cực đại
start[i]: chỉ số của phần tử đầu tiên của lời giải bài toá n
con Pi
select: chỉ số của bài toá n con mà lời giải của bài toá n
con đó là lời giải của bài toá n xuất phá t
14
Truy vết
maxsubseq(a1,a2,. . ., aN){
s[1] = a[1]; start[1] = 1;
res = s[1]; select = 1;
for i = 2 → N do{
if s[i-1] > 0 then {
s[i] = s[i-1] + a[i]; start[i] = start[i-1];
}else{
s[i] = a[i]; start[i] = i;
}
if s[i] > res then{
res = s[i]; select = i;
}
}
output(‘day con tu ’, start[select], ‘ den ’, select);
return res;
}
15
Truy vết
Bài toá n dã y con tăng dần dài nhất
prev[i]: chỉ số của phần tử trước phần tử a[i] trong lời giải
của bài toá n con Pi.
select: chỉ số của bài toá n con mà lời giải của bài toá n
con đó là lời giải của bài toá n xuất phá t
16
Truy vết
incsubseq(a1,a2,. . ., aN){
s[1] = 1; prev[1] = -1;
res = s[1]; select = 1;
for i = 2 → N do{
s[i] = 1; prev[i] = -1;
for j = 1 → i-1 do{
if a[j] < a[i] and s[i] < s[j] + 1 then{
s[i] = s[j] + 1; prev[i] = j;
}
}
if s[i] > res then {res = s[i]; select = i;}
}
i = select;
while(i > -1){ output(i); i = prev[i]; }
return res;
}
17
Truy vết
Bài toá n dã y con chung dài nhất
nếu S[i][j] = S[i-1][j-1] + 1 thì a[i][j] = ‘c’ (đi ché o)
Ngược lại
Nếu S[i-1][j] > S[i][j-1] thì a[i][j] = ‘u’; (đi lên)
Ngược lại a[i][j] = ‘l’ (đi sang trá i)
18
Truy vết
lcs([X1,…,Xn], [Y1,…,Ym]){
for i = 0 → n do S[i][0] = 0;
for j = 0 → m do S[0][j] = 0;
for i = 1 → n do{
for j = 1 → m do{
if Xi = Yj then{
S[i][j] = S[i-1][j-1] + 1; end_i = i; end_j = j; a[i][j] = ‘c’;
}else{
if S[i-1][j] > S[i][j-1] then{
S[i][j] = S[i-1][j]; a[i][j] = ‘u’;
}else{
S[i][j] = S[i][j-1]; a[i][j] = ‘l’;
}
}
}
}
return S[n][m];
19
}
Truy vết
trace(end_i, end_j, a){
i = end_i; j = end_j;
while(true){
if(a[i][j] == 'c’){
output(i,j);
i = i-1; j = j-1;
}else if(a[i][j] == 'u'){
i = i-1;
}else{
j = j-1;
}
if(i == 0 || j == 0) break;
}
}
20
20 trang
10920
Free
Bạn đang xem tài liệu "Bài giảng Thuật toán ứng dụng - Chương 5, Phần 1: Quy hoạch động - Phạm Quang Dũng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_thuat_toan_ung_dung_chuong_5_quy_hoach_dong_pham_q.pdf
