约束满足问题的介绍

た入场券 2022-06-16 12:39 172阅读 0赞

# 约束满足问题 #

约束满足问题在人工智能领域有着广泛的应用。比如新的学期教室的规划分配，飞机场跑道的占用情况，它们都涉及了约束条件。我们所熟知的经典的皇后问题、幻方问题都属于约束满足问题。约束满足问题可以分为二元约束满足问题和多元约束满足问题。其中，多元约束满足问题可以被划分为等价的二元约束满足问题。因而，研究二元约束满足问题是一个重要的研究方向。在已有的约束传播技术中，弧相容（AC）出现的最早，在求解中也应用的最为广泛。在BT算法中，维持弧相容算法（maintaining arc consistency，简称MAC）也被认为是处理大规模难解问题的最有效的一般方法。

约束可满足问题）约束可满足问题（CSP）<X, D, C> 包括3部分：
      变量集X= { x_1, x_2, ... x_n } 由n个变量组成；
      论域集D= { D(x_1), D(x_2), ... D(x_n) } 是变量域构成的集合，其中D(x_i)表示变量x_i对应的变量域；
      约束集合C= { c_1, c_2, ... c_e } 是由e个约束组成的约束集合。

如下为一个约束满足问题的示例：

<?xml version="1.0" encoding="UTF-8"?>
    
    -<instance>
    
    <presentation nbSolutions="?" name="?" maxConstraintArity="10" format="XCSP 2.0">This is a random instance generated from RBGenerator.</presentation>
    
    
    -<domains nbDomains="1">
    
    <domain name="D0" nbValues="3">1..3</domain>
    
    </domains>
    
    
    -<variables nbVariables="3">
    
    <variable name="V0" domain="D0"/>
    
    <variable name="V1" domain="D0"/>
    
    <variable name="V2" domain="D0"/>
    
    </variables>
    
    
    -<relations nbRelations="2">
    
    <relation name="R0" semantics="conflicts" nbTuples="6" arity="2">1 2|1 3|2 1|2 3|3 1|3 2|</relation>
    
    <relation name="R1" semantics="conflicts" nbTuples="6" arity="2">1 1|2 1|2 2|3 1|3 2|3 3|</relation>
    
    </relations>
    
    
    -<constraints nbConstraints="2">
    
    <constraint name="C0" arity="2" scope="V0 V1" reference="R0"/>
    
    <constraint name="C1" arity="2" scope="V1 V2" reference="R1"/>
    
    </constraints>
    
    </instance>

此约束满足问题中有3个变量：x0,x1,x2

其中：x0的论域是\{1,2,3\}

x1的论域是\{1,2,3\}

x2的论域是\{1,2,3\}

约束由元组的形式给出，support给出的是支持元组，confilct给出的是不支持元组。

约束c0=\{(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)\}

约束c1=\{(1,1),(2,1),(2,2),(3,1),(3,2),(3,3)\}

c0和c1表示的都是不支持的元组

图示为此CSP。