Geocaching trivia

[geo-amd]

A solução só pode ser obtida usando a habilidade e intuição humanas. O problema proposto é uma instância do clássico problema do caixeiro viajante e prova-se que não existe solução geral por computador que resolva o problema em tempo útil. A solução por computador mais básica consiste em testar todas as permutações das 28 caches:

Código: Selecionar todos

28! = 304888344611713860501504000000 permutações

Se cada permutação demorar um milissegundo a ser testada, o programa demora 9667945985911778 milénios a correr. Eis uma animação deste algoritmo de "força bruta" a funcionar (só para 7 caches):



Para resolver o problema à mão, por tentativa e erro, primeiro é preciso construir a tabela de distâncias, 28x28. A fórmula que dá a distância em km entre duas coordenadas está aqui, em várias linguagens haversine. Deve ser fácil traduzir para o Excel.

Para já não tive tempo para mais...

[jasafara]

Muita matemática...!
Vou tentar chegar à solução a olhómetro

[allien]

Posso estar enganado e/ou não ter percebido a coisa...
Mas num GPS com mapas "navegáveis" e que permitisse a colocação de pontos intermediários, não se conseguiria obter a rota mais curta?

[rifkinda]

Existem GPS que calculam realmente a rota mais curta, usando pontos intermediários. Mas apenas, para um número bastante pequeno de pontos (acho que a partir de 10 pontos intermédios, o meu GPS já estoura) e tens de fixar o ponto inicial e final da rota.
Ora aqui para as Lusitani, terias de fazer com 28 pontos iniciais (o ponto final é o mesmo, na a questão do jasafara ele falava em percurso circular).
Além disso na pergunta dele, ele falava na distância mais curta entre dois pontos, que é um segmento de recta (o que significava que ias fazer as lusitanis a pé, a direito, atravessando tudo o que te aparecesse no caminho), e não a distância mais curta por estrada.

O geo-amd tem toda a razão nos cálculos que fez. E o jasafara apesar de trabalhar num banco (pelo menos foi o que me constou) e lidar com números diariamente, não parece que saiba bem no que se estava a meter quando perguntou o que perguntou...
Ele até sabe fazer uma estatísticas e tecer uns comentários sobre os resultados, ... mas está a precisar de estudar um pouco de Combinatória!

[jasafara]

...
O geo-amd tem toda a razão nos cálculos que fez. E o jasafara apesar de trabalhar num banco (pelo menos foi o que me constou) e lidar com números diariamente, não parece que saiba bem no que se estava a meter quando perguntou o que perguntou...
Ele até sabe fazer uma estatísticas e tecer uns comentários sobre os resultados, ... mas está a precisar de estudar um pouco de Combinatória!

Cara Rita. Sabia perfeitamente no que me estava a meter
Foi há muitos anos mas estudei Análise Combinatória, Investigação Operacional e essas coisas.
Conheço perfeitamente o problema do caixeiro viajante e as complexidades associadas.
De qualquer forma existem técnicas que não passam pela enormidade de combinações possíveis e que permitem simplificar o problema.
Mas não tenho a pretensão de que se chegue a uma solução que se possa afirmar que é a mais curta.

Assim reformulo a questão. Ganha a trivia quem daqui a uma semana (até às 24h de dia 28/2) apresente a rota google maps com menos km's
Eu próprio estou na disputa!

[jasafara]

Além disso na pergunta dele, ele falava na distância mais curta entre dois pontos, que é um segmento de recta (o que significava que ias fazer as lusitanis a pé, a direito, atravessando tudo o que te aparecesse no caminho), e não a distância mais curta por estrada.

Eu pedi para se dar o resultado com o link google maps. Acrescento com rota por carro.
E a distãncia mais curta entre dois pontos de uma superfície esférica (ou aproximadamente) não é um segmento de recta, mas sim uma Geodésia.
Precisas de estudar um pouco mais de matemáticas não eucledianas

[allien]

Alguém que traduza, sff. ! )

[jasafara]

A formulação do problema é muito simples.
Não precisas de saber Teoria de Grafos nem o que é um problema NP-Completo, para o procurares resolver

[allien]

A formulação do problema é muito simples.
Não precisas de saber Teoria de Grafos nem o que é um problema NP-Completo, para o procurares resolver

Ainda bem! Fico muito mais descansado...

