nach oben

Natural Computing

Erschienen in:

01.03.2008

Solving the Hamiltonian path problem with a light-based computer

verfasst von: Mihai Oltean

Erschienen in: Natural Computing | Ausgabe 1/2008

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we propose a special computational device which uses light rays for solving the Hamiltonian path problem on a directed graph. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. In each node the rays are uniquely marked so that they can be easily identified. At the destination node we will search only for particular rays that have passed only once through each node. We show that the proposed device can solve small and medium instances of the problem in reasonable time.

Vorheriger Artikel Top-Down modulation of neural responses in visual perception: a computational exploration

Nächster Artikel On the universality of peptide computing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Adleman L (1994) Molecular computation of solutions to combinatorial problems. Science 266:1021–1024CrossRef

Ascheuer N (1995) Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. PhD thesis, TU Berlin

Bajcsy M, Zibrov AS, Lukin MD (2003) Stationary pulses of light in an atomic medium. Nature 426:638–641CrossRef

Černý V (1993) Quantum computers and intractable (NP-Complete) computing problems. Phys Rev A 48:116–119CrossRef

Cormen TH, Leiserson CE, Rivest RR (1990) Introduction to algorithms. MIT Press

Doniach S, Garel H, Orland H, (1996) Phase diagram of a semiflexible polymer chain in a θ solvent: application to protein folding. J Chem Phys 105:1601–1608CrossRef

Faist J (2005) Optoelectronics: silicon shines on. Nature 433:691–692CrossRef

Feitelson DG (1988) Optical computing: A survey for computer scientists. MIT Press

Flyckt SO, Marmonier C (2002) Photomultiplier tubes: principles and applications. Photonis, Brive, France

Garey MR, Johnson DS (1979) Computers and intractability: a guide to NP-completeness. Freeman & Co, San Francisco, CAMATH

Goodman JW (1982) Architectural development of optical data processing systems. Aust J Electr Electron Eng 2:139–149

Greenwood GW (2001) Finding solutions to NP problems: philosophical differences between quantum and evolutionary search algorithms. In: Proceedings CEC’2001, IEEE Press, pp 815–822

Hartmanis J (1995) On the weight of computations. Bull EATCS 55:136–138MATH

Hau LV, Harris SE, Dutton Z, Behroozi CH (1999) Light speed reduction to 17 meters per second in an ultracold atomic gas. Nature 397:594–598CrossRef

Henkel C, Frisco P, Tengely Sz (2005) An algorithm for SAT without an extraction phase. DNA Computing, Eleventh International Meeting on DNA Based Computers, LNCS 3892, pp 67–80

Lenslet (2004) website, http://www.lenslet.com

Liu C, Dutton Z, Behroozi CH, Hau LV (2001) Observation of coherent optical information storage in an atomic medium using halted light pulses. Nature 409:490–493CrossRef

MacQueen J (1967) Some methods for classification and analysis of multivariate observations. In: LeCam LM, Neyman J (eds) Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. University of California press, Berkeley, pp 281–297

Murphy N, Naughton TJ, Woods D, Henley B, McDermott K, Duffy E, van der Burgt PJM, Woods N (2006) Implementations of a model of physical sorting. In: Adamatzky A, Teuscher C (eds) From Utopian to Genuine Unconventional Computers workshop. Luniver Press, pp 79–100

Naughton TJ (2000) A model of computation for Fourier optical processors. In: Lessard RA, Galstian T (eds) Optics in Computing, Proc. SPIE 4089:24–34

Oltean M (2006) A light-based device for solving the Hamiltonian path problem. In: Calude C et al (eds) Unconventional computing. LNCS 4135, Springer-Verlag, pp 217–227

Paniccia M, Koehl S (2005) The silicon solution. IEEE Spectrum, IEEE Press, October

Reif JH, Tyagi A (1997) Efficient parallel algorithms for optical computing with the discrete Fourier transform primitive. Appl Optics 36(29):7327–7340CrossRef

Rong H, Jones R, Liu A, Cohen O, Hak D, Fang A, Paniccia M (2005a) A continuous-wave Raman silicon laser. Nature 433:725–728CrossRef

Rong H, Liu A, Jones R, Cohen O, Hak D, Nicolaescu R, Fang A, Paniccia M (2005b) An all-silicon Raman laser. Nature 433:292–294CrossRef

Schultes D (2005) Rainbow sort: sorting at the speed of light. Nat Comput Springer-Verlag 5(1):67–82CrossRefMathSciNet

Woods D, Naughton TJ (2005) An optical model of computation. Theor Comput Sci 334(1–3):227–258MATHCrossRefMathSciNet

Sloane N (2006) The on-line encyclopedia of integer sequences. http://www.research.att.com/∼njas/sequences/A023758

Optical Character Recognition (2006) @ Wikipedia, http://en.wikipedia.org/wiki/Optical_character_recognition

Titel: Solving the Hamiltonian path problem with a light-based computer
verfasst von: Mihai Oltean
Publikationsdatum: 01.03.2008
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2008
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-007-9042-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2008

Foreword

A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications

Doubler and linearizer: an approach toward a unified theory for molecular computing based on DNA complementarity

Top-Down modulation of neural responses in visual perception: a computational exploration

On spiking neural P systems and partially blind counter machines

Mapping non-conventional extensions of genetic programming

Premium Partner