如何在Gecode中实现'嵌套'成本函数？

Question

我是通用的gecode和约束编程的新手。

到目前为止，我没有太多麻烦拿起gecode，这很好。但我想知道执行“嵌套”成本函数的最佳方法是什么。具体而言，我期望尽量减少X，但在X相等的解决方案空间内，更喜欢将Y最小化的解决方案？我可以通过定义一个看起来像X * large_number + Y的成本函数来破解它，但如果有一个好的解决方案，我宁愿这样做。

如果任何人都可以指出我解释如何在Gecode中实现这个，那真的很有帮助。谢谢！

Answer 1

您可以使用约束成员在Gecode空间中定义任何类型的优化标准。以Modeling and Programming with Gecode中的第2.5节为例。就你而言，最简单的方法是添加一个约束成员，在先前的最佳解答和当前空间之间添加一个词典约束。

这就是说，一般来说，基于字典顺序的优化可能是浪费（太多搜索）。首先运行搜索优化第一个组件（在您的案例中为X）往往会更好。之后，重新运行搜索时将第一个组件值固定（X设置为最佳可能值），并优化第二个值（在您的情况下为Y）。根据需要迭代成本中的所有元素。