[jasafara]

A formulação do problema é muito simples.
Não precisas de saber Teoria de Grafos nem o que é um problema NP-Completo, para o procurares resolver

Ainda bem! Fico muito mais descansado...

Só me estou a meter com a Rita
Pensa que querias organizar uma visita a todas as Lusitani e que querias fazer o menor número de kms possíveis. Pode-se fazer isso com mais ou menos matemática associada.
O que foi referido é que um problema com a quantidade de pontos como o requerido (28) está para lá das capacidades dos computadores actuais se utilizarem algoritmos obsolentos baseados na força bruta (e que são os utilizados possívelmente pelos GPS...)

[geo-amd]

Claro que o Jasafara sabia do que estava a falar.

Eu só quis dar um primeiro passo, digamos numa tentativa de resolução coletiva, além de que não resisti a referir que este é um problema com a qualidade especial de só ser acessível a humanos habilidosos e não a máquinas.

Só não percebi, e por isso ignorei, a referência ao Google. Estive agora a ver e não sei como obter a distância mais curta entre dois pontos no Google Maps. No Google Maps só sei navegar na imagem, fazer zoom, coisas dessas...

EDIT: Corrigi dois erros ortográficos.

[geo-amd]

... está para lá das capacidades dos computadores actuais se utilizarem algoritmos obsolentos baseados na força bruta...

... além de que demonstra que não é possível inventar algoritmos que resolvam o problema em tempo útil. A única esperança é esperar pelos computadores quânticos, que mudam a definição do que é "computação".

[jasafara]

Claro que o Jasafara sabia do que estava a falar.

Eu só quis dar um primeiro passo, digamos numa tentativa de resolução coletiva, além de que não resisti a referir que este é um problema com a qualidade especial de só ser acessível a humanos habilidosos e não a máquinas.

Só não percebi, e por isso ignorei, a referência ao Google. Estive agora a ver e não sei como obter a distância mais curta entre dois pontos no Google Maps. No Google Maps só sei navegar na imagem, fazer zoom, coisas dessas...

EDIT: Corrigi dois erros ortográficos.

O google maps calcula-te percursos não necessáriamente optimizados entre dois pontos. No entanto para as lusitanis ele só te indicará uma quilometragem baseada na ordem em que tu introduzas as coordenadas (que terás de tentar que seja a melhor por qualquer outro método...).
O ter pedido para aqui colocar um link da rota gerada é só para facilidade de comparação/comprovação de resultados.
Se tu te metes a tentar resolver isso com programação, sem ter em conta as estradas reais seria um problema mais matemático mas que já vimos que não tem solução. Assim a solução passará mais por pelo menos numa fase inicial por uma análise visual do problema e depois efectuar simulações no google maps.

[geo-amd]

Só agora percebi! Pensei que era um desafio matemático meio abstrato mas afinal envolve distâncias por estrada. Eu estava a tentar dar contributos para se tentar resolver problema que afinal não tinha percebido! De facto, é preciso usar dados baseados em mapas e a fórmula haversine não é aqui chamada.

De qualquer forma, uma ligeira correção ao que dizes atrás: Os dois problemas (por estrada e em linha reta) têm solução. O que não é possível é inventar algoritmos genéricos que permitam descobrir essas soluções em tempo razoável.

[jasafara]

Só agora percebi! Pensei que era um desafio matemático meio abstrato mas afinal envolve distâncias por estrada. Eu estava a tentar dar contributos para se tentar resolver problema que afinal não tinha percebido! De facto, é preciso usar dados baseados em mapas e a fórmula haversine não é aqui chamada.

De qualquer forma, uma ligeira correção ao que dizes atrás: Os dois problemas (por estrada e em linha reta) têm solução. O que não é possível é inventar algoritmos genéricos que permitam descobrir essas soluções em tempo razoável.

Mas como disse é baseado em mapas, mas tens de orientar o google maps. Ele só te cria um percurso mais ou menos optimizado entre dois pontos (mas que no entanto podem ter muito mais de 28 conexões possíveis pelo que deve utilizar um algoritmo relativamente sofisticado). Tens de ser tu a indicares a ordem pela qual ele liga as lusitanis...
E a tua introdução teórica foi muito interessante

edit: A fórmula haversine é para aqui chamada, mas está imbuída nos algoritmos de cálculo de rota do google maps...