2.4 排序 (Ordering)
我们已经指出，在解决 CSP 时，我们会对涉及的变量和值确定某种顺序。在实践中，使用两个广泛的原则“即时”计算下一个变量和相应的值通常更有效：最小剩余值 (minimum remaining values) 和 最少约束值 (least constraining value)：
- 最小剩余值 (Minimum Remaining Values, MRV) - 当选择下一个要赋值的变量时，使用 MRV 策略选择具有最少有效剩余值的未赋值变量（即受约束最多的变量）。这在直觉上是合理的，因为受约束最多的变量如果不赋值，最有可能耗尽可能的值并导致回溯，因此最好尽早给它赋值。
- 最少约束值 (Least Constraining Value, LCV) - 同样，当选择下一个要赋值的值时，一个好的策略是选择从剩余未赋值变量的定义域中修剪最少值的那个值。值得注意的是，这需要额外的计算（例如，为每个值重新运行弧一致性/前向检查或其他过滤方法以找到 LCV），但根据使用情况，仍然可以获得速度提升。
2.4.1 结构 (Structure)
解决约束满足问题的最后一类改进是利用其结构的那些方法。特别是，如果我们试图解决一个 树状结构 CSP (tree-structured CSP)（其约束图中没有环），我们可以将寻找解的运行时间从 \(O(d^N)\) 一路减少到 \(O(nd^2)\)，即与变量数量成线性关系。这可以通过树状结构 CSP 算法来实现，概述如下：
- 首先，在 CSP 的约束图中选择一个任意节点作为树的根（选哪个并不重要，因为基本的图论告诉我们树的任何节点都可以作为根）。
- 将树中的所有无向边转换为指向远离根的方向的有向边。然后线性化 (linearize)（或拓扑排序 (topologically sort)）生成的有向无环图。简单来说，这只是意味着对图的节点进行排序，使得所有边都指向右侧。注意我们选择节点 \(A\) 作为我们的根，并将所有边指向远离 \(A\) 的方向，这个过程导致了下面展示的 CSP 的转换：
- 执行弧一致性的反向传递 (backwards pass)。从 \(i = n\) 迭代到 \(i = 2\)，对所有弧 \(Parent(X_i) \longrightarrow X_i\) 强制执行弧一致性。对于上面的线性化 CSP，这种定义域修剪将消除一些值，留下以下内容：
- 最后，执行前向赋值 (forward assignment)。从 \(X_1\) 开始一直到 \(X_n\)，为每个 \(X_i\) 分配一个与其父节点一致的值。因为我们已经在所有这些弧上强制执行了弧一致性，无论我们为任何节点选择什么值，我们都知道它的子节点将各自至少有一个一致的值。因此，这种迭代赋值保证了一个正确的解，这一事实可以毫无困难地通过归纳法证明。
树状结构算法可以通过割集调节 (cutset conditioning) 扩展到相当接近树状结构的 CSP。割集调节涉及首先在约束图中找到最小的变量子集，使得它们的移除导致一棵树（这样的子集被称为图的割集 (cutset)）。例如，在我们的地图着色示例中，南澳大利亚 (\(SA\)) 是最小的可能割集：
一旦找到最小割集，我们就为其中的所有变量赋值，并修剪所有相邻节点的定义域。剩下的是一个树状结构 CSP，我们可以使用上面的树状结构 CSP 算法来解决它！对大小为 \(c\) 的割集的初始赋值可能会在修剪后使生成的树状结构 CSP 没有有效解，因此我们可能仍然需要回溯最多 \(d^c\) 次。由于移除割集给我们留下了一个具有 \((n - c)\) 个变量的树状结构 CSP，我们知道这可以在 \(O((n - c)d^2)\) 内解决（或确定不存在解）。因此，割集调节在一般 CSP 上的运行时间是 \(O(d^c(n-c)d^2)\)，对于小的 \(c\) 来说非常好。