annotations - MiniZinc 中的影响搜索注释有什么作用？

Question

在 MiniZinc 中可以使用搜索注解效果，官网解释如下：

注释影响

在搜索过程中选择迄今为止影响最大的变量

这在实践中意味着什么？最大的影响是什么？这是如何计算的？

Answer 1

要了解impact基于变量的选择，您必须了解first_fail. 在约束规划中，我们通常希望首先解决最困难的子问题，如果找不到解决方案则迅速失败。问题first_fail在于它没有考虑变量所涉及的约束的数量，更多表明对变量的决策“更难”，或者对变量的选择对其他部分的影响搜索树。

作为旁注，dom_w_degis 可以看作是 和 之间的妥协first_fail，impact其中考虑了约束，但过去的决定没有。

impact变量选择应该是一种改进first_fail，不仅要考虑域大小，还要考虑它所涉及的约束以及历史选择有多少“影响”。考虑到所有这些信息，影响最大的变量是预计最难分配正确值的变量。

如您所见，MiniZinc 没有提供如何做出变量选择的准确规范。由求解器实现者选择适合求解器的启发式方法。请注意，很难提供准确的启发式指南，因为它在很大程度上取决于求解器如何跟踪其变量和约束。

有关基于影响的启发式可能实现的想法，我建议阅读 Marco Correia 和 Pedro Barahona 的论文“基于影响的启发式的效率”。您还可以检查特定的 MiniZinc/FlatZinc 求解器以了解启发式的实现。