Búsqueda ternaria

Se nos da una función $f(x)$ que es unimodal en un intervalo $[l, r]$ . Por función unimodal entendemos uno de estos dos comportamientos:

La función crece estrictamente primero, alcanza un máximo (en un solo punto o en un intervalo) y después decrece estrictamente.
La función decrece estrictamente primero, alcanza un mínimo y después crece estrictamente.

En este artículo asumiremos el primer escenario. El segundo es completamente simétrico al primero.

La tarea es encontrar el máximo de la función $f(x)$ en el intervalo $[l, r]$ .

Algoritmo

Consideremos cualesquiera 2 puntos $m_1$ y $m_2$ en este intervalo: $l < m_1 < m_2 < r$ . Evaluamos la función en $m_1$ y $m_2$ , es decir, encontramos los valores de $f(m_1)$ y $f(m_2)$ . Ahora tenemos una de tres opciones:

$f(m_1) < f(m_2)$

El máximo deseado no puede estar a la izquierda de $m_1$ , es decir, en el intervalo $[l, m_1]$ , porque o ambos puntos $m_1$ y $m_2$ o solo $m_1$ pertenecen a la zona donde la función crece. En cualquiera de los dos casos, esto significa que hay que buscar el máximo en el segmento $[m_1, r]$ .
$f(m_1) > f(m_2)$

Esta situación es simétrica a la anterior: el máximo no puede estar a la derecha de $m_2$ , es decir, en el intervalo $[m_2, r]$ , y el espacio de búsqueda se reduce al segmento $[l, m_2]$ .
$f(m_1) = f(m_2)$

Podemos ver que o ambos puntos pertenecen a la zona donde el valor de la función se maximiza, o $m_1$ está en la zona de valores crecientes y $m_2$ en la zona de valores decrecientes (acá usamos la estrictez del crecimiento/decrecimiento). Así, el espacio de búsqueda se reduce a $[m_1, m_2]$ . Para simplificar el código, este caso se puede combinar con cualquiera de los anteriores.

Así, a partir de la comparación de los valores en los dos puntos interiores, podemos reemplazar el intervalo actual $[l, r]$ por un intervalo nuevo, más corto, $[l^\prime, r^\prime]$ . Aplicando repetidamente el procedimiento descrito al intervalo, podemos obtener un intervalo arbitrariamente corto. Eventualmente, su longitud será menor que una constante predefinida (precisión), y el proceso se puede detener. Este es un método numérico, así que podemos asumir que después de eso la función alcanza su máximo en todos los puntos del último intervalo $[l, r]$ . Sin pérdida de generalidad, podemos tomar $f(l)$ como valor de retorno.

No impusimos ninguna restricción sobre la elección de los puntos $m_1$ y $m_2$ . Esa elección definirá la tasa de convergencia y la precisión de la implementación. La forma más común es elegir los puntos de modo que dividan el intervalo $[l, r]$ en tres partes iguales. Así, tenemos

$m_1 = l + \frac{(r - l)}{3}$

$m_2 = r - \frac{(r - l)}{3}$

Si $m_1$ y $m_2$ se eligen más cerca uno del otro, la tasa de convergencia aumenta un poco.

Análisis del tiempo de ejecución

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

Se puede visualizar así: cada vez que evaluamos la función en los puntos $m_1$ y $m_2$ , esencialmente ignoramos alrededor de un tercio del intervalo, el izquierdo o el derecho. Así, el tamaño del espacio de búsqueda es ${2n}/{3}$ del original.

Aplicando el teorema maestro , obtenemos la estimación de complejidad deseada.

El caso de argumentos enteros

Si $f(x)$ toma un parámetro entero, el intervalo $[l, r]$ se vuelve discreto. Como no impusimos restricciones sobre la elección de $m_1$ y $m_2$ , la corrección del algoritmo no se ve afectada. $m_1$ y $m_2$ se pueden seguir eligiendo para dividir $[l, r]$ en 3 partes aproximadamente iguales.

