Bài giảng Thuật toán ứng dụng - Chương 5, Phần 3: 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 Range Minimum Query Bài toán Range Minimum Query RMQ  Cho dãy a[0], a[1], , a[N-1]. Với mỗi bộ chỉ số 0 ≤ i < j ≤ N -1, hãy thực hiện truy vấn RMQ(i, j) tìm và trả về chỉ số của phần tử nhỏ nhất trong dãy con a[i], a[i+1],, a[j]. 2 2 4 6 1 6 8 7 3 3 5 8 9 1 0 1 2 3 4 5 6 7 8 9 10 11 12 RMQ(1,7) = 3 RMQ(6,11) = 7 Bài toán Range Minimum Query RMQ  Ký hiệu M[j, i] là chỉ số phần tử nhỏ nhất của dãy a[i], a[i+2],, a[i+2j -1] (dãy bắt đầu từ chỉ số i và có độ dài là 2j). 3 2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 3 3 4 6 7 8 8 9 10 12 12 13 15 - 3 3 3 3 7 8 8 8 8 12 12 12 12 - - - 3 3 3 3 8 12 12 12 12 - - - - - - - 12 - - - - - - - - - - - - - - - 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 Bài toán Range Minimum Query RMQ  Bài toán con nhỏ nhất M[0,i] = i, i = 0,, N-1  Công thức truy hồi  M[j,i] = M[j-1,i] nếu a[M[j-1,i]] < a[M[j-1,i+2j-1] M[j-1,i+2j-1], ngược lại 4 i i+2j-1 -1 i + 2j-1 i + 2j - 1 M[j-1,i] M[j-1,i + 2j-1] M[j, i] Bài toán Range Minimum Query RMQ preprocessing(){ for (i = 0; i < N; i++) M[0,i] = i; for (j = 0; 2j ≤ N; j++){ for(i = 0; i + 2j -1 < N; i++){ if a[M[j-1,i]] < a[M[j-1,i+2j-1]] then{ M[j,i] = M[j-1,i]; }else{ M[j,i] = M[j-1,i+2j-1]; } } } } 5 Bài toán Range Minimum Query RMQ  Truy vấn RMQ(i,j)  k = [log(j-i+1)]  RMQ(i,j) = M[k,i] nếu a[M[k,i]] ≤ a[M[k, j-2k+1]] M[k, j-2k+1]], ngược lại  RMQ(4,14) = ?  k = [log(14-4+1)]=3  a[7] > a[12]  RMQ(4,14) = 12 6 2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 M[3,4] = 7 M[3,7] = 12