Herramientas de usuario

Herramientas del sitio


mediana

Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

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 ==
mediana.1516553378.txt.gz · Última modificación: 2018/01/21 16:49 por santo