Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:busqueda-ternaria [2018/01/19 20:16]
santo
+++ algoritmos-oia:busqueda-ternaria [2018/01/21 16:57] (actual)
santo
@@ Línea 101: / Línea 101: @@
 ===== Búsqueda ternaria =====
-Existe otro algoritmo diferente, también eficiente y que se puede aplicar en estos casos en lugar de la búsqueda binaria que acabamos de mostrar, y es el de //búsqueda ternaria//.
+Existe otro algoritmo diferente, también eficiente((aunque con peor factor constante)) y que se puede aplicar en estos casos en lugar de la búsqueda binaria que acabamos de mostrar, y es el de //búsqueda ternaria//.
 Esta búsqueda tiene la misma idea principal que la búsqueda binaria, que es la idea de ir examinando valores de la función y "descartando" posiciones candidatas en base a la información obtenida.
@@ Línea 152: / Línea 152: @@
 Veamos cómo llevar este problema a buscar un mínimo en una función unimodal, para aplicar las técnicas que aprendimos.
-Veamos que llevar todos los números a un número muy chiquito, puede llevarnos muchos pasos para mover los números grandes. Lo mismo si queremos llevar todos a un número muy grande, los chiquitos deberían sumar $d$ muchas veces. Es posible demostrar que esta función, que para cada posible número $x$ objetivo al cual queremos llevar los demás, nos dice la cantidad de pasos $f(x)$ necesarios, es una función unimodal sonriente. [FIXME: Explicar mejor esto!! Necesitamos una demostración, no es obvio para nada.] Buscaremos un número "intermedio" para el cual sea óptimo llevar a todos los números hacia éste, por lo tanto, con las técnicas que vimos para buscar mínimo de funciones unimodales sonrientes. Usaremos en este caso búsqueda ternaria, pero podríamos haber utilizado búsqueda binaria perfectamente.
+Veamos que llevar todos los números a un número muy chiquito, puede llevarnos muchos pasos para mover los números grandes. Lo mismo si queremos llevar todos a un número muy grande, los chiquitos deberían sumar $d$ muchas veces. Es posible demostrar que esta función, que para cada posible número $x$ objetivo al cual queremos llevar los demás, nos dice la cantidad de pasos $f(x)$ necesarios, es una función unimodal sonriente: La razón es que la cantidad de pasos para una casilla particular es $\frac{|v_{casilla} - x|}{d}$, que como función de $x$ es convexa (ya que es la función [[https://es.wikipedia.org/wiki/Valor_absoluto|valor absoluto]] trasladada y escalada), luego el costo total que es la suma de todas las casillas es suma de funciones convexas, y resulta también función convexa.
+Entonces, buscaremos un número "intermedio" para el cual sea óptimo llevar a todos los números hacia éste, por lo tanto, con las técnicas que vimos para buscar mínimo de funciones unimodales sonrientes. Usaremos en este caso búsqueda ternaria, pero podríamos haber utilizado búsqueda binaria perfectamente.
 Primero hay que ver cómo calcular la cantidad de movidas necesarias para llevar a todos los números a un número $v$, ya que eso es lo que nos permite evaluar $f(x)$ teniendo el $x$. Para eso, recorremos todos los números de la matriz, y la cantidad de movidas necesarias para cada número $a$ será la diferencia entre $a$ y $v$, dividido por $d$ que es cuánto se achica esa diferencia en cada movida; es decir, $abs(a-v)/d$.
@@ Línea 159: / Línea 161: @@
 Hay que tener cuidado porque cuando hagamos (b-a)/3, quizás no caemos en un número de igual resto en la división por $3$ que lo que queremos, entonces pensar en llevar a todos los número hacia éste no tendría sentido. Lo que podemos hacer en este problema para evitar esto, es primero, restarles a todos los números su resto en la división por $d$, total lo que importa son sus diferencias relativas ya que vamos a sumar y restar $d$. Y luego, es pensar "a qué múltiplo de $d$ queremos llevar a todos los números". Otra manera también sería divir todo por $d$ y pensar que las movidas suman y restan $1$, es completamente equivalente.
+Otra manera diferente de razonar y resolver este problema se explica [[algoritmos-oia:ordenamiento:mediana|en este artículo]].
 ==== Código ====
@@ Línea 205: / Línea 209: @@
         // El minimo seguro esta en el rango [a,b) elegido
         int a=minimo/d, b=maximo/d + 1;
+        #define costo(x) obtenerMovidas(matriz, (x)*d, d)
         while (b-a>1)
         {
             int m1 = a + (b-a)/3;
             int m2 = a + (2*(b-a))/3;
-            if (obtenerMovidas(matriz, m1*d, d) <= obtenerMovidas(matriz, m2*d, d))
+            if (costo(m1) <= costo(m2))
                 b = m2;
             else
@@ Línea 215: / Línea 220: @@
         }
         // El optimo se encuentra en a, pues el rango es [a,a+1)
-        cout << obtenerMovidas(matriz, a*d, d) << endl;
+        cout << costo(a) << endl;
     }else{
         cout << -1 << endl;
@@ Línea 229: / Línea 234: @@
 [[http://codeforces.com/problemset/tags/ternary%20search|ternary search en Codeforces]]
+===== Utilidad de la búsqueda ternaria =====
+Si podríamos haber usado búsqueda binaria común sin ningún problema en lugar de búsqueda ternaria, que es bastante más rebuscada ¿Cuál es el sentido de aprender a utilizar este método?
+Una primera ventaja es conocer otro algoritmo, ya que siempre mientras más ideas aprendemos, más herramientas tenemos para crear nuestras propias ideas en otros problemas, basándonos en ideas que vimos en otros algoritmos anteriores.
+Sin embargo, la ventaja auténtica de la búsqueda ternaria a la hora de buscar extremos de funciones unimodales, se observa en problemas con resultados **inexactos**, es decir con **cómputos de punto flotante**. Al trabajar con doubles y una función "continua" en los reales, no podemos hablar de "el siguiente real", para verificar en un punto particular si la función está creciendo o decreciendo (que es lo que analizamos al comparar $f(x)$ y $f(x+1)$). Podríamos comparar $f(x)$ con $f(x+\epsilon)$, siendo $\epsilon$ un valor muy chiquito, pero esto es propenso a errores de precisión en los cálculos y puede llevar a resultados erróneos, ya que estaríamos haciendo una comparación crítica en el algoritmo de dos valores muy muy cercanos.
+En estos casos, la búsqueda ternaria resuelve ambos inconvenientes: Es mucho más numéricamente estable al operar con resultados de punto flotante, ya que se evalúa la función en valores más espaciados, lo que hace que pequeñas diferencias no sean tan críticas al algoritmo. Y no hay que andar pensando en "el siguiente real", ya que no se evalúan "diferencias con el siguiente", sino que simplemente se examina el valor de la función en $a + \frac{b-a}{3}$ y $a + \frac{2(b-a)}{3}$.
+Al igual que pasaba con la búsqueda binaria, al utilizar la búsqueda ternaria en cómputos de punto flotante, podemos detener la búsqueda cuando el rango $[a,b)$ que sabemos que contiene al mínimo sea suficientemente pequeño, aceptando el error resultante.
+<code cpp>
+   // Los valores iniciales deben ser tales que haya un minimo en el rango [a,b) inicial.
+   const double EPS = 1e-9; // Determina el error que aceptamos, que impacta en la cantidad de pasos
+   double a = a_inicial;
+   double b = b_inicial;
+   while (b-a>EPS)
+   {
+      int m1 = a + (b-a)/3.0;
+      int m2 = a + (2.0*(b-a))/3.0;
+      if (f(m1) <= f(m2))
+         b = m2;
+      else
+         a = m1; // Ya no hay "+1": No hay un "siguiente numero real", es un continuo.
+   }
+   // Sabemos que el minimo esta en [a,b), asi que tomamos el punto medio como valor de compromiso.
+   double x = (a+b)/2.0;
+   return f(x);
+</code>
 ===== Apéndice: Demostración de propiedades de unimodales =====
 FIXME: ¡Escribir unas demos!

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página