Herramientas de usuario
mediana
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Próxima revisión | Revisión previa | ||
|
mediana [2018/01/21 16:47] santo creado |
mediana [2018/01/21 16:50] (actual) santo |
||
|---|---|---|---|
| Línea 15: | Línea 15: | ||
| Supongamos que tenemos una larga ruta, con $n$ pueblos en ciertas posiciones. Tenemos que elegir una posición de la ruta para crear allí una oficina de correos, de modo tal que **el total** de lo que se debe viajar desde cada pueblo hasta la oficina de correos sea lo menor posible. | Supongamos que tenemos una larga ruta, con $n$ pueblos en ciertas posiciones. Tenemos que elegir una posición de la ruta para crear allí una oficina de correos, de modo tal que **el total** de lo que se debe viajar desde cada pueblo hasta la oficina de correos sea lo menor posible. | ||
| - | El total es justamente la suma, sobre todos los pueblos, de la distancia entre el pueblo y la oficina. Más precisamente, si el pueblo $i$ está en el kilómetro $p_i$ de la ruta, y ubicamos la oficina de correos en $x$, entonces el total de kilómetros de viaje será $\sum_i=1^n${|p_i - x|}$. Lo que buscamos es el $x$ que minimice esta cuenta. | + | El total es justamente la suma, sobre todos los pueblos, de la distancia entre el pueblo y la oficina. Más precisamente, si el pueblo $i$ está en el kilómetro $p_i$ de la ruta, y ubicamos la oficina de correos en $x$, entonces el total de kilómetros de viaje será $\sum_{i=1}^n{|p_i - x|}$. Lo que buscamos es el $x$ que minimice esta cuenta. |
| Como ejemplo de [[algoritmos-oia:busqueda-ternaria|búsqueda ternaria]], vimos que la función anterior resulta ser convexa y por lo tanto unimodal, así que con búsqueda binaria o ternaria se puede encontrar el valor mínimo y el kilómetro óptimo (valor de $x$) donde ubicar la oficina. | Como ejemplo de [[algoritmos-oia:busqueda-ternaria|búsqueda ternaria]], vimos que la función anterior resulta ser convexa y por lo tanto unimodal, así que con búsqueda binaria o ternaria se puede encontrar el valor mínimo y el kilómetro óptimo (valor de $x$) donde ubicar la oficina. | ||
| - | Sin embargo, es posible dar una solución más elegante, que permite entender mejor lo que está pasando y que a veces es más útil para razonar o para resolver problemas más complejos: resulta que el valor óptimo de $x$ es **la mediana** ((Si $n$ es par, cualquier valor entre los dos elementos del medio, inclusive, produce un total óptimo.)). La explicación se basa en el dibujo interactivo que se pued ever [[https://www.xarg.org/2016/07/calculate-the-argmin-of-the-sum-of-absolute-values/|aquí]]. Como la distancia total es la suma de las "barritas" desde $x$ hasta los puntos, cuando hay más barritas de un lado que del otro, es posible bajar la distancia total moviendo $x$ en esa dirección. Por lo tanto, necesariamente el mejor valor posible tendrá que tener igual cantidad barritas saliendo hacia cada lado, para que no se puede mejorar moviendo $x$. Y eso ocurre cuando $x$ es la mediana de los puntos $p_i$. | + | Sin embargo, es posible dar una solución más elegante, que permite entender mejor lo que está pasando y que a veces es más útil para razonar o para resolver problemas más complejos: resulta que el valor óptimo de $x$ es **la mediana** ((Si $n$ es par, cualquier valor entre los dos elementos del medio, inclusive, produce un total óptimo.)). La explicación se basa en el dibujo interactivo que se puede ver [[https://www.xarg.org/2016/07/calculate-the-argmin-of-the-sum-of-absolute-values/|aquí]]. Como la distancia total es la suma de las "barritas" desde $x$ hasta los puntos, cuando hay más barritas de un lado que del otro, es posible bajar la distancia total moviendo $x$ en esa dirección. Por lo tanto, necesariamente el mejor valor posible tendrá que tener igual cantidad barritas saliendo hacia cada lado, para que no se puede mejorar moviendo $x$. Y eso ocurre cuando $x$ es la mediana de los puntos $p_i$. |
| == Problemas relacionados a la mediana == | == Problemas relacionados a la mediana == | ||
| Línea 29: | Línea 29: | ||
| == Variante con pesos == | == Variante con pesos == | ||
| - | Una variante de la misma idea puede ocurrir cuando los "pueblos" tienen un peso $w_i$ (podría ser su cantidad de habitantes), de forma que nos interesa optimizar $\sum_i=1^n${w_i|p_i - x|}$. En este caso, lo que notamos es que la cuenta es la misma que en el problema normal sin pesos, si tuviéramos $w_i$ copias del pueblo $p_i$((Si bien esta "idea" se basa en que los pesos $w_i$ sean enteros, la conclusión sigue siendo válida con pesos reales positivos.)). Entonces, el lugar óptimo es la "mediana de los pesos", es decir, la posición de aquel pueblo que reparta los pesos totales a izquierda y derecha lo más parejo posible. | + | Una variante de la misma idea puede ocurrir cuando los "pueblos" tienen un peso $w_i$ (podría ser su cantidad de habitantes), de forma que nos interesa optimizar $\sum_{i=1}^n{w_i|p_i - x|}$. En este caso, lo que notamos es que la cuenta es la misma que en el problema normal sin pesos, si tuviéramos $w_i$ copias del pueblo $p_i$((Si bien esta "idea" se basa en que los pesos $w_i$ sean enteros, la conclusión sigue siendo válida con pesos reales positivos.)). Entonces, el lugar óptimo es la "mediana de los pesos", es decir, la posición de aquel pueblo que reparta los pesos totales a izquierda y derecha lo más parejo posible. |
| == Variante asimétrica == | == Variante asimétrica == | ||
mediana.1516553276.txt.gz · Última modificación: 2018/01/21 16:47 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
