Un algoritmo de búsqueda ternaria es una técnica en ciencias de la computación para hallar los extremos de una función (máximo o mínimo) de una función unimodal. Una búsqueda ternaria determina que el extremo que se busca, no puede estar en el primer tercio del dominio o que no puede estar en el último tercio del dominio, luego se repite el proceso en los dos tercios restantes. Una búsqueda ternaria es un ejemplo de un Algoritmo divide y vencerás (ver Algoritmo de búsqueda).
Función
Supongamos que estamos buscando un máximo de f(x) y sabemos que el máximo se encuentra en algún lugar entre A y B. Para que el algoritmo sea aplicable debe haber un valor x tal que para todo a,b con A ≤ a < b ≤ x, tenemos que f(a) < f(b), y para todo a,b con x ≤ a < b ≤ B, tenemos que f(a) > f(b).
Algoritmo
Sea una función unimodal en el intervalo [l; r]. Tomamos dos puntos y en este segmento: . Entonces, hay tres posibilidades: Si , entonces el máximo requerido no puede ubicarse en el lado izquierdo - . Esto significa que el máximo debe buscarse en el intervalo Si , de manera similar al anterior caso. Ahora, el máximo requerido no puede estar en el lado derecho - , así que debe buscarse en el segmento Si , entonces la búsqueda debe realizarse en , pero este caso se puede atribuir a cualquiera de los dos anteriores (para simplificar el código). Tarde o temprano, la longitud del segmento será un poco menor que una constante predeterminada, y el proceso podrá detenerse. Puntos de partición y :
Tiempo de ejecución
Algoritmo Recursivo en lenguaje Python: def BusquedaTernaria(f, l, r, absolutePrecision): ''' l y r son los límites actuales; el máximo está entre ellos; absolutePrecision es el nivel de precisión ''' if abs(r - l) < absolutePrecision: return (l + r)/2
m1 = (2*l + r)/3 m2 = (l + 2*r)/3
if f(m1) < f(m2): return BúsquedaTernaria(f, m1, r, absolutePrecision) else: return BúsquedaTernaria(f, l, m2, absolutePrecision)
en lenguaje C: double BusquedaTernaria(double f[] ,int l ,int r ,double absolutePrecision ) { //l y r son los límites actuales; //el máximo está entre ellos; //absolutePrecision es una constante predeterminada
if(r-l <= absolutePrecision) { return ( l + r ) / 2.0; } else { int m1 = ( 2 * l + r ) / 3; int m2 = ( l + 2 * r ) / 3;
if(f[m1]< f[m2])
return BusquedaTernaria( f , m1 , r , absolutePrecision );
else
return BusquedaTernaria ( f , l , m2 , absolutePrecision );
Algoritmo Iterativo
en lenguaje Python: from typing import Callable, Tuple
def trisection(f: Callable, bracket: Tuple[float, float, float], xtol=0.001, maxiter=100) -> Tuple[float, int, int]: """Recibe una funcion f, una tupla bracket que define un bracket de f y, a partir de dicho bracket, devuelve una tupla r, nit, nfev con un minimo aproximado r y el numeros de iteraciones y de evaluaciones de f necesarias para encontrarlo mediante el método de triseccion
Args: f (Callable): función a evaluar bracket (Tuple[float, float, float]): bracket sobre el que buscar el mínimo xtol (float, optional): margen de error mínimo. Por defecto es 0.001. maxiter (int, optional): número de iteraciones máximas del algoritmo. Por defecto es 100.
Raises: Exception: se ha superado el número maximo de iteraciones ValueError: el bracket no cumple las condiciones de orden
Returns: Tuple[float, int, int]: tupla con la raiz, en numero de iteraciones y el numero de evaluaciones de la funcion """ a, b, c = bracket if not (a < b < c) and not (f(a) > f(b) and f(b) < f(c)): raise ValueError('Incorrect bracket')
nit = 0 # Número de iteraciones nfev = 0 # Número de evaluaciones de la función
while abs(c - a) > xtol and nit <= maxiter: nit += 1 nfev += 2 # Evaluamos la función en dos nuevos puntos
# Calculamos los puntos intermedios x1 = a + (c - a) / 3 x2 = c - (c - a) / 3
f1 = f(x1) f2 = f(x2)
if f1 < f2: c = x2 else: a = x1
if nit >= maxiter: raise Exception("El número máximo de iteraciones permitidas ha sido excedido.")
r = (a + c) / 2 return r, nit, nfev
en lenguaje C: double BusquedaTernaria(double f[] ,int l ,int r ,double absolutePrecision ) { //Buscar el máximo de la función unimodal f () dentro de [l, r] //Para encontrar el mínimo, invierta la instrucción if / else o invierta la comparación. bool b=true; while(b==true) { if( r - l <= absolutePrecision)
b=false; return ( l + r) / 2;
int m1 = ( 2 * l + r ) / 3; int m2 = ( l + 2 * r ) / 3; if(f[m1]< f[m2])
l = m1;
else
r = m2;
Véase también Búsqueda de la sección dorada Búsqueda binaria Búsqueda exponencial
Referencias
Enlaces externos
Categoría:Algoritmos de búsqueda Categoría:Optimización