Herramientas de usuario
algoritmos-oia:busqueda-ternaria
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:busqueda-ternaria [2018/01/19 20:24] santo |
algoritmos-oia:busqueda-ternaria [2018/01/21 16:57] (actual) santo |
||
|---|---|---|---|
| Línea 101: | Línea 101: | ||
| ===== Búsqueda ternaria ===== | ===== 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. | 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 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$. | 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. | 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 ==== | ==== Código ==== | ||
| Línea 205: | Línea 209: | ||
| // El minimo seguro esta en el rango [a,b) elegido | // El minimo seguro esta en el rango [a,b) elegido | ||
| int a=minimo/d, b=maximo/d + 1; | int a=minimo/d, b=maximo/d + 1; | ||
| + | #define costo(x) obtenerMovidas(matriz, (x)*d, d) | ||
| while (b-a>1) | while (b-a>1) | ||
| { | { | ||
| int m1 = a + (b-a)/3; | int m1 = a + (b-a)/3; | ||
| int m2 = a + (2*(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; | b = m2; | ||
| else | else | ||
| Línea 215: | Línea 220: | ||
| } | } | ||
| // El optimo se encuentra en a, pues el rango es [a,a+1) | // 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{ | }else{ | ||
| cout << -1 << endl; | cout << -1 << endl; | ||
| Línea 240: | Línea 245: | ||
| 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. | 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 ===== | ===== Apéndice: Demostración de propiedades de unimodales ===== | ||
| FIXME: ¡Escribir unas demos! | FIXME: ¡Escribir unas demos! | ||
algoritmos-oia/busqueda-ternaria.1516393487.txt.gz · Última modificación: 2018/01/19 20:24 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
