求图CSP中回溯的次数
Find the number of backtrack in the graph CSP
如果在为变量 X 赋值后，X 处的递归 returns 没有
解决方案。具体来说，这意味着对于剩余 d 个值的单个变量，可以回溯
最多 d 次。对于以下每个约束图，如果每个变量都有一个大小为 d 的域，有多少个
在最坏的情况下，您必须多次回溯每个指定的顺序吗？
这是CS188的一道题Spring人工智能
这是图表
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选了一个(Blue,Green)中的x，所以我选了Blue，那么，我可以从B中消去，Blue从它的定义域中消去，所以B的值一定是Green。然后，当我查看 D 时，由于 C 被分配为蓝色，因此我知道 D 也必须被分配值 Green，并且在此过程中依此类推。
这意味着通过分配 C，我实际上已经基本上解决了这个排序的问题，这意味着最坏的情况是永远不会有任何回溯，因为通过分配 C，我已经限制了所有我所有其他节点上的域，事实上，这适用于任何大小的域（如果它适用于 2，它显然适用于我域中的 2+ 个元素）。
但是，你可能会疑惑，为什么A->E->B->D->C的顺序会有二维回溯。
好吧，这是一个例子。假设我为 A 分配了值蓝色，然后为 E 分配了绿色，为 B 分配了绿色，为 D 分配了蓝色，并且因为我为 B 分配了绿色，所以我强制 C 有蓝色，但是 C 不能有蓝色，因为 D 现在有蓝色。因此，C 在其域中没有有效元素，因此我需要回溯。
我需要回溯多少次？好吧，我必须从 D 中取消分配 Blue，但现在 D 没有有效域，所以我必须从 B 中取消分配 Green，但是，B 没有域，所以现在我必须从 E 中取消分配 green。现在，我可以继续将 Blue 分配给 E。我想在完成此操作之后，现在有 4 个回溯（C->D->B->E 回溯顺序）所以对于这个大小为 2 的域的简单示例似乎有效（这部分我对如何证明 2d 解决方案有点模糊，在我看来最坏的情况是当你对 E 的分配与你对 A 的分配不匹配时，你必须做 2*d 因为必须去通过两个半场？）
无论如何，我对 CS188 很模糊，已经好几年没学 class 了，我唯一一次不得不回到算法是为了面试学习，哈哈。这很有趣，因为我是 2014 年的 class，但我想我在秋天拍了这个 class。
希望对您有所帮助。
如果在为变量 X 赋值后，X 处的递归 returns 没有 解决方案。具体来说，这意味着对于剩余 d 个值的单个变量，可以回溯 最多 d 次。对于以下每个约束图，如果每个变量都有一个大小为 d 的域，有多少个 在最坏的情况下，您必须多次回溯每个指定的顺序吗？
这是CS188的一道题Spring人工智能
这是图表
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选了一个(Blue,Green)中的x，所以我选了Blue，那么，我可以从B中消去，Blue从它的定义域中消去，所以B的值一定是Green。然后，当我查看 D 时，由于 C 被分配为蓝色，因此我知道 D 也必须被分配值 Green，并且在此过程中依此类推。
这意味着通过分配 C，我实际上已经基本上解决了这个排序的问题，这意味着最坏的情况是永远不会有任何回溯，因为通过分配 C，我已经限制了所有我所有其他节点上的域，事实上，这适用于任何大小的域（如果它适用于 2，它显然适用于我域中的 2+ 个元素）。
但是，你可能会疑惑，为什么A->E->B->D->C的顺序会有二维回溯。
好吧，这是一个例子。假设我为 A 分配了值蓝色，然后为 E 分配了绿色，为 B 分配了绿色，为 D 分配了蓝色，并且因为我为 B 分配了绿色，所以我强制 C 有蓝色，但是 C 不能有蓝色，因为 D 现在有蓝色。因此，C 在其域中没有有效元素，因此我需要回溯。
我需要回溯多少次？好吧，我必须从 D 中取消分配 Blue，但现在 D 没有有效域，所以我必须从 B 中取消分配 Green，但是，B 没有域，所以现在我必须从 E 中取消分配 green。现在，我可以继续将 Blue 分配给 E。我想在完成此操作之后，现在有 4 个回溯（C->D->B->E 回溯顺序）所以对于这个大小为 2 的域的简单示例似乎有效（这部分我对如何证明 2d 解决方案有点模糊，在我看来最坏的情况是当你对 E 的分配与你对 A 的分配不匹配时，你必须做 2*d 因为必须去通过两个半场？）
无论如何，我对 CS188 很模糊，已经好几年没学 class 了，我唯一一次不得不回到算法是为了面试学习，哈哈。这很有趣，因为我是 2014 年的 class，但我想我在秋天拍了这个 class。
希望对您有所帮助。