Pesquisa ternária
Precisamos de pesquisa ternária para encontrar o máximo ou mínimo de uma função unimodal no segmento
[l, r]. Uma função é unimodal quando possui um extremo em um segmento.
A busca pelos valores máximos de uma função é frequentemente utilizada para problemas de otimização. Por exemplo, precisamos encontrar o ângulo máximo possível de um triângulo retângulo, no qual a área será maior. Para fazer isso, vamos percorrer os ângulos de
0 a
90, e neste segmento procuramos uma área que primeiro aumentará e depois diminuirá, ou seja, a função será unimodal.
Como funciona
O princípio de operação é semelhante à pesquisa binária, mas podemos ter um caso ao dividir o segmento ao meio, quando o meio do segmento cai exatamente no extremo e & nbsp; não obteremos um resultado claro.
Portanto, para evitar tal caso, é necessário dividir o segmento não em duas partes, mas em três, e descartamos a parte em que não há extremo, etc., até que os limites convirjam para o resultado.
duplo f (duplo hipo, duplo alfa) {
alfa = (alfa *M_PI)/180;
retorno 0,5 * hipo * hipo * cos(alfa) * sin(alfa);
}
int principal() {
duplo l = 0;
duplo r = 90;
EPS duplo = 1e-6;
dupla hipo = 100;
enquanto (r - l >=EPS) {
duplo m1 = l + (r - l) / 3;
duplo m2 = r - (r - l) / 3;
if (f(hipo, m1) < f(hipo, m2)) {
l=m1;
}
outro {
r=m2;
}
}
fora<< ((l + r) / 2);
retorna 0;
}
A pesquisa ternária pode ser modificada usando método da seção áurea, o que aumenta a taxa de convergência em cerca de 2 vezes.
Fontes
1) pesquisa ternária e proporção áurea
2) pesquisa ternária