变量和取值顺序

回溯算法包括这样一行：

var←SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,cap)

缺省情况下，SELECT-UNASSIGNED-VARIABLE简单地按照列表VARIABLES[csp]给出的次序选择下一个要赋值的变量。这种静态的变量排序很少能造成高效的搜索。例如，在赋值WA = red和NT = green之后，SA只剩下一个可能的赋值，因此下一个赋值SA = blue要比给Q赋值有意义。实际上，在给SA赋值之后，Q，NSW和V的选择都是强制性的了。这种直观的想法——选择“合法”取值最少的变量——称为最少剩余值（MRV）启发式。也称为“最受约束变量”或“失败优先”启发式，后者的叫法是因为它选择了最可能很快导致失败的变量，从而对搜索树剪枝。如果有一个变量X没有剩余可选的合法值，那么MRV启发式将选择X并马上检测到失败——避免其它最终也会选择X的无意义的搜索再进行下去。图5.5中的第二列标着BT+MRV，显示了这种启发式的性能。取决于不同的问题，它的性能比简单的回溯算法好3到3000倍。注意我们的性能评价忽略了计算启发值的额外开销；下一小节将描述一种使这种开销容易处理的方法。

MRV启发式在澳大利亚问题中对选择第一个染色区域根本没有帮助，因为初始的时候每个区域都有三种合法的颜色。在这种情况下，提出了度启发式。它通过选择涉及对其它未赋值变量的约束数最大的变量来试图降低未来选择的分支因子。在图5.1中，SA是有最高的度的变量，它的度为5；其它变量的度为2或者3，除了T的度为0。实际上，一旦选择了SA，应用度启发式求解问题可以不走错任何一步——你可以在每个选择点上选择任何相容的颜色，最后仍然可以不回溯就找到解。最少剩余值启发式通常是一个更强的指导，而度启发式则对打破僵局有用。

一旦一个变量被选定，算法就要决定检验它的取值的次序。为此，最少约束值启发式在某些情况下是有效的。它优先选择的值是在约束图中排除邻居变量的可选值最少的。例如，假设在图 5.1 中，我们已经部分赋了值，WA = red和NT = green，我们下一步要为Q选择值。这里蓝色不是一个好的选择，因为它消除了Q的邻居SA的最后一个可选合法值。最少约束值启发式因此更愿意选择红色而不是蓝色。一般来说，启发式应该试图给剩下的变量赋值留下最大的灵活性。当然，如果我们试图找到问题的所有解，而不只是第一个解，那么这个排序就无所谓了，因为无论如何我们要考虑每种情况。当问题没有解的时候也是一样。