约束满足问题的介绍约束满足问题

122 阅读 0 评论 81 点赞

我是靠谱客的博主正直音响，这篇文章主要介绍约束满足问题的介绍约束满足问题，现在分享给大家，希望可以做个参考。

约束满足问题

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

复制代码

1
2
3
4
约束可满足问题）约束可满足问题（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个约束组成的约束集合。

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<?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>