búsqueda ternaria

Algoritmo para encontrar los extremos de una función unimodal

Un algoritmo de búsqueda ternario ^[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 estamos buscando 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 algún 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 se puede ubicar en el lado izquierdo – . Esto significa que tiene sentido buscar el máximo solo en el intervalo ${\displaystyle f(m_{1})<f(m_{2})}$ ${\displaystyle [l;m_{1}]}$ ${\displaystyle [m_{1};r]}$
• si , que la situación es similar a la anterior, hasta la simetría. Ahora, el máximo requerido no puede estar en el lado derecho – , así que vaya 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 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. ${\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 ,  izquierda ,  derecha ,  precisión_absoluta )  ->  float : """Izquierda y derecha son los límites actuales;  el máximo está entre ellos.  """ if abs ( derecha - izquierda ) < precisión_absoluta : return ( izquierda + derecha ) / 2              tercio_izquierdo  =  ( 2 * izquierda  +  derecha )  /  3  tercio_derecho  =  ( izquierda  +  2 * derecha )  /  3 si  f ( tercero_izquierdo )  <  f ( tercero_derecho ):  devuelve  búsqueda_ternaria ( f ,  tercio_izquierdo ,  derecha ,  precisión_absoluta )  más :  devuelve  búsqueda_ternaria ( f ,  izquierda ,  tercio_derecho ,  precisión_absoluta )

Algoritmo iterativo

def  ternary_search ( f ,  izquierda ,  derecha ,  precisión_absoluta )  ->  float : """Encontrar el máximo de la función unimodal f() dentro de [izquierda, derecha].  Para encontrar el mínimo, invierta la declaración if/else o invierta la comparación.  " "" mientras que abs ( derecha - izquierda ) >= precisión_absoluta : tercio_izquierdo = izquierda + ( derecha - izquierda ) / 3 tercio_derecho = derecha - ( derecha - izquierda ) / 3                          si  f ( tercero_izquierdo )  <  f ( tercero_derecho ):  izquierda  =  tercio_izquierdo  más :  derecha  =  tercio_derecho # Izquierda y derecha son los límites actuales; el máximo está entre ellos  retorno  ( izquierda  +  derecha )  /  2

Ver también

• El 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 evaluar f lleva 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
• Implementación de búsqueda ternaria de dimensiones N

Referencias

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