Novo chip resolve problema em um segundo

Você pode nunca ter ouvido falar nele, mas o “problema do caixeiro viajante” é um clássico da computação: “dado um número de cidades, como encontrar o caminho mais curto que passe por todas elas?”. Pode parecer um exercício fútil, mas é um exemplo de otimização combinatória, algo fundamental no cálculo de rotas no trânsito, análise molecular de medicamentos, análise de portfolios financeiros em busca de investimentos com o maior retorno e menor risco, e outros cenários onde vários parâmetros, e a interação entre eles, deve ser considerada. A notícia está no site Olhar Digital.

Quanto maior o número de elementos (ou cidades, no exemplo acima) a serem considerados, mais tempo de computação é necessário para chegar a uma solução ideal. É por isso que um novo chip, desenvolvido por pesquisadores do Departamento de Engenharia Elétrica da Universidade de Ciências de Tóquio, no Japão, está chamando a atenção. De acordo com o professor Takayuki Kawahara, líder da equipe, o novo chip consegue calcular uma solução para 22 cidades instantaneamente, algo que em um processador tradicional “de alto desempenho” levaria 1.200 anos.

Pesquisadores vem há tempo estudando soluções para o problema usando circuitos integrados. Entretanto, elas exigiam pré-processamento e o número de componentes (e tempo) necessários para entrada dos dados aumentava de acordo com a escala do problema. Por isso, técnicas já existentes conseguiam encontrar uma solução para no máximo 16 elementos.