Como calcular a rota mais eficiente que passa por todas as casas do mundo?

52

Eu sou novo no GIS.

Preciso de ajuda para determinar a melhor ou mais eficiente rota, usando um trenó voador, por todas as casas do mundo. Um dos meus colegas de trabalho me disse que este site seria o melhor lugar para perguntar, porque eu encontraria muitos especialistas em GIS úteis.

Vou precisar de algumas orientações sobre qual software usar, onde obter os dados e como processá-los. Como eu tive algumas despesas extras este mês, prefiro algumas soluções de código aberto.

Obrigado a todos!

PS: Estou com pressa, pois preciso disso para amanhã!

open-source-gis routing Papai Noel
fonte
20
Este é basicamente o Problema do Vendedor Viajante que, a menos que você esteja disposto a usar uma heurística, tem n! complexidade tão boa sorte encontrar qualquer solução para tantos n antes que o universo acabe ...
Smalltown2k
7
Espere, desde quando apenas crianças cristãs recebem visitas de Papai Noel?
21812 Steve Bennett
4
Vamos apenas assumir que o Sr. Claus tem uma lista de limites para visitar e mantê-la não-denominacional. Obrigado :)
blah238
9
Essa rota também está restrita a começar no Polo Norte? Pólo geográfico norte ou pólo magnético norte?
Spacedman
3
Assim. O primeiro passo é reunir um conjunto de dados para todos os locais de habitação do mundo. Alguém gostaria de postar um link da caixa de depósito?
Simon

Respostas:

25

Espere, certamente Rudolph sabe para onde ir. Ele faz isso há anos.

Andrew
fonte
16

Muitas vezes, é bom atender à necessidade mencionada, em vez de responder à pergunta que foi feita. Gostaria apenas de salientar que existe uma solução paralela bem conhecida que contorna claramente todos os problemas técnicos da computação: o Papai Noel tem ajudantes. Esses agentes trabalham de forma assíncrona e independente para identificar as casas que precisam de visitas e realizar as entregas. Nenhum cálculo GIS especial por parte do Papai Noel é necessário.

É maravilhoso que essa tecnologia seja dimensionada, de modo que, à medida que a população (cristã) do mundo se expandiu em várias ordens de grandeza ao longo dos milênios, a capacidade do Papai Noel de cumprir suas tarefas nunca esteve seriamente em dúvida: o número de ajudantes disponíveis aumentou. proporção direta ao número de casas que precisam de visitas.

Há uma demonstração física da existência desses ajudantes. Se, para assumir o contrário, apenas um indivíduo tentasse entregar presentes para, digamos, um bilhão de habitações ao longo de um dia do calendário (que se estende por 48 horas, representando fusos horários), teria que visitar quase 6 mil residências por segundo . Um limite inferior para a distância média entre habitações é proporcionado pela densidade das grandes cidades do mundo, nas quais as pessoas podem viver apenas a 10 metros ou mais. Isso exigiria uma velocidade média de 6000 x 10 = 60.000 metros por segundo, superando em muito a barreira do som (criando barulhos sônicos que não sãoouvida no Natal) e criando tanta fricção atmosférica que o trenó se tornaria uma bola de fogo ardente, destruindo tudo nas proximidades. Embora isso nos dê uma nova compreensão da origem do brilho vermelho no nariz de Rudolph, demonstra claramente que apenas uma solução paralela é possível, QED.

whuber
fonte
11
Caso você não acredite nos ajudantes, aqui está a prova: en.wikipedia.org/wiki/Prep_%26_Landing
Tobias Kienzler
6

Este é algo que você provavelmente pode resolver usando a do Warshal ou de Dijkstra algoritmo

Embora o número de casas no mundo seja muito grande, levaria muito tempo para calcular isso, acho que esse é um bom ponto inicial. Agora não tenho tempo para explicá-las, mas eu lhe dou um ponto inicial. Vou sair com minha família agora e talvez volte a essa pergunta no próximo ano.

Roger
fonte
4
Obrigado pelas amáveis ​​palavras. Mas: (1) Como esses algoritmos resolveriam esse problema do vendedor ambulante? (2) O algoritmo de Dijkstra (para encontrar caminhos mais curtos entre dois pontos dados em uma determinada rede ) é rápido. Aplicá-lo a um conjunto de dados de todas as habitações do mundo, se fosse adequadamente podado para incluir arestas apenas para vários vizinhos mais próximos de cada habitação, não seria apenas viável, mas razoavelmente rápido - provavelmente precisando apenas de segundos ou minutos de computação.
whuber
2

Parece que o Google já descobriu isso para você, Papai Noel! Na verdade, você deveria estar na Ásia no momento!

http://www.google.com/santatracker/

Matt
fonte
0

Com um conjunto de dados que contém a latitude e longitude de cada habitação (dados do censo?), Talvez eu usasse a fórmula Haversine em uma linguagem de programação ou outra. Mas, novamente, eu não sou um elfo.

Fórmula de Haversine

Natrix
fonte
Se você estiver no ar, certamente terá que levar em consideração a redondeza da terra e sua altitude.
Natrix