• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International Journal of Artificial Intelligence Tools: Architectures, Languages, Algorithms >DIRECT ALGORITHMS FOR FINDING MINIMAL UNSATISFIABLE SUBSETS IN OVER-CONSTRAINED CSPs
【24h】

DIRECT ALGORITHMS FOR FINDING MINIMAL UNSATISFIABLE SUBSETS IN OVER-CONSTRAINED CSPs

机译：在过度约束的CSP中寻找最小不满足子集的直接算法

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

摘要

In many situations, an explanation of the reasons behind inconsistency in an over-constrained CSP is required. This explanation can be given in terms of minimal unsatisfiable subsets (MUSes) of constraints. This paper presents algorithms for finding minimal unsatisfiable subsets (MUSes) of constraints in over constrained CSPs with finite domains and binary constraints. The approach followed is to generate subsets in the subset space, test them for consistency and record the inconsistent subsets found. We present three algorithms as variations of this basic approach. Each algorithm generates subsets in the subset space in a different order and curtails search by employing various search pruning mechanisms. The proposed algorithms are anytime algorithms: a time limit can be set on an algorithm's search and the algorithm can be made to find a subset of MUSes. Experimental evaluation of the proposed algorithms demonstrates that they perform two to three orders of magnitude better than the existing indirect algorithms. Furthermore, the algorithms are able to find MUSes in large CSP benchmarks.
机译：在许多情况下，需要对过度约束的CSP中不一致的原因进行解释。可以根据约束的最小不满足子集（MUSes）进行解释。本文提出了在有限域和二元约束的超约束CSP中寻找约束的最小不满足子集（MUSes）的算法。遵循的方法是在子集空间中生成子集，测试它们的一致性并记录发现的不一致子集。我们提出了三种算法，作为这种基本方法的变体。每种算法都会以不同的顺序在子集空间中生成子集，并通过采用各种搜索修剪机制来减少搜索。所提出的算法是随时算法：可以在算法搜索中设置时间限制，并且可以使算法找到MUS的子集。对提出的算法的实验评估表明，与现有的间接算法相比，它们的性能要好两到三个数量级。此外，该算法能够在大型CSP基准中找到MUS。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号