Não muito tempo atrás, uma equipe de pesquisadores da universidade de Stanford e da universidade de McGill universidades quebrou um dos 35 anos de registro em ciência da computação por uma quase imperceptível margem — quatro centésimos de um trilionésimo de trilionésimo de trilionésimo de trilionésimo de um por cento, para ser exato., O avanço-feito para aquela criança poster para difíceis de resolver quandaries de ciência da computação, o problema do” vendedor ambulante ” — era muito minúsculo para ter qualquer significado prático imediato, mas ele deu nova vida na busca por soluções aproximadas melhoradas.

*original story reprinted with permission from Simons Science News, an editorially independent division of SimonsFoundation.org cuja missão é melhorar a compreensão pública da ciência, cobrindo desenvolvimentos de investigação e tendências em matemática e ciências computacionais, físicas e da vida.,*O problema do caixeiro viajante pergunta: dada uma coleção de cidades conectadas por rodovias, Qual é a rota mais curta que visita cada cidade e retorna ao lugar de partida? A resposta tem aplicações práticas para processos como furos de perfuração em placas de circuitos, tarefas de agendamento em um computador e características de ordenação de um genoma.

Ver mais

O problema do caixeiro viajante é fácil para o estado, e — pelo menos na teoria — que pode ser facilmente resolvido com a verificação de que cada viagem de ida rota para encontrar o mais curto., O problema com esta abordagem da Força bruta é que à medida que o número de cidades cresce, o número correspondente de viagens de ida e volta para verificar supera rapidamente as capacidades dos computadores mais rápidos. Com 10 cidades, existem mais de 300.000 diferentes viagens de ida e volta__.__ Com 15 cidades, o número de balões possibilidades para mais de 87 bilhões.,

Christofides ” Algoritmo

No início da computação, matemáticos esperava que alguém venha com uma abordagem muito melhor para grandes problemas do caixeiro viajante — algoritmo de alguns que permitiria computadores para resolvê-los em uma quantidade razoável de tempo. Mas, enquanto os cientistas da computação têm feito progressos com cenários específicos — identificar o menor de ida percurso__ 49-mapa da cidade na década de 1950, um 2,392-mapa da cidade na década de 1980 e um 85,900-mapa da cidade em 2006 — ninguém desenvolveu um algoritmo que possa resolver todos os problema do caixeiro viajante., De acordo com um artigo de referência publicado em 1972, tal solução poderia nem sequer ser possível. O cientista da computação Richard Karp, da Universidade da Califórnia em Berkeley, __mostrou que o problema do Caixeiro Viajante é “NP-hard”, o que significa que não tem algoritmo eficiente (a menos que uma famosa conjectura chamada P=NP seja verdadeira — mas a maioria dos cientistas da computação agora suspeita que é falsa).

Depois de Karp o artigo foi publicado, muitos cientistas da computação definir suas vistas sobre a criação de um eficiente algoritmo para encontrar soluções aproximadas para o problema do caixeiro viajante — round-trip rotas cujos comprimentos estão dentro distância de percussão de que a melhor rota possível., Aqui, eles tiveram melhor sorte: em 1976, Nicos Christofides, um professor do Imperial College London, desenvolveu um algoritmo que produz rotas garantidas a ser no máximo 50 por cento mais longo do que a rota mais Curta.

Quando foi criado, muitos cientistas da computação assumiram que o algoritmo de Christofides, que é simples o suficiente para ensinar aos estudantes de ciência da computação em uma hora, era um substituto que eventualmente daria lugar a um algoritmo mais sofisticado capaz de aproximar melhor a verdadeira solução. No entanto, durante décadas, esse algoritmo não se materializou.,

“quase todos os estudantes de pós-graduação em Ciência da Computação Teórica passaram algumas semanas fúteis ou meses tentando melhorar o algoritmo de Christofides”, disse Sanjeev Arora, um cientista da Computação da Universidade de Princeton.

Finalmente, em 2011, o Stanford-McGill equipe bateu Christofides’ 50% de garantia para certos tipos de problemas do caixeiro viajante, mostrando que o seu algoritmo de soluções seriam no máximo 49.99999999999999999999999999999999999999999999999996% maior do que a verdadeira resposta.,

uma cadeia de algoritmos de aproximação melhorados surgiram desde então, depois que os cientistas da computação começaram a olhar para o problema com olhos frescos. Embora essas aproximações se apliquem apenas a certos tipos de problemas de vendedores ambulantes, a abordagem que eles incorporam mantém grande promessa, disse Michel Goemans, um cientista da computação do Massachusetts Institute of Technology.”mal arranhámos a superfície”, disse ele. “Acredito que, talvez cinco anos mais tarde, haverá um resultado muito mais poderoso.,”

the Shortest Tree

Christofides’ algorithm starts by looking not for the shortest round-trip route, but the shortest ” spanning tree — – a collection of branches linking the cities, with no closed loops. Ao contrário do caminho mais curto de ida e volta, a árvore de extensão mais curta é fácil de construir eficientemente: comece por encontrar a estrada mais curta que liga duas cidades; esse é o primeiro ramo. Para adicionar o ramo seguinte, encontrar a estrada mais Curta conectando uma nova cidade a um desses dois-e assim por diante até que todas as cidades tenham sido alcançadas.,

A árvore resultante não é uma solução possível para o problema do caixeiro viajante porque não cria uma rota de ida e volta. Mas pode ser convertido em uma viagem de ida e volta visualizando os galhos como paredes e, em seguida, imaginando caminhar ao longo da árvore, com seu dedo tocando a parede, até que você volte para onde você começou. A viagem resultante visita cada cidade e retorna ao ponto de partida, mas geralmente está longe do caminho mais curto para fazê — lo, porque normalmente envolve passos retraídos muitas vezes-cada parede na árvore é atravessada duas vezes, uma vez de cada lado.,

