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 $F(x)$ trong đoạn $[l, r]$ thoả mãn: $F$ 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í $m_1$ và $m_2$ trong đoạn $[l, r]$ sao cho $l < m_1 < m_2 < r$. Rõ ràng cực trị có thể nằm ở 1 trong 3 phần:

  • $[l, m_1]$. Khi đó, ta biết chắc chắn $F(m_1) > F(m_2)$.

  • $[m_1, m_2]$. Ta không thể rút ra kết luận gì về $F(m_1)$ và $F(m_2)$.

  • $[m_2, R]$. Tương tự trường hợp đầu, ta biết chắc chắn $F(m_1) < F(m_2)$.

Ngược lại, bằng việc so sánh $F(m_1)$ và $F(m_2)$, ta có thể rút ra kết luận như sau:

  • Nếu $F(m_1) < F(m_2)$: Ta biết chắc chắn H nằm trong $[m_1, r]$.
  • $F(m_1) > F(m_2)$: Ta biết chắc chắn H nằm trong $[l, m_2]$.
  • $F(m_1) = F(m_2)$: H nằm trong $[m_1, m_2]$. (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 $F$ ở hai điểm m1, m2 ta có thể thay đổi và giảm không gian tìm kiếm $[l, r]$ xuống một khoản không gian nhỏ hơn $[l', r']$. Nếu ta chọn:

  • $m_1 = l + (r - l) / 3$
  • $m_2 = r - (r - l) / 3$

Thì sau mỗi lần, độ lớn của đoạn $[l, r]$ giảm xuống còn $2/3$ 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 $(2 / 3) ^ K$. Ví dụ với $l = -10^9, r = 10^9$, ta lặp lại $K = 100$ lần, thì đoạn [l, r] thu về chỉ còn độ dài là $(2 / 3.0) ^ {100} * (2*10^9) < 5 * 10^{-9}$, đủ 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à $O(logT)$ 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 $f(x, y)$ 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.

Bài tập tự luyện