Loading AI tools
técnica en ciencias de la computación para hallar los extremos de una función unimodal De Wikipedia, la enciclopedia libre
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).
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
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:
Puntos de partición m1 y m2:
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 );
}
}
}
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;
}
}
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.