“Este é um resultado que eu queria toda a minha carreira”, disse David Williamson, da Universidade de Cornell, que tem vindo a estudar a viajar vendedor problema desde a década de 1980.
A viagem vendedor problema é um de um punhado de problemas básicos que teóricos, cientistas da computação, vire novamente e novamente para testar os limites de eficiência e de computação. O novo resultado “é o primeiro passo para mostrar que as fronteiras de computação eficiente são de fato melhores do que pensávamos”, disse Williamson.,
progresso fraccional
embora não exista provavelmente um método eficiente que encontre sempre a viagem mais curta, é possível encontrar algo quase tão bom: a árvore mais Curta ligando todas as cidades, o que significa uma rede de conexões (ou “arestas”) sem laços fechados. O algoritmo de Christofides usa esta árvore como a espinha dorsal para uma viagem de ida e volta, adicionando arestas extras para convertê-la em uma viagem de ida e volta.
qualquer rota de ida e volta deve ter um número par de bordas em cada cidade, uma vez que cada chegada é seguida por uma partida., Acontece que o inverso também é verdadeiro — se cada cidade em uma rede tem um número par de conexões, então as bordas da rede devem traçar uma viagem de ida e volta.
A árvore mais curta que liga todas as cidades não tem esta propriedade de serenidade, uma vez que qualquer cidade no final de um ramo tem apenas uma ligação a outra cidade. Assim, para transformar a árvore mais curta em uma viagem de ida e volta, Christofides (que morreu no ano passado) encontrou a melhor maneira de conectar pares de cidades que têm números ímpares de bordas. Em seguida, ele provou que a viagem de ida e volta resultante nunca será mais de 50% maior do que a melhor viagem de volta possível.,ao fazê-lo, ele desenvolveu talvez o mais famoso algoritmo de aproximação em Ciência da Computação Teórica — um que normalmente forma o primeiro exemplo em livros e cursos.
“todo mundo conhece o algoritmo simples”, disse Alantha Newman da Universidade de Grenoble Alpes e do Centro Nacional de pesquisa científica na França. E quando você sabe disso, ela disse, “Você sabe o estado da arte” – pelo menos, você sabia até julho passado.
cientistas da Computação suspeitaram há muito tempo que deveria haver um algoritmo de aproximação que superasse o algoritmo de Christofides., Afinal de Contas, seu algoritmo simples e intuitivo nem sempre é uma maneira eficaz de projetar uma rota de vendedor ambulante, uma vez que a árvore mais Curta conectando as cidades pode não ser a melhor espinha dorsal que você poderia escolher. Por exemplo, se esta árvore tem muitos ramos, cada cidade no final de um ramo terá que ser combinado com outra cidade, potencialmente formando lotes de novas conexões caras.,
Em 2010, Oveis Gharan, Saberi e Mohit Singh, do Instituto de Tecnologia da Geórgia começaram a pensar se seria possível melhorar Christofides ” algoritmo escolhendo não a menor árvore de ligar todas as cidades, mas uma árvore aleatória a partir de uma cuidadosamente escolhida coleção. Eles se inspiraram em uma versão alternativa do problema do vendedor ambulante em que você está autorizado a viajar ao longo de uma combinação de caminhos — talvez você chegar a Denver por 3/4 da rota de Chicago para Denver mais 1/4 da rota de Los Angeles para Denver.,ao contrário do problema dos vendedores ambulantes regulares, este problema fraccional pode ser resolvido de forma eficiente. E embora as rotas fraccionárias não façam sentido físico, os cientistas da computação acreditam há muito tempo que a melhor rota fraccionada deve ser um guia áspero para os contornos de boas rotas ordinárias.
Para criar seu algoritmo, Oveis Gharan, Saberi e Singh definido um processo aleatório que escolhe uma árvore de ligar todas as cidades, de modo que a probabilidade de que uma dada aresta está na árvore que é igual a borda da fração da melhor fracionário rota., Existem muitos processos aleatórios, então os pesquisadores escolheram um que tende a produzir árvores com muitas cidades igualmente conectadas. Após este processo aleatório cuspir uma árvore específica, seu algoritmo conecta-a no esquema de Christofides para combinar cidades com números ímpares de arestas, para convertê-la em uma viagem de ida e volta.
este método parecia promissor, não só para os três investigadores, mas também para outros cientistas da computação. “A intuição é simples”, disse Ola Svensson do Instituto Federal Suíço de tecnologia Lausanne. Mas ” para provar que é uma besta diferente.,”
No ano seguinte, porém, Oveis Gharan, Saberi e Singh conseguiu provar que seu algoritmo batidas Christofides ” algoritmo para “gráfica” viajando vendedor problemas — aqueles em que as distâncias entre as cidades são representadas por uma rede (não necessariamente incluindo todas as conexões) em que cada aresta tem o mesmo comprimento. Mas os pesquisadores não conseguiram descobrir como estender seu resultado ao problema geral dos vendedores ambulantes, no qual algumas bordas podem ser muito mais longas do que outras.,
“Se tivermos que adicionar uma borda super cara para a correspondência, então estamos lixados, basicamente”, disse Karlin.
empurrando para trás
No entanto, Oveis Gharan emergiu dessa colaboração com uma crença inabalável de que seu algoritmo deve bater o algoritmo de Christofides para o problema geral viajante do vendedor. “Nunca tive dúvidas”, disse ele.Oveis Gharan continuou girando o problema em sua mente ao longo dos anos que se seguiram., Ele suspeitava que uma disciplina matemática chamada geometria dos polinômios, pouco conhecida no mundo teórico da ciência da computação, poderia ter as ferramentas que ele precisava. Então, quando Karlin veio até ele dois anos atrás sugerindo que eles Co-aconselharam um brilhante novo estudante de graduação chamado Nathan Klein que tinha se formado em matemática e violoncelo, ele disse: “OK, vamos tentar-eu tenho esse problema interessante.”
Karlin pensou que, se nada mais, seria uma oportunidade divertida de aprender mais sobre a geometria dos polinômios., “Eu realmente não pensei que seríamos capazes de resolver este problema”, disse ela.ela e Oveis Gharan não hesitaram em atirar Klein para o fundo da pesquisa de ciência da computação. Oveis Gharan tinha-se cortado os dentes no problema dos vendedores ambulantes como um estudante graduado em 2010. E os dois conselheiros concordaram sobre o mérito de atribuir problemas difíceis aos estudantes graduados, especialmente durante seus primeiros anos, quando eles não estão sob pressão para obter resultados.
os três mergulharam em uma intensa colaboração., “Era só nisso que eu pensava durante dois anos”, disse Klein.
eles passaram o primeiro ano Resolvendo uma versão simplificada do problema, para ter uma noção dos desafios que estavam enfrentando. Mas mesmo depois que eles conseguiram isso, o caso geral ainda parecia um “moonshot”, disse Klein.
ainda assim, eles tinham tido uma sensação para suas ferramentas — em particular, a geometria dos polinômios. Um polinômio é uma combinação de termos feitos de Números e variáveis aumentadas para potências, tais como 3x2y + 8xz7., Para estudar o problema dos vendedores ambulantes, os pesquisadores destilaram um mapa de cidades até um polinômio que tinha uma variável para cada borda entre cidades, e um termo para cada árvore que poderia conectar todas as cidades. Fatores numéricos, em seguida, ponderaram estes termos para refletir o valor de cada aresta na solução fraccional para o problema do vendedor ambulante.
Este polinômio, eles descobriram, tem uma propriedade cobiçada chamada “estabilidade real”, o que significa que os números complexos que fazem o polinômio avaliar a zero nunca se encontram na metade superior do plano complexo., A coisa boa sobre a estabilidade real é que ela permanece em vigor mesmo quando você faz muitos tipos de mudanças em seu polinômio. Então, por exemplo, se os pesquisadores quisessem se concentrar em cidades particulares, eles poderiam usar uma única variável para representar todas as diferentes bordas que levam a uma cidade, e eles poderiam definir as variáveis para bordas que não se importavam com igual a 1. Como eles manipularam esses polinômios simplificados, os resultados de suas manipulações ainda tinham estabilidade real, abrindo a porta para uma grande variedade de técnicas.,
Esta abordagem permitiu aos investigadores obter uma abordagem sobre questões como a frequência com que o algoritmo seria forçado a ligar duas cidades distantes. Em uma análise de quase 80 páginas, eles conseguiram mostrar que o algoritmo bate o algoritmo de Christofides para o problema do vendedor ambulante geral (o artigo ainda tem que ser revisado por pares, mas os especialistas estão confiantes de que está correto). Uma vez que o artigo foi concluído, Oveis Gharan retirou um e-mail para Saberi, seu antigo conselheiro de doutorado. “Acho que posso finalmente formar-me”, brincou ele.
