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
THUẬT TOÁN ỨNG DỤNG
QUY HOẠCH ĐỘNG
Range Minimum Query
Phạm Quang Dũng
Bộ môn KHMT
1
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].
0 1 2 3 4 5 6 7 8 9 10 11 12
2 4 6 1 6 8 7 3 3 5 8 9 1
RMQ(1,7) = 3
RMQ(6,11) = 7
2
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).
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
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
0
3
3
1
1
3
3
2
3
4
5
6
7
8
9
10 11 12 13 14 15
0
1
2
3
4
3
3
3
-
3
3
3
-
4
7
8
-
6
8
7
8
8
8
8
8
9
10 12 12 13 15 -
12 12 12 12 -
-
-
-
-
-
-
12 12 12 12 -
-
-
-
-
-
-
-
-
12 -
-
-
-
-
-
3
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
i+2j-1 -1
i + 2j-1
i
i + 2j - 1
M[j-1,i + 2j-1]
M[j-1,i]
4
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
M[3,7] = 12
a[7] > a[12] RMQ(4,14) = 12
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4
6
M[3,4] = 7
6 trang
14640
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 3: 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_phan_3_quy_hoach_dong.pdf
