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

Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn THUẬT TOÁN ỨNG DỤNG 1 QUY HOẠCH ĐỘ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: S(0, j) = 0   i = 0,1,, n: 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