Você usou um algoritmo de caixeiro-viajante para resolver um problema?
https://stackoverflow.com/questions/264050
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estudei TSP na faculdade no contexto de NP completude. Eu nunca realmente tinha uma situação em que se aplica a um problema prático. Um pouco de pesquisa mostra que ele tem sido usado para escolher o caminho mais barato para mover uma broca ao redor, que está a fazer furos em placas de circuito. Isso é muito bonito tudo o que eu poderia encontrar.
Você está usando isso? Que outras aplicações práticas é que a TSA tem?
Solução
Tal como acontece com os outros neste tópico eu construí uma solução para um problema NP completo na faculdade (que era um projeto paralelo para um amigo) - um programa de agendamento. No momento em que eu concordei em trabalhar em seu problema que eu não sabia o que NP completa foi. Mais tarde eu percebi que tinha chegar a alguns razoavelmente bons heurística para resolver o problema - mas é claro que o verdadeiro truque foi saber quando dizer ao usuário que não havia solução e eles tinham sobre-restrita do problema.
Foi uma ótima maneira de reunir meus eventuais aulas teóricas eo mundo real.
Mais uma vez, heurísticas e "perto o suficiente" são geralmente bem para usos do mundo real onde as soluções quase ótimas são preferidas por causa do custo de encontrar e implementar a solução ideal.
Outras dicas
I já foi dada a tarefa de escrever um programa para preencher uma área retangular de forma bastante uniforme com um "rabisco" - uma linha curva que não faz auto-intersecção. Minha primeira tentativa foi para gerar pontos aleatórios dentro do retângulo e tentar encontrar uma turnê deles (não necessariamente o mais curto absoluto). Infelizmente esta abordagem simplesmente não funciona muito bem e eu abandonei ele.
Eu fiz resolver o problema no final, porém:
O meu método de sucesso não estava relacionada com a TSP mas para os curiosos vou resumi-lo:
Comece com um único segmento de linha. Agora loop: se uma linha é "muito longo", dividi-lo em dois. Mova cada ponto um pouco ao acaso, mas pontos fazem repelem. Termine o laço quando pouco progresso pode ser feito. Há detalhes, mas espero que você começa a idéia.
Claro que isso produz um caminho angular (que teria sido aceitável), mas é fácil transformar os cantos em arcos suaves.
E sim, eu mantive o código.
Eu nunca usei pessoalmente, mas outro aplicativo além de perfurar placas de circuito é se você quer ir para um número de lugares diferentes, dizem vender aspiradores. Você pode usar uma solução do problema para decidir a forma mais barata para visitar todos os lugares exatamente uma vez.
Saber quando um problema é NP-hard é útil para excluir soluções envolvendo resolver esse problema. Sempre que você vê TSP (ou qualquer outro problema NP-hard) elevar sua feia cabeça para problemas de tamanho não-trivial você sei você está indo para o caminho errado. Não só você sabe, mas você sabe por , e pode confiantemente dizer ao seu chefe / companheiro / ninguém.
Dito http://en.wikipedia.org/wiki/CONCORDE revela que :
Concorde foi aplicada a problemas de mapeamento de genes, a função da proteína [1] predição, [2] encaminhamento veículo, [3] conversão de imagens bitmap para desenhos de linha contínua, [4] movimentos de navios de agendamento para sísmica levantamentos, [5] e no estudo da escamação propriedades de combinatória problemas de otimização. [6]
Sim, eu usá-lo em aplicação Geocaching para o planeamento da rota.
Atualmente, usa uma distância em linha reta entre os pontos, mas deve corretamente (quando eu chegar ao redor dele) de uso de estradas para calc as distâncias entre pontos.
Na maioria das vezes você não quiser usar um algoritmo que resolve o NP-Completo / problema difícil. Você só quer um algoritmo que é "bom o suficiente". Estes são geralmente baseados em heurística e dar aproximações razoáveis.
Eu tinha um problema que era uma instância de Independent-Set (NP-completos), mas eu encontrei um algoritmo guloso que deu resultados muito bons na grande maioria dos casos, e tinha um tempo de execução eficiente.
Muitos tipos de ordenação otimizado, como captador piscina carro, entrega de pacotes UPS, etc., sempre que os requisitos nó de passagem pode ser expresso em uma dimensão de esforço, como o tempo ou a distância.
TSP é a Olá Mundo de NP problemas completos. Em sua forma canônica puro, você não vai encontrá-lo em estado selvagem, muitas vezes ( demos como este não incluído ), mas um grande subconjunto de NP problemas completos estão relacionados ou mesmo com base no TSP, tais como:
- Veículo roteamento (inclui caminhão de abastecimento de roteamento)
- roteamento Airline / vôo
- roteamento Train
- Ski roteamento inclinação máquina arado
Cada um deles tem extra, restrições específicas de domínio, que os tornam mais difícil de resolver. Então TSP é uma boa introdução para NP problemas completos, para compreender sua natureza.
Poucos problemas na vida real coincidir com as coisas que você aprende na aula de matemática. Os problemas são simplificadas e abstraídas para que você possa ver a matemática e não se distrair com detalhes. O melhor exemplo da vida real de grandes TSPs, como você mencionou, na verdade não envolve qualquer caixeiro-viajante: envolve máquinas de agendamento que têm empregos para executar com tempos de preparação dependentes da sequência . Isso inclui máquinas onde um braço se move uma ferramenta em torno de diferentes locais, e também algumas aplicações de pintura (vermelhos> laranja-> amarelo é mais fácil do que vermelhos> amarelo-> laranja). Há também algumas aplicações em cristalografia de raios X onde você tem que orientar alguma amostra de um cristal em vários ângulos diferentes.
Esta empresa foi baseado em um algoritmo TSP melhorado.
Eles instaladores de TV a cabo rota e reparadores em torno NYC entre outros problemas.
Porque os seres humanos geralmente pode resolver problemas TSP a par ou melhor do que a maioria dos algoritmos para mapas com 20-60 nós, não é muito comum ter um computador resolver o problema. Quando o custo é alto o suficiente, tendo o computador obter uma melhoria de 1-2% ao longo de um ser humano pode valer a pena o custo de realizar o cálculo. Se a rota não muda, então pode-se justificar gastar algum tempo otimizando-o. Isso é comum em design de circuitos integrados.
Airline sites de viagens usar uma versão especializada do problema TSP quando o show-lhe uma lista de companhias aéreas e os preços para cada rota. A diferença é em vez de distância, eles otimizar o custo, e certamente não há nenhuma exigência para visitar cada cidade uma vez! Digamos que você queira voar a partir de LGA para LAX. Há cerca de 1/2 dúzia de rotas diretas, e um número infinito de outras rotas. Ele pode sugerir LGA-> ORD-> LAX ou LGA-> DWF-> LAX. Os seres humanos, que podem manualmente rotas de preços às vezes pode encontrar tarifas mais baixas que os procurou pelos sites de viagens. Normalmente, as pessoas não querem mais de duas conexões, mas não há um limite para o número de conexões para um determinado vôo.
Eu usei-o para resolver rotas para o meu do Caixeiro Viajante do iPhone do jogo . O que é interessante é que as pessoas são muito bons em resolver a rota mais curta, mas não resolver o caminho mais longo. As rotas mais longas e mais curtas têm a mesma complexidade, mas as pessoas parecem treinados para ser capaz de encontrar rotas mais curtas, muitas vezes mais rápido e melhor do que o que um computador pode fazer.
No meu primeiro emprego foi construído um aplicativo de agendamento de atendimento domiciliar.
Nós resolvemos o problema TSP com algumas limitações de tempo não lineares e com uma função de custo não linear adicional.
Usamos um solver não ideal para resolver o problema.
não iria Google Maps (e todos os outros Mapa baseada em software de roteamento) estar usando algum tipo de caixeiro viajante para resolver direcções de condução?
Eu não usei TSP, tanto quanto eu sei, mas eu tenho trabalhado em uma série de robôs autônomos para percorrer um labirinto. Então eu pergunto se TSP poderia ser aplicada a maze problemas.
