¶ Tìm kiếm tam phân - Ternary Search
Nguồn: e-maxx
Người dịch: Đỗ Thanh Lam
¶ Mở đầu
Cho một hàm F(x) chỉ có một cực trị duy nhất (unimodal). Có hai dạng hàm F(x) cơ bản:
- Phần đầu tăng chặt, đạt đến giá trị lớn nhất, sau đó giảm chặt. (concave)
Một hàm số thoả mãn tính chất này nếu tất cả các đoạn thẳng nối 2 điểm của đồ thị hàm số, nằm "bên dưới" của đồ thị.
- Phần đầu giảm chặt, đạt đến giá trị nhỏ nhất, sau đó tăng chặt. (convex)
Một hàm số thoả mãn tính chất này nếu tất cả các đoạn thẳng nối 2 điểm của đồ thị hàm số, đều nằm "bên trên" của đồ thị.
Trong bài viết này chúng tôi sẽ giải quyết trường hợp 1, trường hợp 2 sẽ làm tương tự nhưng ngược lại.
¶ Bài toán
Cho một hàm trong đoạn thoả mãn: tăng chặt tới một cực đại (điểm H) rồi giảm chặt. Yêu cầu tìm điểm đạt giá trị lớn nhất (điểm H).
¶ Thuật toán
Xét hai vị trí và trong đoạn sao cho . Rõ ràng cực trị có thể nằm ở 1 trong 3 phần:
- . Khi đó, ta biết chắc chắn .
- . Ta không thể rút ra kết luận gì về và .
- . Tương tự trường hợp đầu, ta biết chắc chắn .
Ngược lại, bằng việc so sánh và , ta có thể rút ra kết luận như sau:
- Nếu : Ta biết chắc chắn H nằm trong .
- : Ta biết chắc chắn H nằm trong .
- : H nằm trong . (Chú ý: khi cài đặt chặt tam phân với hàm số thực, ta thường bỏ qua trường hợp này, để tránh sai số, và do trên thực tế 2 số thực hầu như không bao giờ bằng nhau).
Do đó, dựa vào việc so sánh ở hai điểm m1, m2 ta có thể thay đổi và giảm không gian tìm kiếm xuống một khoản không gian nhỏ hơn . Nếu ta chọn:
Thì sau mỗi lần, độ lớn của đoạn giảm xuống còn lần.
Nếu ta lặp đi lặp lại K lần, thì độ lớn của [l, r] sẽ chỉ còn . Ví dụ với , ta lặp lại lần, thì đoạn [l, r] thu về chỉ còn độ dài là , đủ chính xác với hầu hết mọi bài toán.
Độ phức tạp thuật toán là với T là độ chính xác mà ta cần thực hiện.
¶ Cài đặt
double max_f(double left, double right) {
int N_ITER = 100;
for (int i = 0; i < N_ITER; i++) {
double x1 = left + (right - left) / 3.0;
double x2 = right - (right - left) / 3.0;
if (f(x1) > f(x2)) right = x2;
else left = x1;
}
return f(left);
}
¶ Mở rộng
Tìm kiếm tam phân cũng có thể dùng để giải các bài toán trên 2D với hàm dạng nếu hàm f là hàm lồi. Ví dụ bài E trong đề ACM ICPC Vietnam National Round 2017, lời giải chi tiết ở đây.