约束满足问题(Constraint Satisfaction Problem, CSP)的Java实现（一）原理部分

问题的定义

在这里插入图片描述
一个约束满足问题由三个部分组成，即变量，可行域，约束。按照本人理解，变量为需要求解的量，可行域为变量中每个变量对应的可选择的值域，一般考虑为离散的问题。约束一般分为unary constraint, binary constraint,和多约束，但多约束也可以转换为binary constraint。
unary constraint:
$T_1 \neq d_1$
binary constraint:
$T_1 + d_1 \leq T_2$
多约束：
$T_1 + T_2 \leq T_3$

约束的预处理：Inference

Node consistency 节点相容

A single variable (corresponding to a node in the CSP network) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints. For example, in the variant of the Australia map-coloring problem (Figure 6.1) where South Australians dislike green, the variable SA starts with domain {red , green, blue}, and we can make it node consistent by eliminating green, leaving SA with the reduced domain {red , blue}.
即通过将变量可行域中，不满足单约束的值提前去掉。

Arc consistency 弧相容

A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints. 对于 $X_i$ 来说，如果其域中的每一个值 $D_i$ ,在 $X_j$ 的域中都有一个值 $D_j$ 能够满足其条件，则说明 $X_i$ 对 $X_j$ 是弧相容的。在预处理中，我们需要让所有点都弧相容，因此我们会检测每一段弧，并将不符合要求的domain剔除。如果最后有domain的大小为0，则说明问题无解。一般采用AC-3算法实现。
在这里插入图片描述

回溯搜索与变量排序

回溯搜索一般采用DFS配和剪枝进行。

MRV排序

Minimum-remaining-values (MRV) heuristic. It also has been called the “most constrained variable” or REMAINING-VALUES “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. If some variable X has no legal values left, the MRV heuristic will select X and failure will be detected immediately—avoiding pointless searches through other variables. The MRV heuristic usually performs better than a random or static ordering, sometimes by a factor of 1,000 or more, although the results vary widely depending on the problem.
MRV选择具有最少可行值得变量进行排序，先用最少得，可以保证能够“快速失败”