CTDL & giải thuật

Tìm kiếm tam phân trên hàm đơn đỉnh

Tìm kiếm tam phân không dùng cho mọi hàm số. Nó chỉ loại bỏ chắc chắn một phần miền khi giá trị giảm rồi tăng, hoặc tăng rồi giảm, trên miền đang xét.

Tam phân chỉ đúng khi hình dạng hàm cho phép

Ternary Search tìm cực trị trên miền có tính đơn đỉnh: với bài cực tiểu, hàm giảm ngặt rồi tăng ngặt, chỉ được phẳng ngay tại đáy; với bài cực đại thì ngược lại. Nếu có nhiều đáy tách rời, so hai điểm không cho biết chắc phần nào chứa nghiệm và thuật toán có thể loại nhầm đáp án. Một đoạn phẳng nằm ở sườn cũng gây lỗi tương tự: với dãy 5,4,4,4,4,4,4,1,2,3, phép so f(3) = f(6) = 4 khiến ta bỏ phần chứa đáy ở vị trí 7.

Ý chính

Trước khi viết vòng lặp, phải chứng minh hoặc nhận ra tính đơn đỉnh trên toàn miền đang xét. Ternary Search không phải cách thay thế Binary Search cho một hàm bất kỳ.

Ternary Search: f(x) = (x-1)² + (x-4)² + (x-7)² trên [-10, 10] Đáy x = 4 · f(4) = 18 Vòng 1: m1 = -4 (210), m2 = 4 (18) f(m1) > f(m2) → dịch biên trái l = -4 Vòng 2: m1 = 0 (66), m2 = 6 (30) f(m1) > f(m2) → dịch biên trái l = 0 Quét đoạn cuối → Cực tiểu x = 4 Giá trị nhỏ nhất f(4) = 18
Ternary Search: mốc 1, 4, 7 Vòng 1: [-10, 10] f(-4) = 210 > f(4) = 18 → l = -4 Vòng 2: [-4, 10] f(0) = 66 > f(6) = 30 → l = 0 Thêm 4 vòng → quét [2, 5] f(2)=30, f(3)=21, f(4)=18, f(5)=21 Cực tiểu: x = 4 · f(4) = 18
Hình 1. So sánh f(m1) và f(m2) để loại bỏ một phần ba miền trên hàm lồi f(x).

Quy tắc loại một phần ba

Trên đoạn số nguyên [l,r], đặt m1=l+(r-l)/3 và m2=r-(r-l)/3. Với hàm cực tiểu đơn đỉnh, nếu f(m1) <= f(m2) thì luôn còn một điểm đáy trong [l, m2], nên gán r=m2. Ngược lại (f(m1) > f(m2)), m1 đang ở sườn giảm nên đáy nằm bên phải m1, gán l=m1. Bất biến là ít nhất một điểm tối ưu vẫn ở trong đoạn mới.

Trực giác: ở phía giảm, điểm đi sang phải cho giá trị nhỏ hơn; ở phía tăng thì ngược lại. Quan hệ hai giá trị chỉ loại được một phía vì hình dạng hàm đã biết. Dấu bằng giữ được trường hợp đáy phẳng bằng cách không bỏ cả vùng giữa.

Trên số nguyên, khi r-l nhỏ, m1 hoặc m2 có thể trùng biên và vòng lặp ngừng co nếu cứ tiếp tục. Bản mẫu dừng khi còn tối đa bốn điểm, tính trực tiếp từng điểm và chọn cặp (giá trị,x) nhỏ nhất. Cách này cũng quy định rõ khi nhiều nghiệm cùng tốt: lấy x nhỏ nhất.

Ví dụ tổng bình phương

Cho các điểm 1,4,7, tối thiểu hóa f(x)=(x-1)^2+(x-4)^2+(x-7)^2 trên [-10,10]. Hàm lồi nên đơn đỉnh; nghiệm nguyên tốt nhất là 4 với giá trị 9+0+9=18. Code đọc n, l, r cùng dãy a rồi trả x f(x).

Tổng bình phương có thể giải bằng trung bình, nhưng nó là ví dụ nhỏ dễ tự kiểm. Trong bài thật, f có thể là chi phí hình học hoặc một mô phỏng O(n) không có công thức đóng. Khi đó tổng chi phí là số lần gọi f nhân chi phí một lần tính.

