Tìm kiếm bậc ba
Chúng ta cần tìm kiếm bậc ba để tìm giá trị lớn nhất hoặc giá trị nhỏ nhất của một hàm đơn thức trên đoạn
[l, r]. Hàm số là đơn phương khi nó có một cực trị trên một đoạn.
Việc tìm kiếm các giá trị lớn nhất của một hàm thường được sử dụng cho các bài toán tối ưu hóa. Ví dụ: chúng ta cần tìm góc lớn nhất có thể có của một tam giác vuông mà tại đó diện tích sẽ lớn nhất. Để làm điều này, chúng tôi sẽ xem xét các góc từ
0 đến
90 và trên phân khúc này, chúng tôi đang tìm kiếm một khu vực sẽ tăng trước rồi sau đó giảm, tức là. chức năng sẽ là đơn thức.
Cách thức hoạt động
Nguyên tắc hoạt động tương tự như tìm kiếm nhị phân, nhưng chúng ta có thể gặp trường hợp khi chia đoạn làm đôi, khi đoạn giữa của đoạn rơi chính xác vào điểm cực trị và & nbsp; chúng tôi sẽ không nhận được kết quả rõ ràng.
Do đó, để tránh trường hợp như vậy, cần phải chia đoạn không phải thành hai phần mà thành ba phần và chúng tôi loại bỏ phần không có cực trị, v.v., cho đến khi các ranh giới hội tụ về kết quả.
double f(hypo kép, alpha kép) {
alpha = (alpha *M_PI)/180;
return 0,5 * hypo * hypo * cos(alpha) * sin(alpha);
}
int main() {
gấp đôi l = 0;
gấp đôi r = 90;
nhân đôi EPS = 1e-6;
hypo gấp đôi = 100;
while (r - l >=EPS) {
nhân đôi m1 = l + (r - l)/3;
nhân đôi m2 = r - (r - l)/3;
if (f(hypo, m1) < f(hypo, m2)) {
l=m1;
}
khác {
r=m2;
}
}
ra<< ((l+r)/2);
trả về 0;
}
Tìm kiếm bậc ba có thể được sửa đổi bằng cách sử dụng phương pháp phần vàng, làm tăng tốc độ hội tụ lên khoảng 2 lần.
Nguồn
1) tìm kiếm ternary và tỷ lệ vàng
2) tìm kiếm bậc ba