No entanto, esta rota de ida e volta é, na pior das hipóteses, duas vezes mais longa que a melhor solução para o problema do caixeiro viajante. Ao adicionar algumas auto-estradas cuidadosamente escolhidas a esta árvore e tomando alguns atalhos inteligentes, Christofides mostrou como cortar esta viagem de ida e volta para um que é no máximo 50 por cento mais longo do que o caminho mais curto.

A árvore mais curta foi um ponto de partida natural para os esforços para construir uma curta viagem de ida e volta., But this approach also offered an opening for researchers trying to whittle down Christofides ‘ 50 percent guarantee. Porque embora a árvore de extensão mais Curta pareça eficaz no início, outras árvores podem ser melhores quando se trata do processo de corte curto que converte a árvore em uma viagem de ida e volta-por exemplo, uma árvore que nunca se ramifica precisa apenas de uma estrada adicional para se tornar uma viagem de ida e volta.

então o objetivo era encontrar uma árvore que atingisse o equilíbrio perfeito entre comprimento e fácil conversão em uma viagem de ida e volta., Nenhum algoritmo eficiente pode descobrir esta árvore perfeita (a menos que P=NP), mas um algoritmo de aproximação bem sucedido só precisa encontrar uma muito boa.

Uma fração de Viagem

O caminho na direção do que “muito bom” spanning tree tem envolvido, que é amplamente utilizado, mas contraditório técnica de permitir fracionário soluções para certos tipos de problemas. Uma viagem de ida e volta fraccionada, por exemplo, pode envolver ir em metade da estrada de Minneapolis para Detroit e metade da estrada de Cleveland para Detroit. Essa via é, naturalmente, um disparate do ponto de vista prático., Mas pode ser formulado em termos matemáticos precisos, e, ao contrário do problema padrão do vendedor ambulante, esta versão fraccionada pode ser resolvida de forma eficiente.muitos problemas de aproximação na ciência da computação podem ser resolvidos calculando a solução para a versão fraccionada do problema e, em seguida, encontrando uma maneira inteligente de arredondar as frações para produzir uma solução aproximada para o problema original. Mas até recentemente, ninguém tinha descoberto uma boa maneira de fazer isso para o problema do caixeiro viajante.,

em 2009, Amin Saberi da Universidade de Stanford e Arash Asadpour, então um estudante graduado, desenvolveu uma técnica geral de arredondamento que usa aleatoriedade para tentar escolher uma solução de número inteiro que mantém tantas propriedades da solução fraccionada quanto possível. Saberi viu esta nova técnica de arredondamento como “um martelo forte à procura de um prego.”O prego certo, suspeitava ele, pode ser o problema do vendedor ambulante.,

alguns meses mais tarde, Saberi, Asadpour, Goemans, Stanford estudante de pós-graduação Shayan Gharan, e Aleksander Madry, agora, da École Polytechnique Fédérale de Lausanne, na Suíça, mostrou que o novo arredondamento técnica pode produzir um bom algoritmo de aproximação para uma variação do problema do caixeiro viajante, o “assimétrica” caso a caso. No ano seguinte, Saberi, Gharan e Mohit Singh da Universidade McGill usaram a mesma abordagem para desenvolver um novo algoritmo de aproximação para o problema de caixeiro viajante comum.,

dado um mapa de cidades e rodovias, o novo algoritmo começa calculando a solução fracionada exata para o problema do caixeiro viajante. Em seguida, ele arredonda essa solução fraccional para uma árvore que esperamos chegar perto de atingir o equilíbrio procurado entre o comprimento e fácil conversão para uma viagem de ida e volta. Finalmente, o algoritmo conecta essa árvore — ao invés da mais Curta — na estrutura de Christofides.

O novo algoritmo foi “uma ideia que poderíamos descrever em uma hora ou duas, mas provar que realmente funcionou levou mais de um ano”, disse Saberi.,

Depois de uma análise longa, a equipe Stanford-McGill foi finalmente capaz de vencer o algoritmo de Christofides por uma pequena margem para problemas “gráficos” de caixeiros-viajante, uma ampla subclasse. Dentro de meses, outros grupos, energizados pelo sucesso da equipe Stanford-McGill, usaram outras técnicas de arredondamento para produzir algoritmos para o caso gráfico com melhores aproximações; o recorde atual está em 40 por cento, uma melhoria substancial sobre os 50 por cento de Christofides.,

O gráfico de caso “encapsula um monte de as mesmas dificuldades que você encontra em o problema geral,” Arora disse, acrescentando que as mesmas técnicas que funcionam para o gráfico de caso pode muito bem ser exercida sobre a conta geral do problema do caixeiro viajante.no entanto, Saberi disse, resolver o problema de aproximação de caixeiros viajantes em sua generalidade irá provavelmente exigir uma infusão de novas ideias.,

“A descoberta matemática é como sentir o seu caminho numa sala escura: colocar a sua mão aqui e encontrar uma cadeira, colocar a sua mão ali e encontrar uma mesa”, disse ele, parafraseando o matemático Andrew Wiles. “A dada altura, a tua mão carrega no interruptor da luz, e de repente tudo faz sentido. Para o problema do caixeiro viajante, mesmo depois de tantos papéis que empurraram o envelope em tantas direções, eu não acho que nós temos carregado esse interruptor ainda.”

original story reprinted with permission from Simons Science News, an editorially independent division of SimonsFoundation.,org cuja missão é melhorar a compreensão pública da ciência, cobrindo os desenvolvimentos de investigação e as tendências em matemática e as ciências computacionais, físicas e da vida.