Carian Ternary
Kami memerlukan carian ternary untuk mencari maksimum atau minimum fungsi unimodal pada segmen
[l, r]. Fungsi adalah unimodal apabila ia mempunyai satu ekstrem pada segmen.
Carian untuk nilai maksimum fungsi sering digunakan untuk masalah pengoptimuman. Sebagai contoh, kita perlu mencari sudut maksimum yang mungkin bagi segi tiga tepat, di mana kawasan itu akan menjadi yang terbesar. Untuk melakukan ini, kami akan melalui sudut dari
0 hingga
90, dan pada segmen ini kami mencari kawasan yang mula-mula akan meningkat dan kemudian berkurang, i.e. fungsi akan menjadi unimodal.
Cara ia berfungsi
Prinsip operasi adalah serupa dengan carian binari, tetapi kita mungkin mempunyai kes apabila membahagikan segmen pada separuh, apabila bahagian tengah segmen jatuh tepat pada extremum, dan & nbsp; kita tidak akan mendapat keputusan yang jelas.
Oleh itu, untuk mengelakkan kes sedemikian, adalah perlu untuk membahagikan segmen bukan kepada dua bahagian, tetapi kepada tiga, dan kami membuang bahagian yang tidak ada ekstrem, dsb., sehingga sempadan menumpu pada hasilnya.
double f( double hypo, double alpha ) {
alfa = (alfa *M_PI)/180;
kembali 0.5 * hypo * hypo * cos(alpha) * sin(alpha);
}
int main() {
ganda l = 0;
berganda r = 90;
EPS berganda = 1e-6;
ganda ganda = 100;
sementara (r - l >=EPS) {
berganda m1 = l + (r - l) / 3;
berganda m2 = r - (r - l) / 3;
jika (f(hipo, m1) < f(hipo, m2)) {
l=m1;
}
lain {
r=m2;
}
}
keluar<< ((l + r) / 2);
kembali 0;
}
Carian ternari boleh diubah suai menggunakan kaedah bahagian emas, yang meningkatkan kadar penumpuan kira-kira 2 kali ganda.
Sumber
1) carian ternari dan nisbah emas
2) carian ternari