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.

© 2007 Optical Society of America

» View Full Text: Acrobat PDF (3017 KB)

History
Original Manuscript: March 15, 2006
Manuscript Accepted: October 11, 2006
Revised Manuscript: September 10, 2006
Published: January 25, 2007

References

Please [login to View References]

Citing Articles

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Advanced Search

Recent ToC Categories (Beta)