Tractable Symmetry Breaking Using Restricted Search Trees
Tractable Symmetry Breaking Using Restricted Search Trees
复制标题
使用受限搜索树实现易于处理的对称性破缺
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
S. Linton
中科院分区：
文献类型：
--
作者：
C. Roney;Ian P. Gent;T. Kelsey;S. Linton
我们提出了一个新的概念抽象对称破缺-GE树。GE树的构造和遍历打破了任何约束满足或类似问题中的所有对称性。我们给出了一个多项式时间算法的情况下，任意值对称的CSP的建设。我们已经实现了这种技术，并提供其实际有效性的实验证据。
We present a new conceptual abstraction in symmetry breaking - the GE-tree. The construction and traversal of a GE-tree breaks all symmetries in any constraint satisfaction or similar problem. We give a polynomial-time algorithm for this construction in the case of CSPs with arbitrary value symmetries. We have implemented this technique, and supply experimental evidence of its practical effectiveness.