Recherche ternaire
Nous avons besoin d'une recherche ternaire pour trouver le maximum ou le minimum d'une fonction unimodale sur le segment
[l, r]. Une fonction est unimodale lorsqu'elle possède un extremum sur un segment.
La recherche des valeurs maximales d'une fonction est souvent utilisée pour des problèmes d'optimisation. Par exemple, nous devons trouver l'angle maximal possible d'un triangle rectangle, auquel l'aire sera la plus grande. Pour ce faire, nous allons passer par les angles de
0 à
90, et sur ce segment nous recherchons une zone qui va d'abord augmenter puis diminuer, c'est-à-dire la fonction sera unimodale.
Comment ça marche
Le principe de fonctionnement est similaire à la recherche binaire, mais nous pouvons avoir un cas lors de la division du segment en deux, lorsque le milieu du segment tombe exactement sur l'extremum, et & nbsp; nous n'obtiendrons pas de résultat clair.
Par conséquent, pour éviter un tel cas, il est nécessaire de diviser le segment non pas en deux parties, mais en trois, et nous écartons la partie dans laquelle il n'y a pas d'extremum, etc., jusqu'à ce que les limites convergent vers le résultat.
double f( double hypo, double alpha ) {
alpha = (alpha *M_PI)/180 ;
renvoie 0,5 * hypo * hypo * cos(alpha) * sin(alpha);
}
int main() {
double l = 0 ;
r double = 90 ;
double EPS = 1e-6 ;
double hypo = 100 ;
tandis que (r - l >=EPS) {
double m1 = l + (r - l) / 3 ;
double m2 = r - (r - l) / 3 ;
si (f(hypo, m1) < f(hypo, m2)) {
l=m1 ;
}
autrement {
r=m2 ;
}
}
sortie<< ((l + r) / 2);
renvoie 0 ;
}
La recherche ternaire peut être modifiée en utilisant méthode du nombre d'or, ce qui augmente le taux de convergence d'environ 2 fois.
Sources
1) ; recherche ternaire et nombre d'or
2) recherche ternaire