Un algoritmo de búsqueda ternario es una técnica en informática para encontrar el mínimo o máximo de una función unimodal . Una búsqueda ternaria determina que el mínimo o máximo no puede estar en el primer tercio del dominio o que no puede estar en el último tercio del dominio, luego se repite en los dos tercios restantes. Una búsqueda ternaria es un ejemplo de un algoritmo de divide y vencerás (ver algoritmo de búsqueda ).
La función
Supongamos que estamos buscando un máximo de f ( x ) y que conocemos las máximas encuentra en algún lugar entre una y B . Para que el algoritmo sea aplicable, debe haber algún valor x tal que
- para todo a , b con A ≤ a < b ≤ x , tenemos f ( a ) < f ( b ), y
- para todo a , b con x ≤ a < b ≤ B, tenemos f ( a )> f ( b ).
Algoritmo
Sea f ( x ) una función unimodal en algún intervalo [ l ; r ]. Tome dos puntos cualesquiera m 1 y m 2 en este segmento: l < m 1 < m 2 < r . Entonces hay tres posibilidades:
- si f ( m 1 ) < f ( m 2 ) , entonces el máximo requerido no puede ubicarse en el lado izquierdo - [ l ; m 1 ] . Significa que el máximo además tiene sentido mirar solo en el intervalo [ m 1 ; r ]
- si f ( m 1 )> f ( m 2 ) , 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 - [ m 2 ; r ] , así que ve al segmento [ l ; m 2 ]
- si f ( m 1 ) = f ( m 2 ) , entonces la búsqueda debe realizarse en [ m 1 ; m 2 ] , 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 puede detenerse.
puntos de elección m 1 y m 2 :
- m 1 = l + ( r - l ) / 3
- m 2 = r - ( r - l ) / 3
- Orden de tiempo de ejecución
Algoritmo recursivo
def ternary_search ( f , left , right , absoluta_precision ) -> float : "" "Izquierda y derecha son los límites actuales; el máximo está entre ellos. " "" if abs ( derecha - izquierda ) < absoluta_precision : return ( izquierda + derecha ) / 2 Tercer_izquierdo = ( 2 * Izquierda + Derecha ) / 3 Tercer_derecha = ( Izquierda + 2 * Derecha ) / 3 if f ( left_third ) < f ( right_third ): return ternary_search ( f , left_third , right , absoluta_precision ) else : return ternary_search ( f , left , right_third , absoluta_precision )
Algoritmo iterativo
def ternary_search ( f , left , right , absoluta_precision ) -> float : "" "Encuentra el máximo de la función unimodal f () dentro de [left, right] Para encontrar el mínimo, invierte la instrucción if / else o invierte la comparación. " " " while abs ( derecha - izquierda ) > = absoluta_precision : left_third = izquierda + ( derecha - izquierda ) / 3 right_third = derecha - ( derecha - izquierda ) / 3 if f ( izquierda_tercero ) < f ( derecha_tercero ): izquierda = izquierda_tercero else : derecha = derecha_tercero # Izquierda y derecha son los límites actuales; el máximo está entre ellos return ( izquierda + derecha ) / 2
Ver también
- Método de Newton en optimización (se puede usar 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 usar para buscar dónde la derivada cambia de signo)
- Búsqueda de interpolación
- Búsqueda exponencial
- Búsqueda lineal
- Implementación de búsqueda ternaria dimensional N