algorithm - AC-3 算法和回溯

Question

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

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

它对我所有的测试用例都运行得很好而且很快，但是我的一个朋友问我这个问题：“如果最初的 AC-3 没有减少任何东西怎么办？” 并暗示我将在回溯的每一步运行 AC-3。

我有一种感觉，在这种情况下它对我没有多大帮助，但在某处我已经看到 AC-3 可以两种方式使用，但没有进一步的解释。我可以获得更多关于此的信息吗？

PS：实际上每次运行 AC-3 对我来说是无法忍受的，因为它运行大约 2 秒长。但是我出于好奇而问这个问题，当我解决其他一些问题时它会很有用。

Answer 1

由于这个问题已经死了大约一个月，我想我会自己回答。在回溯的每一步运行 AC-3 确实有好处。我遇到过这样的问题，最初的 AC-3 并没有减少太多，但随后修复了一些变量的问题要成功得多。