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/20 14:21] santo |
algoritmos-oia:busqueda-ternaria [2018/01/21 16:57] (actual) santo |
||
|---|---|---|---|
| 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: 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|módulo]] 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. | + | 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. | 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. | ||
| Línea 161: | 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 207: | 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 217: | 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 242: | 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.1516458087.txt.gz · Última modificación: 2018/01/20 14:21 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
