| Popis: |
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. |
