1

我已经开始在我的工作中使用 choco-solver 并且不了解传播者和搜索策略如何相互配合。

我认为 choco 有一些标志可以告诉我在传播过程中是否有任何约束变量域发生了变化。如果有，那么传播会一次又一次地开始，直到没有发生域更改。之后，如果约束仍然不满足或失败，搜索策略将连接到求解过程。

但是我的程序的输出告诉我我错了。Propogator 确实工作了 2 或 3 次，每次都更改域，但随后调用了搜索策略。

请帮助我，我的结论哪里错了？或者它应该按照我的想法工作并且我的代码中有一些错误导致错误的输出？

对不起，我的英语不好

4

2 回答 2

4

Choco 是一个约束编程求解器，这些求解器都按照相同的原理工作。

与蛮力搜索不同，约束求解器将首先调用所有（相关）传播器以从变量域中删除它知道变量不能接受的值。调用一个传播器可能会触发新值变得不可能，因此可能会触发其他传播器再次运行。

一旦所有传播者报告他们无法删除更多值（我们称之为修复点），将咨询搜索策略以查看下一步该做什么。（一般来说，这是对应该是什么解决方案的猜测，我们可能需要回溯）。

如果所有变量只有一个可能的值，这是一个解决方案。但是，在我们的搜索中，变量可能会丢失所有可能的值。在这种情况下，传播者将失败。如果我们已经使用了搜索，我们将需要回溯。如果这是在根节点，则意味着问题无法解决。

有关更多信息，请尝试几个约束求解器的教程。其中很多都可以在Wikipedia上找到。您也许还可以找到在线课程。

于 2017-09-28T12:28:24.143 回答
0

为了完成 Dekker 的回答，根据我的经验，在实践中通常会在相当少的迭代中达到修复点。这仍然可能很慢（因为有很多约束，或者因为“全局约束”可能传播缓慢），但乒乓效应很少有戏剧性的。Choco Solver 和类似的求解器有许多技巧可以有效地传播......

因此，每个传播器在分支之前只调用 2-3 次是完全可以的。

于 2017-10-03T23:46:32.190 回答