AC-3算法与回溯

Question

我使用以下方法解决了一个CSP问题：

1. 运行AC3以减少可变域
2. 使用简单的回溯找到解决方案。

它对我所有的测试都很有效，但是我的一个朋友问我：“如果最初的AC-3没有减少任何东西怎么办？”这意味着我将在回溯的每一步运行AC-3。

我有一种感觉，在这种情况下，它对我没有多大帮助，但在某个地方，我看到AC-3可以双向使用，但没有进一步的解释。我能得到更多这方面的信息吗？

PS:实际上，在我的情况下，每次运行AC-3是无法忍受的，因为它的运行时间约为2秒。但我问这个问题是出于好奇，当我要解决其他问题时，它可能是有用的。

Answer 1

既然这个问题已经死了一个月了，我想我会自己回答的。在回溯的每一步中运行AC-3确实有好处。我已经解决了这样的问题，最初的AC-3并没有减少多少，但随后的问题，一些变量是固定的，要成功得多。