Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa | |||
mediana [2018/01/21 16:49] santo |
mediana [2018/01/21 16:50] (actual) santo |
||
---|---|---|---|
Línea 19: | Línea 19: | ||
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 puede 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 == |