Otimização de algoritmo – rota mais curta entre vários pontos

StackOverflow https://stackoverflow.com/questions/1511585

Pergunta

Problema:Eu tenho uma grande coleção de pontos.Cada um desses pontos possui uma lista com referências a outros pontos com a distância entre eles já calculada e armazenada.Preciso determinar a rota mais curta que começa em uma origem e passa por um número específico de pontos até qualquer destino.

Ex:Estou de férias e vou ficar em uma cidade específica.Estou fazendo uma viagem SÓ DE IDA para conhecer QUALQUER quatro cidades e quero viajar a menor distância possível.Não posso visitar a mesma cidade mais de uma vez.

Solução atual:No momento, estou apenas percorrendo todas as possibilidades manualmente e armazenando o caminho mais curto.Isso funciona, mas parece ineficiente.Além disso, esse problema será eventualmente expandido para incluir a pesquisa de vários pontos de origem para vários pontos de destino, então acho que isso pode explodir o espaço de pesquisa.

Qual é a melhor maneira de procurar o caminho mais curto?

Foi útil?

Solução

Respondendo à postagem atualizada, sua solução de verificar todas as possibilidades é ótima (pelo menos ninguém descobriu algoritmos melhores até agora).Sim, esse é um caixeiro-viajante, cuja essência não é tocar todas as cidades, mas sim tocar todas as cidades uma vez.Se você não quiser procurar a melhor solução possível, poderá achar útil usar heurísticas que funcionam mais rápido, mas permitem discrepâncias limitadas da solução ideal.

Para futuros respondentes: Algoritmo Floyd-Warshall e todas as variações do tipo Floyd são inaplicáveis ​​aqui.

Outras dicas

Geralmente, você deve ser rigoroso variantes ruins ... acho que você deve usar algumas variações do método de ramo_and_boundhttp://en.wikipedia.org/wiki/branch_and_bound

Ou a primeira pesquisa da Bredth como Norheim.se disse ou Algoritmo de Dijkstra Seria minha sugestão também.

Isso soa como vendedor viajante? Uma solução é usar uma técnica de otimização, como um algoritmo evolutivo. Atualmente, você está fazendo uma pesquisa exaustiva, que ficará muito lenta muito rapidamente. Mas acho que esse é um problema de vendedor ambulante e foi abordado por várias décadas, se não séculos, e existem várias maneiras possíveis de ataque. Google é seu amigo.

Talvez seja isso que o pôster original significa "iterando através de cada possibilidade manualmente e armazenando o caminho mais curto", mas pensei em tornar explícito o que parece ser uma solução de linha de base.

Suponha que você já tenha um algoritmo de caminho mais curto de dois pontos-isso possui soluções clássicas para vários tipos de gráficos. Suponha que todas as distâncias não sejam negativas e d (a-> b-> c) = d (a-> b) + d (b-> c).

Os itens essenciais são que o caminho começa em S passa por uma das cidades intermediárias "ABCD" e termina com E:

por exemplo, sabcde, sacbde, etc ...

Com apenas 4 cidades intermediárias, você enumora todas as 24 permutações. Para cada permutação, use seu algoritmo de dois pontos mais curto para calcular o caminho da cabeça para a cauda e sua distância total.

Em seguida, dado o ponto de partida e final, existem 12 possibilidades ligadas a uma de ABCD e para cada duas possibilidades para o interior. Você já calculou essas distâncias, então adiciona a distância de S à cabeça e a cauda para E. Escolha o mínimo. Portanto, depois de pré -computar as distâncias intermediárias para um conjunto fixo de cidades do interior, você precisa fazer 12 problemas de caminho mais curto de dois pontos para qualquer par de pontos de partida e final.

Obviamente, isso escala mal com um número crescente de cidades intermediárias. Não está claro para mim que isso possa fazer melhor, a menos que você impor mais restrições à estrutura do gráfico (isso está em um espaço físico da Euclidenan? Desigualdade do triângulo?).

Meu exemplo de pensamento: suponha que todas as distâncias intermediárias entre as cidades sejam O (1). Sem restrição no gráfico, a distância de S para qualquer cidade intermediária pode ser de 1000, exceto que um é 1. O mesmo para a cauda. Assim, você pode forçar a primeira cidade a ser visitada para ser qualquer coisa. Agora, vá uma camada, pegue a primeira cidade como o "ponto de partida". Aplique o mesmo argumento: você pode fazer o melhor caminho para qualquer uma das seguintes cidades manipulando as distâncias no gráfico.

Parece que a complexidade não pode ser ajudada sem suposições adicionais.

Esta é a situação muito comum e em tempo real que alguém pode cair. O Map do Google Interface do Usuário fornece o caminho na mesma ordem, você adiciona na lista de destino. Não fornece o caminho ideal, embora sua própria API do Google Maps forneça a solução.

A API do Google Maps fornece a solução para isso. Na solicitação para descobrir o caminho, você deve fornecer o sinalizador 'otimizewaypoints: true'. O pedido parecerá assim.

var request = {
            origin: start,
            destination: end,
            waypoints: waypts,
            optimizeWaypoints: true,
            travelMode: google.maps.TravelMode.DRIVING
        };

E você pode ver todo o código do utilitário na fonte de exibição como utilitário completo é desenvolvido em JavaScript e HTML.

Eu espero que isso ajude.

Parece que as bordas do seu gráfico são bidirecionais. Nesse caso, o algoritmo que você está procurando é Algoritmo de Dijkstra.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top