Searching with iterated maps
- 9 January 2007
- journal article
- Published by Proceedings of the National Academy of Sciences in Proceedings of the National Academy of Sciences of the United States of America
- Vol. 104 (2), 418-423
- https://doi.org/10.1073/pnas.0606359104
Abstract
In many problems that require extensive searching, the solution can be described as satisfying two competing constraints, where satisfying each independently does not pose a challenge. As an alternative to tree-based and stochastic searching, for these problems we propose using an iterated map built from the projections to the two constraint sets. Algorithms of this kind have been the method of choice in a large variety of signal-processing applications; we show here that the scope of these algorithms is surprisingly broad, with applications as diverse as protein folding and Sudoku.Keywords
This publication has 20 references indexed in Scilit:
- Deconstructing the energy landscape: Constraint-based algorithms for folding heteropolymersPhysical Review E, 2006
- Finding best approximation pairs relative to two closed convex sets in Hilbert spacesJournal of Approximation Theory, 2004
- Random projections and the optimization of an algorithm for phase retrievalJournal of Physics A: General Physics, 2003
- Analytic and Algorithmic Solution of Random Satisfiability ProblemsScience, 2002
- GLOBAL OPTIMIZATION STUDIES ON THE ID PHASE PROBLEMInternational Journal of General Systems, 1996
- On the Application of the Minimal Principle to Solve Unknown StructuresScience, 1993
- Image restoration by the method of generalized projections with application to restoration from magnitudeJournal of the Optical Society of America A, 1984
- Phase retrieval algorithms: a comparisonApplied Optics, 1982
- Reconstruction of an object from the modulus of its Fourier transformOptics Letters, 1978
- Solvable Model of a Spin-GlassPhysical Review Letters, 1975