CSP问题
对于CSP问题的形式化描述如下:
- 变量
- 值域:每个变量都有自己的值域；
- 约束集描述变量的取值:有一个变量元组和一个显式的关系函数式描述，例如
- 状态有部分或者全部变量的赋值来描述：
- 一个合法的赋值不违反任何约束条件；
- 一个完整的赋值意味着对每个变量都有赋值；
- CSP问题的解式全体合法的，完整的赋值的状态
地图着色问题
四色定理就是一类地图着色问题，也是经典的CSP问题：每一个地图（三连通的简单平面图）都是四面可染色的，也即对任意三正则地图均有;
对于Australian Map，CSP形式化如下：
- 一个可行的解为
Varieties of CSPs
对于CSP问题，可以根据变量类型和值域类型进行分类：
-
离散变量
-
有限值域：size means for complete assignment
著名的有SAT问题，这是个NPC问题；
-
无限值域：例如Job scheduling
-
-
连续变量
- 例如：start/end times for hubble telescope observations
Backtracking Search
类似于DFS，回溯搜素算法式解决CSP问题的基础的无信息算法，可以描述如下：
- One variable at a time：因为CSP问题都是可交换的，就像[WA = red then NT = green] same as [NT = green then WA = red]，因此在每一步只需要考虑一个变量；
- Check constraints as you go：固定下一个变量之前，检查约束条件，使得已固定的变量不会相互冲突；
以下是Australian Map的一棵搜索树：
以下是算法伪代码：
简单来说，Backtracking = DFS + variable-ordering + fail-on-violation；
