We have found the best path to take between the stars. The travelling salesman problem, an infamous mathematical puzzle that seeks the shortest route between many locations while visiting each only once and returning to the first, has been solved on the largest scale yet: the galaxy.
The travelling salesman problem seems simple, but it is notoriously difficult. It can be solved for specific data sets, but a general algorithm to solve any instance of the problem hasn鈥檛 yet been found. William Cook at the University of Waterloo in Canada and Keld Helsgaun at Roskilde University in Denmark have solved it on the largest scale yet.
They analysed data from the Gaia space telescope, which measured the locations of 2,079,471 stars in our galaxy in its first data release. The most efficient route that visits each of them is about 94,208,157.5 light years long, the pair found. If there is a shorter route, they calculated that it cannot be off by more than a factor of 0.0000074 鈥� about 700 light years. They then .
Advertisement
鈥淭his would be the fastest way to visit every measured star in the galaxy, but you鈥檇 need your warp engine,鈥� says Cook. Even at the speed of light, it would take nearly 100 million years to make this journey.
Solving the travelling salesman problem isn鈥檛 a purely academic exercise. The methods Cook and Helsgaun used can also be applied to other types of data, such as flight scheduling and genome mapping. 鈥淭he larger a problem you can solve, the closer you can come to reality, to modelling the actual world,鈥� says Cook. Gaia has now released data on the locations of more than 1 billion stars, and the researchers are working on finding the fastest route between them.
This problem took about 200 years of computing time over two years, says Cook.聽In the future, quantum computers could speed up that optimisation process. 鈥淭here are two parts of this: you have to find a good solution, and then prove that nobody can do better,鈥� says Cook. 鈥淨uantum computing, in principle, could do that first part very well if you had a good enough machine.鈥�
For now, though, quantum computers aren鈥檛 capable of such a large problem, so Cook is offering a monetary reward for anyone who can improve on his route between the stars.
Sign up to our free Launchpad newsletter for a voyage across the galaxy and beyond, every Friday
