Viaje de distancia más corta - punto de encuentro

Question

Encontré este problema en el que hay varias casas en una cuadrícula 2-D (se dan sus coordenadas) y esencialmente tenemos que encontrar qué casa se puede usar como punto de reunión que la distancia recorrida por todos se minimiza. Supongamos que una distancia a lo largo del eje xo y toma 1 unidad y una distancia a los vecinos diagonales toma (digamos) 1.2 unidades.

No puedo pensar en un buen algoritmo de optimización para esto.

P.S: No es un problema de tarea. Y solo busco un algoritmo (no código) y si es posible, es una prueba.

P.S # 2: No estoy buscando la solución Exhaustive. Créanlo o no, me llamó la atención :)

Answer 1

Esto es probablemente muy ineficiente, pero recorra todas las casas, luego recorra todas las otras casas. (anidados para bucles) Use distance formula para encontrar la distancia entre las 2 casas. Entonces tienes la distancia entre cada casa. Una manera rápida y fácil de encontrar qué casa es la distancia más cercana es agregar la distancia a pie de todos juntos para la casa dada. La casa con la menor distancia a pie total es el área de reunión de elección.

Answer 2

Bueno, podrías forzarlo brutalmente. Tome cada casa y calcule la distancia entre cada casa. Sume las distancias para cada casa individual. Entonces solo agarra la casa que tuvo la suma más baja.

Answer 3

Su métrica de distancia es extraña. Es de esperar que viajar en diagonal tome al menos sqrt (2) ~ = 1.41 veces la distancia de desplazamiento en la dirección del componente, porque así es cuánto más avanzar si se viaja en línea recta a lo largo de la diagonal con el teorema de Pitágoras .

Si insistió en una distancia en Manhattan (no se permiten diagonales), entonces querrá elegir la casa más cercana a la mediana (x) + mediana (y) de las casas.

Considere la caja 1D, tiene un montón de puntos en una línea y desea elegir el punto de reunión. Para ser más concretos/simples, digamos que hay 5 casas, ninguna duplicada.

Considere lo que ocurre cuando el punto de encuentro se aleja de la mediana a la derecha. Por cada unidad de distancia hasta que pase la 4ª casa de izquierda a derecha, 3 personas tienen que dar un paso adicional a la derecha, y 2 personas tienen que dar un paso menos a la izquierda, por lo que el costo aumenta en 1. Una vez pase la 4ª casa, luego 4 personas tengan que dar un paso adicional hacia la derecha, y una sola persona tenga que dar un paso menos a la izquierda, por lo que el costo aumenta en 3. Se mantiene un argumento idéntico al mover el punto de encuentro a la izquierda desde la mediana. Alejarse de la mediana siempre aumenta el costo.

El argumento se generaliza a cualquier número de personas, con o sin casas duplicadas, e incluso a través de un número arbitrario de dimensiones, siempre que no se permita el uso de la diagonal.

Answer 4

Como ya se señaló, en el caso de la distancia de Manhattan, la mediana da una solución. Esta es una conclusión obvia del hecho bien conocido de que la mediana minimiza la media de la desviación absoluta:

E|X-c| >= E|X-median(X)| para cualquier constante c.

Y aquí se puede encontrar un ejemplo de la prueba para el caso discreto:
https://stats.stackexchange.com/questions/7307/mean-and-median-properties/7315#7315

Answer 5

Se me ha pinchado por el mismo problema desde hace algún tiempo. La solución es el consenso obvio dado en publicaciones anteriores: encuentre la mediana (mx, my) de forma independiente y luego encuentre el punto más cercano en los N puntos dados y ese es el lugar de reunión. Para ver por qué esta es realmente la solución, primero debes considerar la distancia.

d = sum (| xi-x |) + sum (| yi-y |) sobre todo 1 < = i < = N,

que es independiente en x e y. Por lo tanto, podemos resolver el caso 1-D para xey. Voy a omitir la explicación dada ^^ y por lo tanto concluir que (mx, mi) es la mejor solución si tenemos en cuenta todos los puntos posibles.El mayor desafío es demostrar que podemos pasar de (mx, my) a la más cercana (xi, yi) tal que (xi, yi) es uno de los puntos dados, sin cambiar (aumentar) la distancia. La prueba dice:

Considere que hemos ordenado las coordenadas x (a modo de prueba) y que X1<X2<...<Xn. También Xj<mx<X(j+1) donde j = N/2, ahora vamos a mover mx un paso hacia la izquierda, es decir mx' <- mx-1. Por lo tanto, d' = |X1-mx+1| + .. + |Xj-mx+1| + |X(j+1)-mx+1| + .. + |Xn-mx+1| Sabemos que mx-1 aumentará los valores N/2 (para k> = j + 1 y disminuirá para < = j) por lo que el efecto es el mismo. Por lo tanto (mx-1, my) da la misma solución . Significa que hay un espacio entre Xj<mx<X(j+1) y Yj<my<Y(j+1) donde la distancia no cambia. Por lo tanto, podemos encontrar el punto más cercano que es la respuesta.

He ignorado el caso sutil de nodos pares/impares, pero espero que las matemáticas funcionen cuando se den cuenta de la prueba básica.

Esta es mi primera publicación, ayúdame a mejorar mis habilidades de escritura.

Answer 6

Su problema se llama Optimal Meeting Point Finding. El siguiente artículo proporciona un algoritmo aproximado eficiente http://www.cse.ust.hk/~wilfred/paper/vldb11.pdf