什么时候应该停止扩展CSP的视野？

Question

您应该何时停止扩大CSP规划师的视野？ 具体来说，是否存在约束满足问题规划器的一个条件，即当在某个范围内与搜索的弧一致性失败时，意味着弧的一致性也将在所有更长的范围内失败。

Answer 1

如果您的计划者非常普遍，答案必须是否定的。

假设您的约束系统足够普遍，它可以检查“此矩阵的每一行对应于图灵机的磁带，而行i是第i步和最后一行之后的图灵机状态的快照表明图灵机已停止“。

然后“我发现一个满足约束条件的矩阵”对应于“这个图灵机已经停止”，并且通过https://en.wikipedia.org/wiki/Halting_problem几乎找出图灵机或其他一般计算已停止的唯一方法就是玩东西并等待看它是否停止。