Novo chip japonês resolve em um segundo problema que levaria 1.200 anos

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.

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.

O que a equipe do Professor Kawahara fez foi rearranjar os elementos do circuito, de forma que a quantidade de “células” necessárias para armazenar cada estado possível, e o tempo necessário para o cálculo, fossem drasticamente reduzidos.

Os autores apresentaram seus resultados na 18ª edição do Simpósio Mundial para Inteligência de Máquina Aplicada e Informática (SAMI 2020). Eles esperam que, no futuro, sua solução possa ser usada em sistemas de alto desempenho e baixo consumo de energia, para facilitar a descoberta de soluções ótimas para grandes números de combinações.

Fonte: Tokyo University of Science