Búsqueda ternaria

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 f(x) una función unimodal en el intervalo [l; r]. Tomamos dos puntos m₁ y m₂ en este segmento: l < m₁ < m₂ < r. Entonces, hay tres posibilidades:

• Si f(m₁) < f(m₂), entonces el máximo requerido no puede ubicarse en el lado izquierdo - [l; m₁]. Esto significa que el máximo debe buscarse en el intervalo [m₁;r]
• Si f(m₁) > f(m₂), de manera similar al anterior caso. Ahora, el máximo requerido no puede estar en el lado derecho - [m₂; r], así que debe buscarse en el segmento [l; m₂]
• Si f(m₁) = f(m₂), entonces la búsqueda debe realizarse en [m₁; m₂], 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 m₁ y m₂:

• m₁ = l + (r-l)/3
• m₂ = r - (r-l)/3

Tiempo de ejecución

$T(n)=T(2n/3)+1=\Theta (\log 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

Enlaces externos

• Datos: Q2010006