Ricerca ternaria
Abbiamo bisogno di una ricerca ternaria per trovare il massimo o il minimo di una funzione unimodale sul segmento
[l, r]. Una funzione è unimodale quando ha un estremo su un segmento.
La ricerca dei valori massimi di una funzione viene spesso utilizzata per problemi di ottimizzazione. Ad esempio, dobbiamo trovare l'angolo massimo possibile di un triangolo rettangolo, in corrispondenza del quale l'area sarà la più grande. Per fare ciò, attraverseremo gli angoli da
0 a
90, e su questo segmento cerchiamo un'area che prima aumenterà e poi diminuirà, cioè la funzione sarà unimodale.
Come funziona
Il principio di funzionamento è simile alla ricerca binaria, ma potremmo avere un caso quando si divide il segmento a metà, quando il centro del segmento cade esattamente sull'estremo e & nbsp; non otterremo un risultato chiaro.
Pertanto, per evitare un caso del genere, è necessario dividere il segmento non in due parti, ma in tre, e scartiamo la parte in cui non c'è estremo, ecc., Fino a quando i confini non convergono sul risultato.
doppia f( doppia ipo, doppia alfa ) {
alfa = (alfa *M_PI)/180;
restituisce 0,5 * hypo * hypo * cos(alpha) * sin(alpha);
}
int main() {
doppio l = 0;
doppio r = 90;
doppio EPS = 1e-6;
doppia ipo = 100;
mentre (r - l >=EPS) {
doppio m1 = l + (r - l) / 3;
doppio m2 = r - (r - l) / 3;
if (f(ipo, m1) < f(ipo, m2)) {
l=m1;
}
altro {
r=m2;
}
}
fuori<< ((l + r) / 2);
ritorno 0;
}
La ricerca ternaria può essere modificata utilizzando metodo della sezione aurea, che aumenta il tasso di convergenza di circa 2 volte.
Fonti
1) ricerca ternaria e rapporto aureo
2) ricerca ternaria