• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Principles and practice of constraint programming >A Microstructure-Based Family of Tractable Classes for CSPs
【24h】

A Microstructure-Based Family of Tractable Classes for CSPs

机译：CSP的基于微结构的可操作类系列

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

摘要

The study of tractable classes is an important issue in Artificial Intelligence, especially in Constraint Satisfaction Problems. In this context, the Broken Triangle Property (BTP) is a state-of-the-art microstructure-based tractable class which generalizes well-known and previously-defined tractable classes, notably the set of instances whose constraint graph is a tree. In this paper, we propose to extend and to generalize this class using a more general approach based on a parameter k which is a given constant. To this end, we introduce the k-BTP property (and the class of instances satisfying this property) such that we have 2-BTP = BTP, and for k ＞ 2, k-BTP is a relaxation of BTP in the sense that k-BTP (∈) (k + 1)-BTP. Moreover, we show that if k-TW is the class of instances having tree-width bounded by a constant k, then k-TW C (k + 1)-BTP. Concerning tractability, we show that instances satisfying k-BTP and which are strong k-consistent are tractable, that is, can be recognized and solved in polynomial time. We also study the relationship between k-BTP and the approach of Naanaa who proposed a set-theoretical tool, known as the directional rank, to extend tractable classes in a parameterized way. Finally we propose an experimental study of 3-BTP which shows the practical interest of this class, particularly w.r.t. the practical solving of instances satisfying 3-BTP and for other instances, w.r.t. to backdoors based on this tractable class.
机译：易处理类的研究是人工智能中的重要问题，尤其是在约束满足问题中。在这种情况下，“破碎三角形特性”（BTP）是基于微结构的最新可处理类，可归纳出众所周知的和先前定义的可处理类，尤其是其约束图为树的实例集。在本文中，我们建议基于参数k（它是给定常数）使用更通用的方法来扩展和推广此类。为此，我们引入k-BTP属性（以及满足该属性的实例类别），使我们具有2-BTP = BTP，并且对于k＞ 2，在k的意义上，k-BTP是BTP的松弛。 -BTP（∈）（k +1）-BTP。而且，我们证明如果k-TW是树的宽度由常数k限定的实例的类别，则k-TW C（k +1）-BTP。关于可延展性，我们证明满足k-BTP且k一致强的实例是可延展的，即可以在多项式时间内识别和求解。我们还研究了k-BTP与Naanaa的方法之间的关系，Naanaa提出了一种集理论工具，称为定向等级，以参数化方式扩展可处理的类。最后，我们提出了一项对3-BTP的实验研究，该实验表明了此类的实际兴趣，尤其是w.r.t.满足3-BTP的实例的实际解决方案，对于其他实例，则为w.r.t.基于这个易处理的类的后门程序。

著录项

  • 来源
  • 会议地点 Cork(IE)
  • 作者

    Martin C. Cooper; Philippe Jegou; Cyril Terrioux;

  • 作者单位

    IRIT, University of Toulouse Ⅲ, 31062 Toulouse, France;

    Aix-Marseille Universite, CNRS, ENSAM, Universite de Toulon, LSIS UMR 7296, Avenue Escadrille Normandie-Niemen, 13397 Marseille Cedex 20, France;

    Aix-Marseille Universite, CNRS, ENSAM, Universite de Toulon, LSIS UMR 7296, Avenue Escadrille Normandie-Niemen, 13397 Marseille Cedex 20, France;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号