AAAIMar, 2009

破坏价值的对称性

TL;DR研究发现,对称性是解决许多约束满足问题的重要因素,其中一种常见类型是对称值。我们研究了打破值对称性的方法,结果确定了消除值对称性的计算限制。虽然在一般情况下,修剪所有对称值是 NP-hard 的,但实验表明在实践中可以打破很多值对称性,这些结果对规划、调度和其他领域的研究人员可能有用,因为值对称性出现在许多不同的领域中。