发帖
雷达卡
摘要翻译：
对称性是许多约束程序的一个重要特征。我们证明了任何作用于一组对称破缺约束的对称性都可以用来破缺对称性。不同的对称在每个对称类中挑选出不同的解。我们在两种方法中使用这些观察来消除问题的对称性。这些方法的设计具有对称破缺方法的许多优点，但没有一些缺点。特别地，这两种方法通过快速有效的post约束传播来修剪搜索空间，同时减少了对称破缺和分支启发式之间的冲突。实验结果表明，这两种方法在一些标准基准上表现良好。
---
英文标题：
《Symmetries of Symmetry Breaking Constraints》
---
作者：
George Katsirelos, and Toby Walsh
---
最新提交年份：
2009
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
Symmetry is an important feature of many constraint programs. We show that any symmetry acting on a set of symmetry breaking constraints can be used to break symmetry. Different symmetries pick out different solutions in each symmetry class. We use these observations in two methods for eliminating symmetry from a problem. These methods are designed to have many of the advantages of symmetry breaking methods that post static symmetry breaking constraint without some of the disadvantages. In particular, the two methods prune the search space using fast and efficient propagation of posted constraints, whilst reducing the conflict between symmetry breaking and branching heuristics. Experimental results show that the two methods perform well on some standard benchmarks.
---
PDF链接：
https://arxiv.org/pdf/0909.3276
京公网安备 11010802022788号
