如果在将值分配给变量 X 后，递归返回 X 处没有解决方案，则必须回溯。具体来说，这意味着对于剩余 d 个值的单个变量，最多可以回溯 d 次。对于以下每个约束图，如果每个变量都有一个大小为 d 的域，那么在最坏的情况下，对于每个指定的排序，您必须回溯多少次？
这是 CS188 Spring 人工智能的一个问题
这是图表
A->B->C->D->E
问题：C-B-D-E-A
回溯数：0
为什么这仍然被认为是线性排序？我不明白为什么 EA 仍然不被认为是从 E 到 A 的回溯，你将被迫返回并将通过 3 个变量。请帮忙。谢谢....
看看这个问题，我想我可以说明你如何在这里得出答案。
为了重新定义，假设我将此问题说明为具有 5 个节点 A、B、C、D、E 的着色问题。
每个节点都可以拥有这组域。（蓝色，绿色）和我的约束，没有节点可以与右侧节点具有相同的颜色。
然后，假设我开始按 C->B->D->E->A 的顺序为这个 CSP 赋值，
这意味着，我为 C 选择了 (Blue, Green) 中的 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 级的，但我想我是在秋天上这门课的。
希望这可以帮助。