• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>AI communications >Symmetry-breaking answer set solving
【24h】

Symmetry-breaking answer set solving

机译：打破对称的答案集求解

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

摘要

We investigate the role of symmetry detection and symmetry breaking in answer set programming to eliminate symmetric parts of the search space and, thereby, simplify the solution process. We reduce symmetry detection to a graph automorphism problem which allows us to extract symmetries of a logic program from the symmetries of the constructed coloured graph. The correctness of our reduction is proven. We also propose an encoding of symmetry-breaking constraints in terms of permutation cycles and use only generators in this process to implicitly represent symmetries with exponential compression. These ideas are formulated as preprocessing and implemented in a completely automated flow that first detects symmetries from a given answer set program, adds symmetry-breaking constraints, and can be applied to any existing answer set solver. We demonstrate computational impact on benchmarks versus direct application of the solver.
机译：我们调查了答案集编程中对称检测和对称破坏的作用，以消除搜索空间的对称部分，从而简化了求解过程。我们将对称性检测减少到图自同构问题，这使我们能够从构造的彩色图的对称性中提取逻辑程序的对称性。我们减少的正确性得到了证明。我们还提出了一种根据置换周期对对称破坏约束进行编码的方法，并且在此过程中仅使用生成器隐式表示具有指数压缩的对称性。这些想法被公式化为预处理，并在全自动流程中实施，该流程首先从给定答案集程序中检测对称性，添加打破对称性的约束，并且可以应用于任何现有答案集求解器。我们证明了计算对基准的影响，而不是直接应用求解器。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号