¿Cómo calcular la ruta más eficiente que pasa por todas las casas del mundo?

52

Soy nuevo en SIG.

Necesito ayuda para determinar la ruta mejor o más eficiente, utilizando un trineo volador, a través de todas las casas del mundo. Uno de mis compañeros de trabajo me dijo que este sitio sería el mejor lugar para preguntar, porque encontraría muchos expertos en SIG útiles.

Necesitaré alguna orientación sobre qué software usar, dónde obtener los datos y cómo procesarlos. Como tuve algunos gastos adicionales este mes, preferiría algunas soluciones de código abierto.

¡Gracias a todos!

PD: ¡Tengo un poco de prisa, ya que necesito esto para mañana!

Papá Noel
fuente
20
Esto es básicamente un problema de vendedor ambulante que, a menos que esté dispuesto a usar una heurística, tiene n complejidad así que buena suerte encontrando cualquier solución para esa cantidad de n antes de que el universo termine ...
Smalltown2k
77
Espera, ¿desde cuándo solo los niños cristianos reciben visitas de Santa?
Steve Bennett
44
Supongamos que el Sr. Claus tiene una lista de hogares para visitar y que no sea confesional. Gracias :)
blah238
99
¿Esta ruta también está limitada para comenzar en el Polo Norte? Polo geográfico norte o polo norte magnético?
Spacedman
3
Entonces. El primer paso es reunir un conjunto de datos para todas las ubicaciones de viviendas del mundo. ¿A alguien le importa publicar un enlace de Dropbox?
Simon

Respuestas:

25

Espera, seguramente Rudolph sabe a dónde ir. Lo ha estado haciendo por años.

Andrés
fuente
16

A menudo es bueno abordar la necesidad que se establece en lugar de responder a la pregunta que se hizo. Solo me gustaría señalar que existe una solución paralela bien conocida que evita todos los problemas técnicos de computación: Santa tiene ayudantes. Estos agentes trabajan de forma asíncrona e independiente para identificar las casas que necesitan visitas y realizar las entregas. No se necesita ningún cálculo GIS especial por parte de Santa.

Es maravilloso que esta tecnología se amplíe, de modo que a medida que la población (cristiana) del mundo se ha expandido en varios órdenes de magnitud a lo largo de los milenios, la capacidad de Santa de cumplir con sus obligaciones nunca ha estado seriamente en duda: la cantidad de ayudantes disponibles ha aumentado. proporción directa al número de casas que necesitan visitas.


Hay una demostración física de la existencia de estos ayudantes. Si, por suponer lo contrario, solo una persona tratara de entregar obsequios a, digamos, mil millones de viviendas en el transcurso de un día calendario (que abarca 48 horas, contabilizando zonas horarias), tendrían que visitar casi 6000 viviendas por segundo . La densidad de las ciudades más grandes del mundo, en las cuales las personas pueden vivir a solo 10 metros de distancia, proporciona un límite inferior para la distancia media entre viviendas. Esto requeriría una velocidad promedio de 6000 * 10 = 60,000 metros por segundo, superando con creces la barrera del sonido (creando auges sónicos que no sonescuchado en Navidad) y creando tanta fricción atmosférica que el trineo se convertiría en una bola de fuego ardiente que destruiría todo en su proximidad. Aunque esto nos da una nueva comprensión del origen del resplandor rojo en la nariz de Rudolph, demuestra claramente que solo es posible una solución paralela, QED.

whuber
fuente
1
En caso de que no creas en los ayudantes, aquí está la prueba: en.wikipedia.org/wiki/Prep_%26_Landing
Tobias Kienzler
6

Esto es algo que probablemente puede resolver mediante el uso de la de Warshal o Dijkstra algoritmo

Aunque el número de casas en el mundo es demasiado grande, tomaría mucho tiempo calcularlo, creo que este es un buen punto inicial. Ahora no tengo tiempo para explicarlos, pero les doy un punto inicial. Saldré con mi familia ahora y tal vez volveré a esta pregunta el próximo año.

Roger
fuente
44
Gracias por las amables palabras. Pero: (1) ¿Cómo resolvería cualquiera de esos algoritmos este problema de vendedor ambulante? (2) El algoritmo de Dijkstra (para encontrar los caminos más cortos entre dos puntos dados en una red dada ) es rápido. Aplicarlo a un conjunto de datos de todas las viviendas del mundo, si se podara adecuadamente para incluir bordes solo a varios vecinos más cercanos de cada vivienda, no solo sería factible, sino razonablemente rápido, probablemente solo necesitaría segundos o minutos de cálculo.
whuber
0

Con un conjunto de datos que contiene la latitud y la longitud de cada vivienda (¿datos del censo?), Tal vez usaría la fórmula de Haversine en un lenguaje de programación u otro. Pero, de nuevo, no soy un elfo.

Fórmula Haversine

Natrix
fuente
Si estás en el aire seguramente deberías tener en cuenta la redondez de la tierra y tu altitud.
Natrix