Thuật toán Chặt tam phân (Ternary Search): Lý thuyết, ứng dụng và cài đặt trong C++

Từ khóa chính: thuật toán chặt tam phân, ternary search, cực trị, tối ưu hàm, C++, tìm giá trị nhỏ nhất, bài toán liên tục

🔗 Xem thêm:
Ternary Search – Wikipedia
Tìm cực trị bằng nhị phân
Thuật toán tối ưu hóa

Mục lục

1. Thuật toán chặt tam phân là gì?

Chặt tam phân (Ternary Search) là một kỹ thuật tối ưu hóa dùng để tìm cực trị (cực tiểu hoặc cực đại) của một hàm đơn điệu hoặc unimodal trong một khoảng giá trị liên tục hoặc rời rạc. Cơ chế hoạt động của nó dựa trên việc chia đoạn đang xét thành 3 phần thay vì 2 như trong chặt nhị phân, sau đó loại bỏ 1/3 không cần thiết.

1.1 Bài toán mẫu

Cho hàm số \(f(x)\) xác định trên đoạn \([L, R]\), tìm giá trị \(x\) trong đoạn sao cho \(f(x)\) đạt giá trị nhỏ nhất (hoặc lớn nhất) khi biết rằng hàm số chỉ có một cực trị (có dạng hình chữ U hoặc ngược lại).

2. Khi nào nên dùng chặt tam phân?

Hàm số đơn điệu hoặc unimodal.
Không có công thức đạo hàm rõ ràng.
Cần tìm giá trị cực trị với sai số chấp nhận được (thường dùng với số thực).

2.1 So sánh với chặt nhị phân

Tiêu chí	Chặt nhị phân	Chặt tam phân
Mục tiêu	Tìm phần tử	Tìm cực trị
Yêu cầu hàm số	Đơn điệu tăng/giảm	Unimodal
Độ chính xác	Chính xác tuyệt đối	Cần điều chỉnh sai số

3. Ý tưởng thuật toán

Giả sử cần tìm cực trị trong đoạn \([L, R]\). Tại mỗi bước, chọn hai điểm:

\(mid1 = L + (R-L)/3\)
\(mid2 = R – (R-L)/3\)

So sánh giá trị hàm tại \(mid1\) và \(mid2\), loại bỏ đoạn không chứa cực trị, và lặp lại.

4. Cài đặt thuật toán chặt tam phân với số thực

Giải bài toán: Tìm giá trị nhỏ nhất của hàm \(f(x) = (x-2)^2 + 3\) trên đoạn [0, 4]

4.1 Mã C++

double f(double x) {
    return (x - 2)*(x - 2) + 3;
}

double ternary_search(double l, double r) {
    double eps = 1e-7;
    while (r - l > eps) {
        double mid1 = l + (r - l) / 3;
        double mid2 = r - (r - l) / 3;
        if (f(mid1) < f(mid2))
            r = mid2;
        else
            l = mid1;
    }
    return (l + r) / 2;
}

4.2 Phân tích độ phức tạp

Độ phức tạp: O(log(R-L)/eps) với sai số epsilon.

5. Chặt tam phân với số nguyên

Chặt tam phân cũng áp dụng cho số nguyên nhưng cần thêm điều kiện dừng.

5.1 Ví dụ minh họa

int f(int x) {
    return (x - 5)*(x - 5) + 1;
}

int ternary_search_int(int l, int r) {
    while (r - l > 3) {
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;
        if (f(mid1) < f(mid2))
            r = mid2;
        else
            l = mid1;
    }
    int res = f(l);
    for (int i = l+1; i <= r; ++i) res = min(res, f(i));
    return res;
}

6. Lưu ý khi dùng ternary search

Chỉ dùng khi hàm có một cực trị.
Không áp dụng cho bài toán có nhiều cực trị.
Với số thực, phải chọn epsilon hợp lý để tránh lặp vô hạn.

7. Ứng dụng thực tế

Tối ưu hóa hàm liên tục trong học máy và AI.
Bài toán mô phỏng vật lý: điểm va chạm, điểm dừng lý tưởng.
Tìm giá trị nhỏ nhất của tổng chi phí, thời gian hoặc năng lượng.

8. Tổng kết

Thuật toán chặt tam phân là một công cụ hiệu quả để giải quyết các bài toán tối ưu hóa một biến với chi phí tính toán thấp. Việc hiểu và vận dụng đúng điều kiện áp dụng là chìa khóa thành công trong các cuộc thi lập trình cũng như ứng dụng thực tế.