Breaking Value Symmetry
Breaking Value Symmetry
复制标题
打破价值对称性
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
T. Walsh
中科院分区：
文献类型：
--
作者：
T. Walsh
对称性是解决许多约束满足问题的重要因素。一种常见的对称类型是当我们有对称值时。在最近的一系列论文中，我们研究了打破值对称的方法（沃尔什2006 a; 2007）。我们的研究结果确定了消除值对称性的计算限制。例如，我们证明了修剪所有对称值一般是NP-困难的。然而，实验表明，在实践中，许多值对称性可以被打破。这些结果可能是有用的研究人员在规划，调度和其他领域的价值对称发生在许多不同的领域。
Symmetry is an important factor in solving many constraint satisfaction problems. One common type of symmetry is when we have symmetric values. In a recent series of papers, we have studied methods to break value symmetries (Walsh 2006a; 2007). Our results identify computational limits on eliminating value symmetry. For instance, we prove that pruning all symmetric values is NP-hard in general. Nevertheless, experiments show that much value symmetry can be broken in practice. These results may be useful to researchers in planning, scheduling and other areas as value symmetry occurs in many different domains.