Expand this Topic clickable element to expand a topic
Skip to content
Optica Publishing Group

Optical solution for bounded NP-complete problems

Not Accessible

Your library or personal account may give you access

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

Full Article  |  PDF Article
More Like This
An Optical Solution For The Traveling Salesman Problem

Tobias Haist and Wolfgang Osten
Opt. Express 15(16) 10473-10482 (2007)

An optical solution for the traveling salesman problem: erratum

Tobias Haist and Wolfgang Osten
Opt. Express 15(20) 12627-12627 (2007)

Optical NP problem solver on laser-written waveguide platform

María Ramos Vázquez, Vibhav Bharadwaj, Belén Sotillo, Shu-Zee A. Lo, Roberta Ramponi, Nikolay I. Zheludev, Guglielmo Lanzani, Shane M. Eaton, and Cesare Soci
Opt. Express 26(2) 702-710 (2018)

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Figures (13)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Equations (21)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Select as filters


Select Topics Cancel
© Copyright 2024 | Optica Publishing Group. All Rights Reserved