Soluzione del problema del commesso viaggiatore mediante dispositivo combinatorio magnonico

Rapporti scientifici volume 13, numero articolo: 11708 (2023) Citare questo articolo

207 accessi

Dettagli sulle metriche

Il problema del commesso viaggiatore (TSP) è un problema decisionale essenziale per una serie di applicazioni pratiche. Oggi questo problema viene risolto sui computer digitali che sfruttano un'architettura di tipo booleano controllando uno per uno un certo numero di possibili percorsi. In questo lavoro descriviamo un tipo speciale di hardware per la soluzione TSP. È un dispositivo combinatorio magnonico comprendente parti magnetiche ed elettriche collegate nel circuito ad anello attivo. Esistono numerosi possibili percorsi di propagazione nella rete magnetica costituita da sfasatori, filtri di frequenza e attenuatori. Gli sfasatori imitano le città in TSP mentre la distanza tra le città è codificata nell'attenuazione del segnale. L'insieme dei filtri di frequenza fa sì che le onde su frequenze diverse si propaghino attraverso percorsi diversi. Il principio di funzionamento si basa sulla classica sovrapposizione delle onde. C'è un certo numero di onde che arrivano in tutti i percorsi possibili in parallelo accumulando diversi spostamenti di fase e smorzamento dell'ampiezza. Tuttavia, solo l'onda o le onde che accumulano un certo sfasamento verranno amplificate dalla parte elettrica. L'amplificazione avviene prima alle onde che possiedono le minime perdite di propagazione. Ciò rende questo tipo di dispositivo adatto alla soluzione TSP, dove le onde sono simili ai venditori che viaggiano contemporaneamente su tutti i percorsi possibili. Presentiamo i risultati della modellazione numerica che illustrano le soluzioni TSP per quattro e sei città. Inoltre, presentiamo i dati sperimentali per la soluzione TSP con quattro città. Il dispositivo prototipo è costituito da componenti disponibili in commercio, tra cui sfasatori/filtri magnetici, cavi coassiali, divisori, attenuatori e un amplificatore a banda larga. Esistono tre esempi per trovare il percorso più breve tra le città per tre diversi insiemi di distanze da città a città. L'approccio proposto è scalabile per TSP con un numero maggiore di città. Vengono discussi anche i limiti e le sfide fisiche.

Il TSP è uno dei problemi di ottimizzazione combinatoria più conosciuti1. Si può affermare come segue: "Dato un elenco di città e le distanze tra ciascuna coppia di città, trova il percorso più breve possibile che visiti ciascuna città esattamente una volta e ritorni alla città di origine". È un problema di durezza polinomiale non deterministico (NP-hard), il che significa che non esiste alcuna garanzia di ottenere il percorso ottimale e nessun algoritmo esatto per risolverlo in tempo polinomiale. Il TSP è importante in una varietà di applicazioni pratiche tra cui i trasporti2, la pianificazione3 e la genomica4. Matematicamente, può essere definito come un insieme di \(n\) città, denominate \(\left\{{c}_{1},{c}_{2},\dots ,{c}_{n }\right\}\) e permutazioni \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\} \). L'obiettivo è scegliere \({\sigma }_{i}\) in modo tale che la somma di tutte le distanze euclidee tra le città in un tour sia ridotta al minimo. Il TSP può essere modellato come un grafico ponderato non orientato come mostrato in Fig. 1, dove le città sono i vertici del grafico, i percorsi sono i bordi del grafico e la distanza di un percorso è il peso del bordo. Il TSP può essere risolto controllando uno per uno tutti i possibili percorsi \(\left(n-1\right)!/2\) possibili. È relativamente facile controllare tutti i percorsi possibili per un numero limitato di città. Ad esempio, ci sono \(\left(4-1\right)!/2=3\) percorsi per il TSP con quattro città. Il numero di percorsi possibili aumenta proporzionalmente al fattoriale \(n\), il che rende difficile la soluzione per un gran numero di città utilizzando dispositivi informatici classici.

Grafico ponderato non orientato per TSP con quattro città. Le città sono i vertici del grafico, i percorsi sono i bordi del grafico e la distanza di un percorso è il peso del bordo.

Ci sono stati diversi tentativi di costruire hardware speciale per la soluzione TSP5,6. Ad esempio, il TSP di 6 città è stato risolto utilizzando una rete ottica di tipo Kohonen6. Tuttavia, nessuno di questi approcci ha prodotto un dispositivo praticamente realizzabile. Recentemente, al TSP7 sono state applicate diverse tecniche di ottimizzazione utilizzate nell’intelligenza artificiale (AI). Potrebbe accelerare significativamente la soluzione TSP ma non può fornire un vantaggio fondamentale se implementato su hardware convenzionale.