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:26] santo |
algoritmos-oia:busqueda-ternaria [2018/01/21 16:57] (actual) santo |
||
|---|---|---|---|
| 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.1516458395.txt.gz · Última modificación: 2018/01/20 14:26 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
