Búsqueda ternaria

Algoritmo para encontrar los extremos de una función unimodal

Un algoritmo de búsqueda ternaria ^[1] es una técnica en informática para encontrar el mínimo o máximo de una función unimodal .

La función

Supongamos que buscamos un máximo de y que sabemos que el máximo se encuentra en algún punto entre y . Para que el algoritmo sea aplicable, debe haber algún valor tal que ${\displaystyle f(x)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle x}$

• para todos con , tenemos , y ${\displaystyle a,b}$ ${\displaystyle A\leq a<b\leq x}$ ${\displaystyle f(a)<f(b)}$
• Para todos con , tenemos . ${\displaystyle a,b}$ ${\displaystyle x\leq a<b\leq B}$ ${\displaystyle f(a)>f(b)}$

Algoritmo

Sea una función unimodal en un intervalo . Tome dos puntos cualesquiera y en este segmento: . Entonces hay tres posibilidades: ${\displaystyle f(x)}$ ${\displaystyle [l;r]}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle l<m_{1}<m_{2}<r}$

• Si , entonces el máximo requerido no puede ubicarse en el lado izquierdo – . Significa que el máximo adicional tiene sentido buscarlo solo en el intervalo ${\displaystyle f(m_{1})<f(m_{2})}$ ${\displaystyle [l;m_{1}]}$ ${\displaystyle [m_{1};r]}$
• Si , la situación es similar a la anterior, salvo simetría. Ahora, el máximo requerido no puede estar en el lado derecho – , entonces pasa al segmento ${\displaystyle f(m_{1})>f(m_{2})}$ ${\displaystyle [m_{2};r]}$ ${\displaystyle [l;m_{2}]}$
• Si , entonces la búsqueda debe realizarse en , pero este caso puede atribuirse 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 puede detenerse. ${\displaystyle f(m_{1})=f(m_{2})}$ ${\displaystyle [m_{1};m_{2}]}$

puntos de elección y : ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$

• ${\displaystyle m_{1}=l+(r-l)/3}$
• ${\displaystyle m_{2}=r-(r-l)/3}$

Orden de tiempo de ejecución

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

Algoritmo recursivo

def  ternary_search ( f ,  left ,  right ,  absolute_precision )  ->  float : """Izquierda y derecha son los límites actuales;  el máximo está entre ellos.  """ if abs ( right - left ) < absolute_precision : return ( left + right ) / 2              tercio_izquierdo  =  ( 2 * izquierda  +  derecha )  /  3  tercio_derecho  =  ( izquierda  +  2 * derecha )  /  3 si  f ( tercio_izquierdo )  <  f ( tercio_derecho ):  devuelve  búsqueda_ternaria ( f ,  tercio_izquierdo ,  derecho ,  precisión_absoluta )  de lo contrario :  devuelve  búsqueda_ternaria ( f ,  tercio_izquierdo ,  derecho ,  precisión_absoluta )

Algoritmo iterativo

def  ternary_search ( f ,  left ,  right ,  absolute_precision )  ->  float : """Encuentre el máximo de la función unimodal f() dentro de [left, right].  Para encontrar el mínimo, invierta la declaración if/else o invierta la comparación.  """ while abs ( right - left ) >= absolute_precision : left_third = left + ( right - left ) / 3 right_third = right - ( right - left ) / 3                          si  f ( tercio_izquierdo )  <  f ( tercio_derecho ):  izquierda  =  tercio_izquierdo  de lo contrario :  derecha  =  tercio_derecho # Izquierda y derecha son los límites actuales; el máximo está entre ellos  return  ( izquierda  +  derecha )  /  2

Véase también

• Método de Newton en optimización (se puede utilizar para buscar dónde la derivada es cero)
• Búsqueda de sección áurea (similar a la búsqueda ternaria, útil si la evaluación de f toma la mayor parte del tiempo por iteración)
• Algoritmo de búsqueda binaria (se puede utilizar para buscar dónde cambia de signo la derivada)
• Búsqueda por interpolación
• Búsqueda exponencial
• Búsqueda lineal

Referencias

1. "Búsqueda ternaria". cp-algorithms.com . Consultado el 21 de agosto de 2023 .