如何在Gecode中实现“嵌套”的成本函数？

Question

一般来说，我对gecode和约束编程是个新手。

到目前为止，我在拾取gecode时并没有遇到太多问题，它非常棒。但我想知道执行“嵌套”成本函数的最佳方式是什么。具体地说，我希望最小化X，但在X相等的解空间内，更喜欢最小化Y的解决方案？我也许可以通过定义一个看起来像X*large_number+Y的成本函数来破解它，但如果有一个好的解决方案，我更愿意这样做。

如果有人能告诉我如何在Gecode中实现这一点，那将会非常有帮助。谢谢!

Answer 1

您可以在Gecode中使用空格中的constrain成员来定义任何类型的优化条件。有关示例，请参阅Modeling and Programming with Gecode中的第2.5节。在您的例子中，最直接的方法是添加一个constrain成员，该成员在先前的最佳解决方案答案和当前空间之间添加字典顺序的约束。

也就是说，一般来说，基于字典顺序的优化可能是浪费的(过多的搜索)。通常，首先运行搜索来优化第一个组件(在您的示例中是X)可能会更好。之后，使用固定的第一个组件值(X设置为最佳可能值)重新运行搜索，并优化第二个值(在本例中为Y)。根据需要对成本中的所有元素进行迭代。