Optical solution for bounded NP-complete problems
- 25 January 2007
- journal article
- Published by Optica Publishing Group in Applied Optics
- Vol. 46 (5) , 711-724
- https://doi.org/10.1364/ao.46.000711
Abstract
We present a new optical method for solving bounded (input-length-restricted) NP-complete combinatorial problems. We have chosen to demonstrate the method with an NP-complete problem called the traveling salesman problem (TSP). The power of optics in this method is realized by using a fast matrix–vector multiplication between a binary matrix, representing all feasible TSP tours, and a gray-scale vector, representing the weights among the TSP cities. The multiplication is performed optically by using an optical correlator. To synthesize the initial binary matrix representing all feasible tours, an efficient algorithm is provided. Simulations and experimental results prove the validity of the new method.Keywords
This publication has 3 references indexed in Scilit:
- Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of ResearchINFORMS Journal on Computing, 1999
- Use of optical hardware to find good solutions to the traveling salesman problemPublished by SPIE-Intl Soc Optical Eng ,1993
- A Technique for Optically Convolving Two FunctionsApplied Optics, 1966