#include <iostream>
#include <vector>
using namespace std;using ll=long long;
pair<ll,ll> minimize(const vector<ll>&a,ll l,ll r){auto f=[&](ll x){ll s=0;for(ll v:a)s+=(x-v)*(x-v);return s;};while(r-l>3){ll m1=l+(r-l)/3,m2=r-(r-l)/3;if(f(m1)<=f(m2))r=m2;else l=m1;}pair<ll,ll>ans={l,f(l)};for(ll x=l+1;x<=r;++x)if(f(x)<ans.second)ans={x,f(x)};return ans;}
int main(){int n=3;ll l=-10,r=10;vector<ll>a={1,4,7};if(cin>>n>>l>>r){a.resize(n);for(auto&x:a)cin>>x;}auto[x,v]=minimize(a,l,r);cout<<x<<' '<<v<<'\n';}

Vòng thu hẹp cần O(log(r-l)) lần đánh giá theo cơ số hằng. Hàm mẫu tốn O(n), nên tổng O(n log phạm_vi); quét cuối là hằng số. Bộ nhớ phụ O(1) ngoài mảng đầu vào.

Miền số thực khác miền số nguyên

Với số thực, thường chạy số vòng cố định như 100–200 lần, đặt m1 và m2 bằng phép chia thực, rồi trả trung điểm. Không dùng điều kiện while r-l>3. Số vòng xác định sai số, nhưng còn phải xem f có ổn định số học và đề yêu cầu bao nhiêu chữ số.

Trên số nguyên, tuyệt đối không chuyển sang double nếu f dùng số nguyên lớn và cần so sánh chính xác. Bản C++ dùng long long; hợp đồng giới hạn để bình phương và tổng không tràn. Nếu tọa độ lớn hơn, phải dùng __int128 cho phép nhân.

Cẩn thận

Nếu f có nhiều cực tiểu cục bộ, Ternary Search có thể trả một điểm không tối ưu toàn cục dù vòng lặp và code hoàn toàn đúng cú pháp.

Khi Binary Search thích hợp hơn

Nếu có thể xét dấu đạo hàm hoặc hiệu rời rạc f(x+1)-f(x) và đại lượng đó đơn điệu, Binary Search tìm điểm đổi dấu thường cần ít lần gọi hàm hơn. Với hàm lồi rời rạc, tìm x nhỏ nhất sao cho f(x) <= f(x+1) (tức độ dốc f(x+1) - f(x) >= 0) là một lựa chọn. Ternary dễ viết khi chỉ có hộp đen f và tính đơn đỉnh đã chắc chắn.

Không dùng tam phân để tìm một giá trị trong mảng đã sắp; Binary Search mới khai thác quan hệ thứ tự đó. Tên “chia ba” không đồng nghĩa nhanh hơn “chia hai”—số lần gọi f mỗi vòng và điều kiện bài mới quyết định.

Các lỗi về biên

Gán l=m1+1, r=m2-1 một cách máy móc có thể bỏ nghiệm khi có đoạn phẳng. Dùng công thức m1,m2 rồi lặp tới l==r có thể kẹt. Đảo dấu so sánh giữa cực tiểu và cực đại làm giữ đúng phía xấu. Cuối cùng, không quét các điểm còn lại khiến phép chia nguyên bỏ sót nghiệm ở sát biên.

Tự kiểm tra bằng cách quét toàn bộ miền nhỏ

Khi thử nghiệm trên đoạn nguyên ngắn [l, r], bạn có thể viết một vòng lặp quét qua toàn bộ các số nguyên từ l đến r, tính trực tiếp f(x) rồi chọn giá trị nhỏ nhất (ưu tiên x nhỏ nhất khi bằng nhau). Cách quét trực tiếp này độc lập hoàn toàn với bước chia ba, giúp bạn kiểm tra các ca dễ sai như nghiệm nằm ở giữa miền, đáy thực nằm giữa hai số nguyên làm hai điểm đạt cùng giá trị nhỏ nhất, và miền chỉ gồm đúng một điểm l = r.

Khi sinh dữ liệu ngẫu nhiên để thử, hãy giữ mảng a nhỏ và đoạn [l, r] hẹp (ví dụ trong [-50, 50]) để vòng quét trực tiếp chạy tức thì. Bạn cũng có thể thử thay hàm mục tiêu bằng tổng trị tuyệt đối |x-a1|+…+|x-ak| (với k chẵn, hàm có cả một đoạn đáy phẳng), nhưng tuyệt đối không kiểm tra một hàm Ternary Search bằng một hàm Ternary Search thứ hai có cùng công thức chia điểm.

Ba bài tự luyện có đáp số

  1. Tìm số nguyên x trong [-20,20] làm nhỏ nhất (x-3)^2 + (x-9)^2. Đáp số: x bằng 6, giá trị 18.
  2. Tìm số nguyên x trong [0,10] làm lớn nhất -(x-4)^2 + 25. Đáp số: x bằng 4, giá trị 25; khi tìm cực đại phải đảo chiều so sánh.
  3. Tìm x nhỏ nhất trong [0,8] đạt min của dãy 9,7,5,3,3,3,6,8,10. Đáp số: x bằng 3; đây là ca đáy phẳng để kiểm quy tắc hòa.

