约束满足问题

  约束满足问题在人工智能领域有着广泛的应用。比如新的学期教室的规划分配，飞机场跑道的占用情况，它们都涉及了约束条件。我们所熟知的经典的皇后问题、幻方问题都属于约束满足问题。约束满足问题可以分为二元约束满足问题和多元约束满足问题。其中，多元约束满足问题可以被划分为等价的二元约束满足问题。因而，研究二元约束满足问题是一个重要的研究方向。在已有的约束传播技术中，弧相容（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。

最后

以上就是正直音响为你收集整理的约束满足问题的介绍约束满足问题的全部内容，希望文章能够帮你解决约束满足问题的介绍约束满足问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。