جستجوی سه تایی
برای یافتن حداکثر یا حداقل یک تابع تک وجهی در بخش
[l, r] به جستجوی سه تایی نیاز داریم. یک تابع زمانی یک وجهی است که یک انتها در یک قطعه داشته باشد.
جستجو برای حداکثر مقادیر یک تابع اغلب برای مسائل بهینه سازی استفاده می شود. به عنوان مثال، ما باید حداکثر زاویه ممکن یک مثلث قائم الزاویه را پیدا کنیم که در آن مساحت بزرگترین باشد. برای این کار از زوایای
0 تا
90 عبور می کنیم و در این بخش به دنبال ناحیه ای هستیم که ابتدا افزایش و سپس کاهش می یابد، یعنی. تابع یک وجهی خواهد بود.
چگونه کار می کند
اصل عملکرد شبیه به جستجوی باینری است، اما ممکن است موردی داشته باشیم که بخش را به نصف تقسیم کنیم، زمانی که وسط قطعه دقیقاً روی انتهایی قرار می گیرد و & nbsp; نتیجه روشنی نخواهیم گرفت.
بنابراین برای جلوگیری از چنین موردی لازم است که قطعه را نه به دو قسمت، بلکه به سه قسمت تقسیم کنیم و قسمتی را که در آن اکستریم و غیره وجود ندارد، دور بریزیم تا مرزها روی نتیجه همگرا شوند.
double f( double hypo, double alpha ) {
آلفا = (آلفا *M_PI)/180;
بازگشت 0.5 * hypo * hypo * cos(alpha) * sin(alpha);
}
int main() {
l دو برابر = 0;
r = 90;
EPS دو برابر = 1e-6;
هیپو دو برابر = 100;
در حالی که (r - l >=EPS) {
m1 دو برابر = l + (r - l) / 3;
متر مربع دو برابر = r - (r - l) / 3;
اگر (f(hypo، m1) < f(hypo، m2)) {
l=m1;
}
دیگر {
r=m2;
}
}
خارج<< ((l + r) / 2);
بازگشت 0;
}
جستجوی سه‌گانه را می‌توان با استفاده از روش مقطع طلایی، که نرخ همگرایی را حدود 2 برابر افزایش می دهد.
منابع
1) جستجوی سه تایی و نسبت طلایی
2) جستجوی سه تایی