Với mỗi bài, hãy quét toàn miền nhỏ để lấy đáp án chuẩn rồi so với Ternary Search. Sau đó thử một hàm có hai đáy tách rời và quan sát thuật toán có thể loại nhầm; phản ví dụ này nhắc rằng tính đơn đỉnh là điều kiện bắt buộc, không phải mẹo tối ưu.

Nhận diện đơn đỉnh từ đề bài

Các cụm “chi phí lồi”, “khoảng cách bình phương”, “một điểm cân bằng” thường gợi ý một đáy, nhưng vẫn phải chứng minh. Tổng các hàm lồi là lồi; vì vậy tổng bình phương khoảng cách giữ tính chất. Ngược lại, min của hai hàm lồi có thể tạo hai đáy và làm tam phân sai.

Trên số nguyên, có thể xét hiệu d(x)=f(x+1)-f(x). Nếu d không giảm, f lồi rời rạc và điểm đổi dấu xác định vùng tối ưu. Khi tính d rẻ, tìm kiếm nhị phân trên dấu thường dùng ít lần gọi f hơn tam phân. Khi chỉ có hàm hộp đen và biết đơn đỉnh, tam phân dễ áp dụng hơn.

Hãy luôn kiểm hai biên l và r; cực trị có thể nằm ngay biên nếu đoạn không chứa đỉnh tự nhiên của hàm. Bài tự luyện nên có một ca nghiệm trái, một ca nghiệm phải, một đáy phẳng và một miền chỉ một điểm. Bốn ca này bắt hầu hết lỗi thu hẹp và quét cuối.

Chi phí gọi hàm cũng quan trọng

Nếu mỗi lần tính f phải chạy một thuật toán O(n), số lần đánh giá ảnh hưởng lớn. Với cách chia ba đều, hai điểm đổi hẳn sau mỗi vòng nên không dùng lại được giá trị cũ; biến thể golden-section search đặt m1, m2 theo tỉ lệ vàng để mỗi vòng dùng lại được một giá trị và chỉ phải tính f thêm một lần. Cách khác là chuyển sang tìm nhị phân trên đạo hàm rời rạc nếu chứng minh được tính đơn điệu. Với số thực, dừng theo số vòng cố định thường ổn định hơn so sánh độ dài với epsilon trên các thang giá trị rất khác nhau.

Khi in đáp án, độ chính xác yêu cầu và sai số của phép tính là hai chuyện riêng. In nhiều chữ số không sửa được một hàm mục tiêu bị tràn số hoặc mất chính xác. Hãy dùng kiểu số đủ rộng, rồi kiểm lại giá trị tại nghiệm và hai điểm lân cận trước khi kết luận.

Luyện tiếp

Trang luyện tập của Big-O Coding chưa có bài gắn nhãn tìm kiếm tam phân. Hãy làm ba bài tự luyện có đáp số ở mục trên, rồi tự luyện thêm bằng ba hàm: tổng bình phương, tổng trị tuyệt đối và một parabol cực đại; mỗi hàm so với cách quét toàn miền nhỏ. Muốn ôn lại tìm kiếm nhị phân và các bài tối ưu theo đáp án, bạn có thể đi theo lộ trình Luyện thi HSG & Olympic Tin học — 250 bài.

Câu hỏi thường gặp

Hàm lồi luôn dùng được tam phân không?

Trên một đoạn và với phép đánh giá nhất quán, hàm lồi có dạng phù hợp cho cực tiểu. Vẫn phải xử lý miền rời rạc và tràn số.

Bao nhiêu vòng cho số thực?

Phụ thuộc miền và sai số. Chạy số vòng cố định rồi phân tích độ dài đoạn còn lại an toàn hơn chờ hai số float bằng nhau.

Có thể ghi nhớ f(m1), f(m2) không?

Với cách chia ba đều thì không, vì hai điểm thay đổi mỗi vòng. Biến thể golden-section search chọn điểm theo tỉ lệ vàng để mỗi vòng dùng lại được một giá trị cũ. Trước hết giữ bản rõ ràng và đúng, sau đó mới đo chi phí f.

Muốn học bài bản cùng giảng viên?

Luyện phỏng vấn Google, Meta, Amazon theo Interview Patterns: 16 buổi online live, lớp 7–15 người, C++/Python/Java. Học thử buổi 1 miễn phí.

Xem Khóa Blue 2.0

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483