La diferencia aparece en el criterio de parada del algoritmo. La búsqueda ternaria tendrá que detenerse cuando $(r - l) < 3$ , porque en ese caso ya no podemos elegir $m_1$ y $m_2$ distintos entre sí y de $l$ y $r$ , y eso puede causar un bucle infinito. Una vez que $(r - l) < 3$ , el conjunto restante de puntos candidatos $(l, l + 1, \ldots, r)$ hay que chequearlo para encontrar el punto que produce el valor máximo $f(x)$ .

Búsqueda de la sección áurea

En algunos casos computar $f(x)$ puede ser bastante lento, pero reducir el número de iteraciones es inviable por temas de precisión. Por suerte, es posible computar $f(x)$ solo una vez en cada iteración (excepto la primera).

Para ver cómo, volvamos al método de selección de $m_1$ y $m_2$ . Supongamos que seleccionamos $m_1$ y $m_2$ en $[l, r]$ de modo que $\frac{r - l}{r - m_1} = \frac{r - l}{m_2 - l} = \varphi$ donde $\varphi$ es alguna constante. Para reducir la cantidad de cómputo, queremos elegir un $\varphi$ tal que en la siguiente iteración uno de los nuevos puntos de evaluación $m_1’$ , $m_2’$ coincida con $m_1$ o $m_2$ , para reutilizar el valor de la función ya computado.

Ahora supongamos que después de la iteración actual ponemos $l = m_1$ . Entonces el punto $m_1’$ satisfará $\frac{r - m_1}{r - m_1’} = \varphi$ . Queremos que este punto coincida con $m_2$ , es decir, $\frac{r - m_1}{r - m_2} = \varphi$ .

Multiplicando ambos lados de $\frac{r - m_1}{r - m_2} = \varphi$ por $\frac{r - m_2}{r - l}$ obtenemos $\frac{r - m_1}{r - l} = \varphi\frac{r - m_2}{r - l}$ . Nótese que $\frac{r - m_1}{r - l} = \frac{1}{\varphi}$ y $\frac{r - m_2}{r - l} = \frac{r - l + l - m_2}{r - l} = 1 - \frac{1}{\varphi}$ . Sustituyendo eso y multiplicando por $\varphi$ , obtenemos la siguiente ecuación:

$\varphi^2 - \varphi - 1 = 0$

Esta es la conocida ecuación de la sección áurea. Resolverla da $\frac{1 \pm \sqrt{5}}{2}$ . Como $\varphi$ debe ser positivo, obtenemos $\varphi = \frac{1 + \sqrt{5}}{2}$ . Aplicando la misma lógica al caso en que ponemos $r = m_2$ y queremos que $m_2’$ coincida con $m_1$ , obtenemos el mismo valor de $\varphi$ . Así, si elegimos $m_1 = l + \frac{r - l}{1 + \varphi}$ y $m_2 = r - \frac{r - l}{1 + \varphi}$ , en cada iteración podemos reutilizar uno de los valores $f(x)$ computados en la iteración anterior.

Implementación


double ternary_search(double l, double r) {
	double eps = 1e-9;				//set the error limit here
	while (r - l > eps) {
		double m1 = l + (r - l) / 3;
		double m2 = r - (r - l) / 3;
		double f1 = f(m1);		//evaluates the function at m1
		double f2 = f(m2);		//evaluates the function at m2
		if (f1 < f2)
			l = m1;
		else
			r = m2;
	}
	return f(l);					//return the maximum of f(x) in [l, r]
}

Acá eps es de hecho el error absoluto (sin tener en cuenta errores por el cálculo inexacto de la función).

En lugar del criterio r - l > eps, podemos elegir un número constante de iteraciones como criterio de parada. El número de iteraciones debería elegirse para asegurar la precisión requerida. Típicamente, en la mayoría de los challenges de programación el límite de error es ${10}^{-6}$ y por lo tanto 200 - 300 iteraciones alcanzan. Además, el número de iteraciones no depende de los valores de $l$ y $r$ , así que el número de iteraciones corresponde al error relativo requerido.