Histórico problema do caixeiro viajante é resolvido em hardware

Redação do Site Inovação Tecnológica

Os carros sem motorista precisam resolver problemas similares de análise combinatória o tempo todo.
[Imagem: Tokyo University of Science]

Problema de otimização combinatorial

Engenheiros da Universidade de Ciências de Tóquio, no Japão, construíram um processador capaz de resolver um dos problemas mais intratáveis da ciência da computação.

O "problema do caixeiro-viajante" é um problema de otimização combinatorial, em que um vendedor deve começar em uma cidade e retornar a essa cidade depois de viajar para todas as diferentes cidades em uma lista. A questão é saber qual é o caminho mais eficiente entre todos os pontos - o problema se torna exponencialmente mais difícil conforme cada cidade é adicionada à lista.

É claro que a agenda de um vendedor ou entregador é apenas um exemplo do problema, e, além das questões de logística, há uma infinidade de situações correlatas que os computadores precisam resolver o tempo todo.

Chip combinatorial

Como ninguém conseguiu ainda idealizar um algoritmo eficiente para esses problemas de otimização combinatorial, várias equipes têm buscado uma solução migrando o problema do software para o hardware, usando circuitos integrados dedicados.

Nesse método, cada estado em um problema do tipo do vendedor ambulante (por exemplo, cada rota possível de um caminhão de entrega) é representado por "células de spin", cada uma tendo dois estados. Usando um circuito capaz de armazenar a força do estado de spin de uma célula em detrimento do outro, é possível obter a relação entre esses estados (ou, em nossa analogia, a distância entre duas cidades para o caminhão de entrega).

Com um sistema grande o suficiente para conter o mesmo número de células e circuitos que o número de componentes do problema (ou cidades e rotas para o caminhão de entrega), torna-se possível identificar o estado que requer menos energia, ou, em outras palavras, a rota que cobre a menor distância, resolvendo o problema do caixeiro-viajante ou qualquer outro tipo de problema de otimização combinatória.

Contudo, uma das grandes desvantagens dessa abordagem de hardware é que o sistema exige um pré-processamento, e o número de componentes e o tempo necessários para inserir os dados aumentam à medida que a escala do problema aumenta. Por esse motivo, essa tecnologia só conseguiu resolver o problema do caixeiro-viajante envolvendo um máximo de 16 estados ou cidades, e sem os ganhos esperados de velocidade e baixo consumo de energia.

Reduzindo as dimensões

Satoshi Kitamura e seus colegas descobriram agora que as interações das células do chip são lineares, o que garante que as células de spin só podem interagir com as células próximas a elas, prolongando o tempo de processamento. "Nós decidimos organizar as células de maneira ligeiramente diferente, para garantir que todas as células de spin pudessem ser interconectadas," explicou o professor Takayuki Kawahara, coordenador da equipe.

A equipe primeiro organizou os circuitos em uma matriz bidimensional e, a seguir, organizou as células de spin separadamente em um arranjo unidimensional. Com isto, os circuitos podem ler os dados e um agregado desses dados é usado para mudar os estados das diversas células.

Isso significa que o número de células de spin necessárias e o tempo necessário para o processamento é drasticamente reduzido. A solução se mostrou eficiente para resolver problemas envolvendo até 22 cidades.

A equipe acredita que esta tecnologia, quando implementada em chips em escala industrial, terá um largo campo de aplicações devido ao seu alto desempenho e baixos requisitos de energia - qualquer aplicação que busque soluções ideais a partir de um grande número de combinações.

Bibliografia:

Artigo: AI Chips on Things for Sustainable Society: A 28-nm CMOS, Fully Spin-to-spin Connected 512-Spin, Multi-Spin-Thread, Folded Halved-Interaction Circuits Method, Annealing Processing Chip
Autores: Satoshi Kitamura, Ryoma Iimura, Takayuki Kawahara
Revista: Proceedings of the IEEE 18th World Symposium on Applied Machine Intelligence and Informatics