如何在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）。根據需要迭代成本中的所有元素。