Búsqueda ternaria
Necesitamos búsqueda ternaria para encontrar el máximo o mínimo de una función unimodal en el segmento
[l, r]. Una función es unimodal cuando tiene un extremo en un segmento.
La búsqueda de los valores máximos de una función se suele utilizar para problemas de optimización. Por ejemplo, necesitamos encontrar el ángulo máximo posible de un triángulo rectángulo, en el que el área será la mayor. Para hacer esto, recorreremos los ángulos de
0 a
90, y en este segmento estamos buscando un área que primero aumentará y luego disminuirá, es decir, la función será unimodal.
Cómo funciona
El principio de funcionamiento es similar a la búsqueda binaria, pero podemos tener un caso al dividir el segmento por la mitad, cuando la mitad del segmento cae exactamente en el extremo, y & nbsp; no obtendremos un resultado claro.
Por lo tanto, para evitar tal caso, es necesario dividir el segmento no en dos partes, sino en tres, y descartamos la parte en la que no hay un extremo, etc., hasta que los límites converjan en el resultado.
doble f (doble hipo, doble alfa) {
alfa = (alfa *M_PI)/180;
return 0.5 * hipo * hipo * cos(alfa) * sin(alfa);
}
int principal() {
doble l = 0;
r doble = 90;
BPA doble = 1e-6;
doble hipo = 100;
mientras (r - l >=EPS) {
doble m1 = l + (r - l) / 3;
doble m2 = r - (r - l) / 3;
si (f(hipo, m1) < f(hipo, m2)) {
l=m1;
}
más {
r=m2;
}
}
fuera<< ((l + der) / 2);
devolver 0;
}
La búsqueda ternaria se puede modificar usando método de la sección dorada, lo que aumenta la tasa de convergencia en aproximadamente 2 veces.
Fuentes
1) búsqueda ternaria y proporción áurea
2) búsqueda ternaria