Geocaching@pt

Uns patuscos dos EUA decidiram fazer por estrada a mais rápida viagem que "visitasse" todos os 48 estados contíguos:

http://greatamericanroadtrip.us/

Demoraram 106 horas e 43 minutos, começando no Vermont e terminando perto da quádrupla fronteira AZ/NM/UT/CO.

Do ponto de vista algorítmico o problema de determinar o caminho mais rápido sujeito à visita dos 48 estados não tem solução "fácil" (a quem interessar digo o nome do problema), pelo que a viagem foi estudada com mapa, e o percurso definido à mão. Tiveram ainda de fazer telefonemas para as autoridades locais para saber os limites de velocidade, o estado das estradas, etc., antes de pôr rodas ao caminho.

Levaram um GPS Magellan, para verificar se o carro (e eles) esteve de facto em todos os 48 estados. Fizeram 11278 km, viram 90 "cops" e receberam 3 números de telefone de moças entusiastas.



É claro que nestes tempos de alta do preço dos combustíveis é politicamente incorrecto pensar em extravagâncias destas, mas como será o mapa para visitar os 18 distritos do nosso território continental?

O percurso daria pelo menos para semear umas caches alusivas ao tema!

Há malucos para tudo!

Ou, como diria o Obelix, "Estes americanos são malucos"!

Ainda há dias estava a pensar nisso! Nisso, no algoritmo que calcule a viagem. Sei que faz ( ou fazia) parte de qualquer currículo do curso de Informática, fazer essa programação. Algo tipo " caixeiro viajante"...

Isso daria muito jeito para calcular uma tarde de geocaching.

Colocavamos as coordenadas das caches e, baseado na cartografia existente, nos diria o caminho optimizado.

Isso é possível?

Abreijos!

Sim. Os programas de navegação automóvel fazem isso. Só conheço bem o CoPilot e com ele posso;

Introduzir várias coordenadas/pontos de paragem, guardar como viagem e pedir para optimizar. Ele calcula os melhores percursos para vários tipos de veículo (carro, caravana, bicicleta ou a pé) e de dois possíveis modos (mais rápido ou mais curto). Depois é iniciar a deslocação e ele vai reconhecendo automaticamente a passagem por cada um deles e mudando para o proximo.

Penso que os concorrentes, TomTom e outros fazem o mesmo com um ou outro pormenor diferente.

Eu tive de marrar no algoritmo de Dijkstra e devo dizer que não é pêra doce o filho da mãe.

Acho que já existem algoritmos muito mais eficientes, mas na altura foi o que melhor me resolveu o problema e o melhor da festa é que nada tinha a ver com o traçado de rotas.

Se algem desejar a função de Dijkstra em C++ eu tenho-a.

Com o meu CSx é que não dá..

Apenas para os curiosos:

Código: Selecionar todos

STDMETHODIMP CDijkstra::ShortestPath(long node1, long node2)
{
    // Inicializações
    InitializeSource(g, g.m_nodes[node1-1]);
    VTYPE_NODE S;
    VTYPE_NODE Q;
    VTYPE_NODE::iterator kl;
    for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++)
    {
        CNode node = (*kl).Copy();
        Q.push_back(node);
    }

    // aqui é que está o algoritmo propriamente dito
    while(Q.size())
    {
        CNode nod = ExtractMin(Q); // menor valor para o percurso mais curto
        S.push_back(nod);

        // verificar cada vertice que seja vizinho de si
        VTYPE_NODE::iterator kl;
        for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++)
        {
            if(ExistEdge(nod, (*kl)))
            {
                bool gasit = false;
                VTYPE_NODE::iterator kll;
                for(kll=Q.begin(); kll<Q.end(); kll++)
                {
                    if((*kll).m_NodeNr == (*kl).m_NodeNr)
                    gasit = true;
                }
                if(gasit)
                    Relax(nod, (*kl), GetEdgeVal(nod, (*kl)));
            }
        }
    }
    RefreshDone(node1, node2);
    return S_OK;
}


Colocavamos as coordenadas das caches e, baseado na cartografia existente, nos diria o caminho optimizado.

Isso é possível?

Hã... Claro! O Quest sempre fez isso. Tens a certeza que o CSx não faz?

Estou a supôr que a interface de rotas seja semelhante nos dois receptores.
No CSx, experimenta criar uma rota.
Define o ínicio no ponto que quiseres e o fim igualmente.
Depois, adiciona os pontos das caches pelo meio.
Se carregares em Menu, deve aparecer um menu onde existem várias opções e uma delas é a ordem ideal de pontos.

Depois diz se bateu certo.
Nuno
Rifkindsss

genios_de_gibraltar Escreveu:....
Levaram um GPS Magellan,...
....

Meus caros, mas ainda há dúvidas?!?



Cláudio Cortez
..com um Magellan Meridian Platinum desde 2005..

Ainda este fim-de-semana vi na revista do Correio da Manhã um artigo de um gajo qualquer que mandou uma encomenda por correio (não prestei muita atenção qual foi o meio usado) com um GPSr lá dentro que gravou o percurso feito pela encomenda.
Resultado:
o percurso da encomenda revela o perfil do gajo... e é o record para o desenho com uma unica linha... Uma coisa qualquer assim...

ajsa Escreveu:Apenas para os curiosos:

Para os curiosos ou para quem teve a cadeira de Algoritmos e Estruturas de Dados relembrar alguma coisa.

MightyReek Escreveu: mandou uma encomenda por correio (...) com um GPSr lá dentro que gravou o percurso feito pela encomenda.
Resultado:
o percurso da encomenda revela o perfil do gajo... e é o record para o desenho com uma unica linha... Uma coisa qualquer assim...

Uma fraude do tamanho do desenho... veja-se a notícia-desmentido.

E se quiserem ver o tal desenho inventivo mas falso como Judas, encontram-no aqui.

Quanto ao algoritmo a usar NÃO É o de Dijkstra, e o problema NÃO É o do caixeiro viajante. Reparem que não têm pontos fixos, isto é, a "rede" mínima assenta sobre alguns vértices do grafo que define a estrutura, mas não todos.

rifkind Escreveu:

Colocavamos as coordenadas das caches e, baseado na cartografia existente, nos diria o caminho optimizado.

Isso é possível?

Hã... Claro! O Quest sempre fez isso. Tens a certeza que o CSx não faz?

Estou a supôr que a interface de rotas seja semelhante nos dois receptores.
No CSx, experimenta criar uma rota.
Define o ínicio no ponto que quiseres e o fim igualmente.
Depois, adiciona os pontos das caches pelo meio.
Se carregares em Menu, deve aparecer um menu onde existem várias opções e uma delas é a ordem ideal de pontos.

Depois diz se bateu certo.
Nuno
Rifkindsss

Olha!

Pois dá!!

Vou testar este fim de semana!! Muitos thanks!!

genios_de_gibraltar Escreveu:O percurso daria pelo menos para semear umas caches alusivas ao tema!

Já existem. Existem diversos "desafios" que englobam os 50 estados (incluiem Hawaii e Alaska), como por exemplo, a multi-cache que os atravessa e os Delorme Challenge.

Essa viagem é, naturalmente, de sonho.

SUp3rFM Escreveu:

genios_de_gibraltar Escreveu:O percurso daria pelo menos para semear umas caches alusivas ao tema!

Já existem. Existem diversos "desafios" que englobam os 50 estados (incluiem Hawaii e Alaska), como por exemplo, a multi-cache que os atravessa e os Delorme Challenge.

Essa viagem é, naturalmente, de sonho.

SUp3rFM, podes aqui indicá-las, só por curiosidade? Agradecido!