Busca ternaria

Un algoritme de busca ternaria és una tècnica en ciències de la computació per a trobar els extrems d'una funció (màxim o mínim) d'una funció unimodal. Una busca ternaria determina que l'extrem que es busca, no pot estar en el primer terç del domini o que no pot estar en l'últim terç del domini, despuix es repetix el procés en els dos terços restants. Una busca ternaria és un eixemple d'un Algoritme dividix i venceràs (vore Algoritme de busca).

Funció

Supongam que estem buscant un màxim de f(x) i sabem que el màxim es troba en algun lloc entre A i B. Per a que l'algoritme siga aplicable deu haver un valor x tal que

• para tot a,b en A ≤ a < b ≤ x, tenim que f(a) < f(b), i
• per a tot a,b en x ≤ a < b ≤ B, tenim que f(a) > f(b).

Algoritme

Siga f(x) una funció unimodal en l'interval [l; r]. Prenem dos punts m₁ i m₂ en este segment: l < m₁ < m₂ < r. Llavors, hi ha tres possibilitats:

• Si f(m₁) < f(m₂), llavors el màxim requerit no pot ubicar-se en el costat esquerre - [l; m₁]. Açò significa que el màxim deu buscar-se en l'interval [m₁;r]
• Si f(m₁) > f(m₂), de manera similar a l'anterior cas. Ara, el màxim requerit no pot estar en el costat dret - [m₂; r], aixina que deu buscar-se en el segment [l; m₂]
• Si f(m₁) = f(m₂), llavors la busca deu realisar-se en [m₁; m₂], pero este cas es pot atribuir a qualsevol dels dos anteriors (per a simplificar el còdic). Vesprada o enjorn, la llongitut del segment serà una miqueta menor que una constant predeterminada, i el procés podrà detindre's.

Punts de partició m₁ i m₂:

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

Temps d'eixecució

$T(n)=T(2n/3)+1=\Theta (\log n)$

Algoritme Recursivo

en llenguage Python:

def BusquedaTernaria(f, l, r, absolutePrecision):
    '''
    l i r són els llímits actuals; 
    el màxim està entre ells;
    absolutePrecision és el nivell de precisió
    '''
    if abs(r - l) < absolutePrecision:
        return (l + r)/2

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

    if f(m1) < f(m2):
        return BúsquedaTernaria(f, m1, r, absolutePrecision) 
    else:
        return BúsquedaTernaria(f, l, m2, absolutePrecision)

en llenguage C:

double BusquedaTernaria(double f[] ,int l ,int r ,double absolutePrecision )
{
    //l i r són els llímits actuals; 
    //el màxim està entre ells;
    //absolutePrecision és una constant 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 );
		}		
	}
}

Algoritme Iterativo

en llenguage Python:

from typing import Callable, Tuple

def trisection(f: Callable, bracket: Tuple[float, float, float], xtol=0.001, maxiter=100) -> Tuple[float, int, int]:
    """Rep una funcion f, una tupla bracket que definix un bracket de f i, a partir de dit bracket, torna 
    una tupla r, nit, nfev en un minimo aproximat r i el numeros de iteraciones i d'evaluacions de 
    f necessàries per a trobar-ho  per mig del método de triseccion

    Args:
        f (Callable): funció a evaluar
        bracket (Tuple[float, float, float]): bracket sobre el que buscar el mínim
        xtol (float, optional): marge d'error mínim. Per defecte és 0.001.
        maxiter (int, optional): número de iteraciones màximes de l'algoritme. Per defecte és 100.

    Raises:

Exception: s'ha superat el número maximo de iteraciones
        ValueError: el bracket no complix les condicions d'orde

    Returns:
        Tuple[float, int, int]: tupla en la raiz, en numere de iteraciones i el numere d'evaluacions 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 d'evaluacions de la funció
    
    while abs(c - a) > xtol and nit <= maxiter:
        nit += 1
        nfev += 2  # Evaluem la funció en dos nous punts
        
        # Calculem els punts intermijos
        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àxim de iteraciones permeses ha segut excedit.")
    
    r = (a + c) / 2
    return r, nit, nfev

en llenguage C:

double BusquedaTernaria(double f[] ,int l ,int r ,double absolutePrecision )
{
    //Buscar el màxim de la funció unimodal f () dins de [l, r] 
    //Per a trobar el mínim, invertixca l'instrucció if / else o invertixca la comparació. 
	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;
		}
	}    
}

Vore també

• Busca de la secció dorada
• Busca binaria
• Busca exponencial