Búsqueda ternaria

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda

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[editar]

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 < bx, tenemos que f(a) < f(b), y
  • para todo a,b con xa < b ≤ B, tenemos que f(a) > f(b).

Algoritmo[editar]

Sea f(x) una función unimodal en el intervalo [l; r]. Tomamos dos puntos m1 y m2 en este segmento: l < m1 < m2 < r. Entonces, hay tres posibilidades:

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

  • m1 = l + (r-l)/3
  • m2 = r - (r-l)/3
Tiempo de ejecución

Algoritmo Recursivo[editar]

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[editar]

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[editar]

Referencias[editar]

Enlaces externos[editar]