约束满足问题 CSP问题的回溯搜索 约束满足问题的局部搜索
提示：以下是本篇文章正文内容，下面案例可供参考
一、约束满足问题是什么？约束满足问题包含一组变量和一组变量间的约束。找到所有变量的一个（或多个）赋值，使所有约束都得到满足。
举一个经典的例子：澳洲版图的颜色填充（ Map-Coloring） 变量集合是各个州郡的单词简写：WA,NT,Q,NSW,V,SA,T 值域：D={red，green，blue} 约束：相邻域的颜色不同
以上就是经典的约束满足问题的例子：颜色填充 下图则是该问题所有解中的一个 为了方便解题，可以将地图转换成约束图（Constraint graph）的方式：节点表示变量，弧表示约束。如下图所示： ps：约束分为绝对约束和偏好约束两个等级，绝对约束要求任何违反规则的都排除在解之外；偏好约束指出哪些解是更偏好的。
二、CSP问题的回溯搜索 回溯搜索（Backtracking search）回溯搜索与深度优先搜索概念上非常相似： 但是在DFS中，我们假定通过应用所有可能的操作将节点添加到边缘来扩展节点（然后，如果需要，这些节点将位于边缘上，准备进一步扩展） 回溯搜索仅需执行一个操作即可生成一个后继节点，然后继续向下操作（然后，如果需要，随后返回该节点，将检查是否可以生成其他任何后继节点。
针对填色问题的回溯描述 如图，对版图随机挑选一个州进行随机着色，当程序走到图中最下层时出现一个问题，如果程序选择红色框起来的选项，那么在对中下部分的州，进行下一层的着色时发现，没有哪一种颜色可以符合两个州郡之间颜色不一样这一约束的。
这时程序将返回到红色框圈起来的这一步，并选择与其在同一层的蓝色圆圈的选择，这一当尝试选择失败，返回上一级，对上一级重新做选择的操作成为回溯操作。
需要注意的是，一般回溯是顺序试探，可能无用，应有一定的策略避免无用搜索。
在回溯搜索中，我们可以发现四个问题： 1，下一步选什么变量？按什么顺序尝试它的值？ 2，如何减少搜索空间？ 3，当前变量与未赋值变量的关系是什么？ 4，如何避免失败，即当一条路径失败时，搜索后面的路径如何避免这种失败
下面我们以此解决这些问题
选择变量的策略一：MRV启发式如图，当我们走完第一步和第二部时，在选择SA为第三步还是Q为第三步，首先分析可供SA和Q选择的颜色数量，我们发现Q有两种颜色可选，而SA只有一种。所以MRV启发式通过优先选择最少剩余量的选项来做出正确选择。
选择变量的策略二：度（degree）启发式如图所示，着色时按照变量与其他变量之间存在的约束数量由多到少的顺序进行着色。
选择变量的策略三：最少约束值（Least constraining value）启发式当进行红色方框圈起来的步骤时，有两种着色选择（蓝色和红色），我们尽量不选择之前着色没有出现过的颜色，将