Punto de encuentro de 5 personas con menor distancia recorrida (pregunta de la entrevista)

Question

Hoy he tenido una entrevista y estoy completamente perplejo con lo que me han preguntado. Básicamente: si te dan 5 personas en una cuadrícula 2D, y tienes que reunirte en un punto con la menor distancia recorrida, ¿cómo lo calcularías?

Lo que le había dicho al entrevistador después de algunas preguntas es utilizar el teorema de Pitágoras para cada punto y luego sumarlos. Sé que fallé completamente en la respuesta...

De todos modos, ¿cuál es la forma adecuada de hacerlo? ¿Y hay un nombre para este tipo de problema para que pueda leer más en él?

Gracias.

Answer 1

Como estás en una cuadrícula, puedes separar el movimiento de cada persona en movimiento a lo largo del $x$ -y el movimiento a lo largo del eje $y$ -La cantidad de movimiento requerida es la suma de estos dos componentes. (Esta es la "distancia de Manhattan" o $L_1$ -distancia). Por lo tanto, si se puede minimizar simultáneamente el total $x$ -que hay que recorrer (que sólo depende de la $x$ -coordenadas del lugar de encuentro) y el total $y$ -que hay que recorrer (que sólo depende de la $y$ -coordenada del lugar de encuentro), entonces has encontrado el lugar óptimo. Como se indica en la otra respuesta, en una dimensión el lugar de encuentro óptimo es siempre la mediana de los lugares (o cualquier lugar entre los dos lugares centrales, si el número de personas es par). Así que la respuesta correcta es $(\bar{x}, \bar{y})$ , donde $\bar{x}=\text{median}(\{x_i\})$ y $\bar{y}=\text{median}(\{y_i\})$ .

Answer 2

Hagámoslo para una sola dimensión, de X1 a X5 en orden ascendente. X3 debería ser el punto de encuentro.
Si el punto de encuentro X > X3 entonces tienes 3 personas que van de X3 a X en lugar de 2 personas de X a X3. Con este principio se consigue que el mejor punto sea X3.

Los puntos Y también deben establecerse en orden ascendente, lo que significa que la persona que está en X1 no tiene que estar necesariamente en Y1.

Del mismo modo, Y3 es un buen punto de encuentro para el eje Y.

No sé si X3,Y3 es el mejor punto, pero la respuesta es un buen comienzo para una entrevista.