[USACO][VOJ] GROUP
Trung
cặp số lại thành một nhóm. Giả sử một nhóm gồm các cặp số thứ a1,
a2, ..., am thì chi phí cho nhóm này sẽ là max(xa1, xa2, ..., xam) *
max(ya1, ya2, ..., yam).
Yêu cầu: tìm cách phân nhóm có tổng chi phí bé nhất.
Solution:
Brucker’s algorithm:
Thuật toán Brucker được sử dụng để tăng tốc thuật toán quy hoạch động
đối với các bài toán quy hoạch động có dạng:
- Cần tính một hàm F(i), i = 1..N
- F(i) = min{F(j) + c(i,j)}
- Định lý:
o Đặt Fi(j) = F(j) + c(i,j)
=> F(i) = min{Fi(j)}
o Nếu ta có thể tìm được 2 hàm g và f thỏa mãn:
f(i) ≥ f(i+1) với i = 1..N-1
và Fi(j) ≤ Fi(k) ↔ g(j,k) ≤ f(i)
Thì ta có thể áp dụng thuật toán Brucker
- Thuật toán Brucker:
o Ta tìm cách tính các F(i) với i chạy từ N về 1.
o Duy trì một queue 2 đầu lưu lại các giá trị j theo thứ tự tăng dần
có thể dùng để cập nhật F(i). Ta cố gắng loại bỏ các phần tử chắc chắn
không thể cập nhật cho F(i).
o Có thể chứng minh được:
+ nếu g(j,k) ≤ f(i), với i < j < k thì Fi’(j) ≤ Fi’(k) với mọi i’≤ i.
Điều này có nghĩa là, nếu g(j,k) ≤ f(i) thì ta có thể loại bỏ k khỏi
queue ở bước tính F(i)
+ nếu g(j,k) ≤ g(k,l), với j < k < l thì j hoặc l luôn tối ưu hơn k.
Nói cách khác, ta có thể loại bỏ k khỏi queue.
o Như vậy, ta thu được thuật toán:
Ta sử dụng queue 2 đầu Q để lưu j, với Q[0] là front, và Q[Q.size] là
back
Pseudo code:
F(n) = 0;
Q.push_back(n);
for i=n-1 downto 1
while Q.size>1 && g(Q[1],Q[0]) ≤ f(i)
Q.pop_front;
F(i) = Fi(Q[0]);
while Q.size>1 &&
g(i,Q[Q.size]) ≤ g(Q[Q.size],Q[Q.size-1]))
Q.pop_back
Q.push_back(i);
Tóm lại, theo thuật toán Brucker, ta cần tìm 2 hàm f và g thỏa mãn:
- f là hàm giảm
- g là hàm số thỏa mãn: Fi(j) ≤ Fi(k) ↔ g(j,k) ≤ f(i)
Nếu tìm được 2 hàm này, ta có thể áp dụng thuật toán Brucker để giải
quyết bài toán.
Quay trở lại bài toán:
Nhận xét 1:
- Nếu tồn tại i và j thỏa mãn: xi ≤ xj và yi ≤ yj thì ta có thể loại
bỏ cặp số (xi,yi) mà không làm thay đổi kết quả bài toán
Từ nhận xét trên, nếu ta sort tất cả các cặp số tăng theo xi, thì
trong dãy đã sắp xếp, yi giảm dần.
Nhận xét 2:
- Trên dãy đã sắp xếp, nếu ta chọn cặp (xi,yi) và cặp (xk,yk) thì ta
có thể chọn mọi cặp (xj, yj) với i < j < k vào cùng nhóm với (xi,yi)
và (xk,yk) mà không làm giảm độ tốt của các chọn. (vì xj < xk và yj ≤
yi)
Gọi F(i) = chi phí nhỏ nhất để phân nhóm các cặp số i..N
=> F(i) = min{F(j+1) + x(j)*y(i)}
Đặt Fi(j) = F(j+1) + x(j)*y(i)
Ta có:
Fi(j) ≤ Fi(k)
↔ F(j+1) + x(j)*y(i) ≤ F(k+1) + x(k)*y(i)
↔ F(j+1) – F(k+1) ≤ y(i) * (x(k) – x(j))
Ta chọn
g(j,k) = ( F(j+1) – F(k+1) ) / ( x(k) – x(j) )
f(i) = y(i)
Dễ thấy, hàm g và f thỏa mãn các điều kiện rằng buộc của thuật toán
Brucker.
Như vậy, bài toán có thể giải được bằng thuật toán Brucker.