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 1$ y $m 2$ en este segmento: $l < m 1 < m 2 < r$ . Entonces, hay tres posibilidades:

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

$m 1 = l + (r - l)/3$
$m 2 = 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:

def BusquedaTernaria(f, l, r, 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.
    """
    while True:
        #l and r son los límites actuales; el máximo está entre ellos
        if abs(r - l) < absolutePrecision:
            return (l + r)/2

        m1 = l + (r - l)/3
        m2 = r - (r - l)/3

        if f(m1) < f(m2):
            l = m1
        else:
            r = m2

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

Referencias

Enlaces externos

Esta obra contiene una traducción derivada de «Ternary search» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

Datos: Q2010006