|
(Foto: Divulgação)
Problema combinatorial
Uma "ameba eletrônica" conseguiu obter uma solução aproximada do histórico problema do caixeiro-viajante.
Nem mesmo os mais modernos supercomputadores digitais conseguem resolver esse problema de otimização combinatorial em tempo viável na prática porque o número de possíveis soluções que os programas precisam avaliar aumenta exponencialmente com o tamanho do problema - um efeito também conhecido como explosão combinatória.
Inúmeras tarefas de aplicação do mundo real, como planejamento e programação em logística e automação, são formuladas matematicamente como problemas de otimização combinatória - a versão original do "problema do caixeiro-viajante" busca a rota mais eficiente para que um vendedor comece a trabalhar em uma cidade e retorne a ela depois de viajar para todas as diferentes cidades em uma lista.
Tendo em vista a utilidade prática da questão, várias tentativas têm sido feitas de resolver esses problemas em tempos viáveis usando simuladores quânticos, processadores analógicos e até um novo tipo de computador, conhecido como "máquina Ising".
Enquanto essas soluções futurísticas não ficam prontas, Kenta Saito e colegas da Universidade de Hokkaido, no Japão, propuseram uma tecnologia mais simples: um pequeno robô que imita uma ameba, um organismo unicelular.
Computação analógica
A ameba é conhecida por maximizar sua colheita de alimentos de forma eficiente, deformando seu corpo. Saito conseguiu imitar a dinâmica da ameba eletronicamente usando um circuito analógico, o que torna sua solução também uma espécie de processador analógico.
O pequeno robô foi colocado sobre uma matriz de rotas eletricamente condutoras na qual as interseções entre as rotas apresentam diferentes valores de resistência elétrica, o que permite programar de maneira simples as exigências e restrições das rotas, como cidades já visitadas ou cidades sem ligação direta.
Saito usou seu processador analógico ameboide para encontrar a rota mais curta para um caixeiro-viajante que precisa visitar 4 cidades. A seguir, para não precisar construir matrizes cada vez maiores, ele programou o comportamento da ameba eletrônica em um simulador e utilizou para avaliar o desempenho em problemas de grande porte.
O algoritmo encontrou soluções válidas de alta qualidade com um comprimento de rota significativamente menor do que o comprimento médio obtido pela amostragem aleatória. Além disso, o tempo necessário para encontrar uma solução válida e eficiente cresceu apenas linearmente com o número de cidades, enquanto um algoritmo tradicional faz esse tempo crescer exponencialmente.
"Como o computador analógico consiste em um circuito simples e compacto, ele pode lidar com muitos problemas do mundo real nos quais entradas, restrições e solicitações mudam dinamicamente, e pode ser embutido em dispositivos IoT como um microchip para economia de energia," disse o professor Masashi Aono.
Até a próxima!
Fonte:
Inovação Tecnológica: inovacaotecnologica.com.br
Boghi Soluções em Novas Tecnologias
|
