Loading...
Please wait, while we are loading the content...
Similar Documents
Using Pseudosymmetry to Reduce Search Effort
| Content Provider | Semantic Scholar |
|---|---|
| Author | Prestwich, Steven David Beck, J. Christopher |
| Copyright Year | 2004 |
| Abstract | Symmetry breaking exploits a relationship between solutions: that they occur in equivalence classes. Constraints may be added to exclude all symmetrically equivalent solutions but one, greatly reducing the search space. Using two problems we show that a weaker relationship can also be exploited: that the existence of one solution implies the existence of another but not necessarily vice versa. It is then sufficient to search only for the latter solution. We demonstrate the value of using such relationships in search by adding pseudosymmetry breaking constraints to the Maximum-Density Still Life and Peaceable Armies of Queens problems. In the latter we are able to improve on known results. In a broader context, we show that pseudosymmetry is a generalization of a number of concepts in constraint programming (symmetry and substitutability), artificial intelligence (the pure literal rule in Boolean satisfiability) and operations research (dominance rules). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://4c.ucc.ie/4cite/TR-01-2004.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
