当一个变量X被赋值后，如果递归在X处返回且没有找到解，就需要进行回溯。具体来说，这意味着对于一个剩余d个值的单一变量，可能需要回溯最多d次。对于以下每个约束图，如果每个变量的域大小为d，在最坏情况下，按照指定的顺序需要回溯多少次？

这是CS188春季人工智能课程中的一个问题

这是图形

A->B->C->D->E

问题：C-B-D-E-A回溯次数：0

为什么这仍然被认为是线性排序？我不明白为什么E-A仍然不被认为有回溯，因为要从E到A，你将被迫回溯并经过3个变量。请帮助我。谢谢……

回答：

看这个问题，我想我可以说明你是如何得出答案的。

重新定义一下，假设我将这个问题描述为一个有5个节点A、B、C、D、E的着色问题。

每个节点可以有这个域集。（蓝色，绿色），我的约束是，没有节点可以与其右侧的节点有相同的颜色。

然后，假设我按照这个顺序C->B->D->E->A开始为这个CSP分配值，

这意味着，我为C选择一个x在（蓝色，绿色）中。所以我选择蓝色，然后，我可以从B的域中排除蓝色，所以B必须是绿色。然后，当我查看D时，由于C被分配了蓝色，我知道D也必须被分配绿色，依此类推。

这意味着，通过分配C，我实际上已经解决了这个问题，按照这个顺序继续下去，最坏的情况是不会有任何回溯，因为通过分配C，我已经约束了所有其他节点的所有域，事实上，这对于任何大小的域都是正确的（如果它对2有效，那么显然对域中的2+元素也有效）。

然而，你可能会想，为什么顺序A->E->B->D->C会有2D次回溯。

好吧，这里有一个例子。假设我为A分配了蓝色，然后为E分配了绿色，为B分配了绿色，为D分配了蓝色，由于我为B分配了绿色，我已经迫使C必须是蓝色，但C不能是蓝色，因为D现在是蓝色。因此，C在其域中没有有效元素，所以我需要回溯。

我需要回溯多少次呢？好吧，我必须取消D的蓝色分配，但现在D没有有效域，所以我必须取消B的绿色分配，然而，B没有域，所以现在我必须取消E的绿色分配。现在，我可以通过为E分配蓝色继续。我认为在做了这些之后，现在已经有4次回溯（C->D->B->E回溯顺序），所以看起来对于这个简单例子，域大小为2是有效的（关于证明有2d解的部分，我有点模糊，看起来最坏的情况是当你对E的分配与对A的分配不匹配时，你必须进行2*d次，因为你必须经过两半？）

无论如何，我对CS188有点模糊，已经多年没上这门课了，我唯一回顾算法的时候是为了准备面试，哈哈。因为我是2014届的，但我记得我是在秋季上的这门课。

希望这对你有帮助。