Difference-map algorithm
The difference-map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta-algorithm in the sense that it is built from more basic algorithms that perform projections onto constraint sets. From a mathematical perspective, the difference-map algorithm is a dynamical system based on a mapping of Euclidean space. Solutions are encoded as fixed points of the mapping.
- Comment
- enThe difference-map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta-algorithm in the sense that it is built from more basic algorithms that perform projections onto constraint sets. From a mathematical perspective, the difference-map algorithm is a dynamical system based on a mapping of Euclidean space. Solutions are encoded as fixed points of the mapping.
- Depiction
- Has abstract
- enThe difference-map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta-algorithm in the sense that it is built from more basic algorithms that perform projections onto constraint sets. From a mathematical perspective, the difference-map algorithm is a dynamical system based on a mapping of Euclidean space. Solutions are encoded as fixed points of the mapping. Although originally conceived as a general method for solving the phase problem, the difference-map algorithm has been used for the boolean satisfiability problem, protein structure prediction, Ramsey numbers, diophantine equations, and Sudoku, as well as sphere- and disk-packing problems. Since these applications include NP-complete problems, the scope of the difference map is that of an . Whereas incomplete algorithms can efficiently verify solutions (once a candidate is found), they cannot prove that a solution does not exist. The difference-map algorithm is a generalization of two iterative methods: Fienup's Hybrid input output (HIO) algorithm for phase retrieval and the for convex optimization. Iterative methods, in general, have a long history in phase retrieval and convex optimization. The use of this style of algorithm for hard, non-convex problems is a more recent development.
- Hypernym
- Algorithm
- Is primary topic of
- Difference-map algorithm
- Label
- enDifference-map algorithm
- Link from a Wikipage to an external page
- barisdemiroz.github.io/sudoku/sudokusolver_demo.html
- Link from a Wikipage to another Wikipage
- 2-SAT
- 3-SAT
- Absolute value
- Boolean satisfiability problem
- Category:Constraint programming
- Category:Search algorithms
- Chaos theory
- Coherent light
- Constraint (mathematics)
- Constraint satisfaction
- Convex optimization
- Diophantine equations
- Discrete Fourier transform
- Douglas-Rachford algorithm
- Dynamical system
- Euclidean space
- File:Diffraction data.png
- File:Iterations 0, 100, 200, 300 and 400 in difference-map reconstruction of grayscale image from Fourier transform modulus.png
- File:Time series of norm of difference-map increment Δ, during solving random 3-SAT instance.png
- Fixed point (mathematics)
- Fraunhofer diffraction
- Hybrid input output (HIO) algorithm for phase retrieval
- Incomplete algorithm
- Iterative methods
- Literal (mathematical logic)
- Local search (optimization)
- Map (mathematics)
- Meta-algorithm
- NP-complete
- Phase problem
- Projection (linear algebra)
- Protein structure prediction
- Ramsey numbers
- Search algorithm
- Set intersection
- Strange attractor
- Sudoku
- Support (mathematics)
- Unitary transformation
- SameAs
- 4ihrh
- Difference-map algorithm
- m.02q38wh
- Q5275267
- Subject
- Category:Constraint programming
- Category:Search algorithms
- Thumbnail
- WasDerivedFrom
- Difference-map algorithm?oldid=1086379622&ns=0
- WikiPageLength
- 13580
- Wikipage page ID
- 10145406
- Wikipage revision ID
- 1086379622
- WikiPageUsesTemplate
- Template:Reflist
