Open AccessAn Optical Solution For The Traveling Salesman Problem
Author(s) -
Tobias Haist,
Wolfgang Osten
Publication year - 2007
Publication title -
optics express
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.394
H-Index - 271
ISSN - 1094-4087
DOI - 10.1364/oe.15.010473
Subject(s) - travelling salesman problem , 2 opt , bottleneck traveling salesman problem , reduction (mathematics) , mathematical optimization , time complexity , computer science , mathematics , quadratic equation , optics , physics , algorithm , geometry
We introduce an optical method based on white light interferometry in order to solve the well-known NP-complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non-polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to N(N) for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal-to-noise ratio. The proposed method is meant purely as a gedankenexperiment.