Solução do problema do caixeiro viajante usando dispositivo combinatório magnônico

Jul 27, 2023

Scientific Reports volume 13, Artigo número: 11708 (2023) Citar este artigo

207 Acessos

Detalhes das métricas

O problema do caixeiro viajante (TSP) é um problema de tomada de decisão essencial para uma série de aplicações práticas. Hoje, esse problema é resolvido em computadores digitais que exploram a arquitetura do tipo booleano, verificando, uma a uma, uma série de rotas possíveis. Neste trabalho descrevemos um tipo especial de hardware para a solução TSP. É um dispositivo combinatório magnônico composto por partes magnéticas e elétricas conectadas no circuito de anel ativo. Existem várias rotas de propagação possíveis na malha magnética feita de deslocadores de fase, filtros de frequência e atenuadores. Os deslocadores de fase imitam cidades no TSP enquanto a distância entre as cidades é codificada na atenuação do sinal. O conjunto de filtros de frequência faz com que as ondas em diferentes frequências se propaguem por diferentes rotas. O princípio de operação é baseado na clássica superposição de ondas. Há uma série de ondas vindo em todas as rotas possíveis em paralelo, acumulando diferentes mudanças de fase e amortecimento de amplitude. Porém, apenas a(s) onda(s) que acumula(m) certa mudança de fase serão amplificadas pela parte elétrica. A amplificação chega primeiro às ondas que possuem as perdas de propagação mínimas. Isso torna este tipo de dispositivo adequado para solução TSP, onde as ondas são semelhantes às dos vendedores viajando em todas as rotas possíveis ao mesmo tempo. Apresentamos os resultados da modelagem numérica ilustrando as soluções TSP para quatro e seis cidades. Além disso, apresentamos dados experimentais para a solução TSP com quatro cidades. O dispositivo protótipo é construído com componentes comercialmente disponíveis, incluindo filtros/deslocadores de fase magnéticos, cabos coaxiais, divisores, atenuadores e um amplificador de banda larga. Existem três exemplos de como encontrar a rota mais curta entre as cidades para três conjuntos diferentes de distâncias entre cidades. A abordagem proposta é escalável para TSP com um maior número de cidades. Limites e desafios físicos também são discutidos.

O TSP é um dos problemas de otimização combinatória mais conhecidos1. Pode ser expresso da seguinte forma: “Dada uma lista de cidades e as distâncias entre cada par de cidades, encontre a rota mais curta possível que visite cada cidade exatamente uma vez e retorne à cidade de origem”. É um problema de dureza de tempo polinomial não determinístico (NP-hard), o que significa que não há garantia de obter a rota ideal e nenhum algoritmo exato para resolvê-lo em tempo polinomial. O TSP é importante em uma variedade de aplicações práticas, incluindo transporte2, agendamento3 e genômica4. Matematicamente, pode ser definido como dado um conjunto de \(n\) cidades, denominadas \(\left\{{c}_{1},{c}_{2},\dots ,{c}_{n }\right\}\), e permutações \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\} \). O objetivo é escolher \({\sigma }_{i}\) tal que a soma de todas as distâncias euclidianas entre cidades em um passeio seja minimizada. O TSP pode ser modelado como um grafo ponderado não direcionado, como mostrado na Fig. 1, onde as cidades são os vértices do grafo, os caminhos são as arestas do grafo e a distância de um caminho é o peso da aresta. O TSP pode ser resolvido verificando uma por uma todas as rotas possíveis \(\left(n-1\right)!/2\). É relativamente fácil verificar todas as rotas possíveis para um pequeno número de cidades. Por exemplo, existem rotas \(\left(4-1\right)!/2=3\) para o TSP com quatro cidades. O número de rotas possíveis aumenta proporcionalmente ao \(n\) fatorial, o que torna difícil a solução para um grande número de cidades usando dispositivos de computação clássicos.

Gráfico ponderado não direcionado para TSP com quatro cidades. As cidades são os vértices do gráfico, os caminhos são as arestas do grafo e a distância de um caminho é o peso da aresta.

Houve diversas tentativas de construção de hardware especial para solução TSP5,6. Por exemplo, o TSP de 6 cidades foi resolvido usando uma rede óptica do tipo Kohonen6. Contudo, nenhuma destas abordagens resultou num dispositivo praticamente viável. Recentemente, uma variedade de técnicas de otimização utilizadas em inteligência artificial (IA) foram aplicadas ao TSP7. Pode acelerar significativamente a solução TSP, mas não pode fornecer uma vantagem fundamental na implementação em hardware convencional.