...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >Symmetry Definitions for Constraint Satisfaction Problems
【24h】

Symmetry Definitions for Constraint Satisfaction Problems

机译：约束满足问题的对称性定义

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.
机译：我们回顾了文献中出现的关于约束满足问题（CSP）的对称性的许多不同定义，并表明可以用两种根本不同的方式来定义对称性：作为保留CSP实例解的操作，或者作为保留约束的操作。我们称这些为解对称性和约束对称性。我们将约束对称性更精确地定义为与CSP实例（微结构补码）相关的超图的自同构。我们证明了CSP实例的解决方案对称性也可以作为相关超图，kary nogood超图的自同构获得，并给出了一些例子来说明某些实例具有比约束对称性更多的解决方案对称性。最后，我们讨论了这些对称性不同概念的实际含义。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号