A carregar...
Publicação
Solving the Travelling Salesman Problem based on Coupled Ring-Oscillators
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 1.24 MB | Adobe PDF |
Orientador(es)
Resumo(s)
When thinking of hard mathematical problems the notion of NP-hard usually comes into
play. One of the most famous NP-hard problems is the Travelling Salesman Problem
(TSP), which tries to solve the following: Given a list of cities and distances in-between
them, what is the shortest possible route that visits every city and returns to the original
city?
This common optimisation problem has some heuristics and approximation algorithms
that can help solve it but most solutions still have an exponential increment of
time and complexity with every city that is added.
By encoding a TSP into a circuit designed with coupled ring oscillators and by analysing
the frequency spectra throughout the time we hoped to be able to determine the shortest
path that would connect all of the cities.
Our test were unable to solve a complete TSP but we were in fact able to prove some
landmark points of our implementation that could help to solve it. Namely we showed
that in our cases higher frequencies spread quicker, multiple frequencies can be spread
through a single ring oscillator and these frequencies actually spread throughout the
circuit.
Some suggestions are made of possible future work and we also take note on some of
the limitations of this project.
Descrição
Palavras-chave
Ring Oscillators Travelling Salesman Problem Coupling Oscillatory computing Optimisation