c++ - 如何在 Gecode 中实现 'nested' 成本函数？

Question

一般来说，我是地理编码和约束编程的新手。

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

如果有人可以指点我解释如何在 Gecode 中实现这一点，那将非常有帮助。谢谢!

Answer 1

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

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