隨機解決一組整數約束條件

我有一組整數約束，我想解決。約束可以由大於，小於或等於某個常數的變量組成。隨機解決一組整數約束條件

實施例：

A >= 20 
A <= 30 
B <= 10 
A + B <= 25 
...

將有幾百個這種簡單的約束條件，並且常數大得多的值（幾十萬）在實踐中。

不過，我不只是要一個解決這些制約因素：我想從解空間的一個隨機解決方案。這並不意味着每個解決方案都必須具有相等的概率（我認爲沒有枚舉它們全部都不可能），但是我想要的是，例如對於變量A，解決方案通常不是20或30，而是在兩者之間的數值可能（或甚至更可能）被挑選出來。

什麼技術適合這種問題？我很難知道在哪裏看，因爲大多數算法都着眼於尋找最優或最快的解決方案，而不是隨機的解決方案。

來源

2013-12-23 Wouter Lievens

一個（可能是極其低效的）方法是[試錯（HTTPS ：//en.wikipedia.org/wiki/Trial_and_error）：在空間中生成一個隨機點並測試它是否滿足所有約束條件。重複，直到一個點通過。 –

約束也是線性的嗎？任何術語是兩個或更多變量的乘積嗎？ – phs

domian有什麼問題？它可能會對如何解決這個問題提供一些見解。 – corsiKa

許多約束編程系統有一個搜索啓發式（稱爲「indomain_random」或類似的東西），它給出隨機順序（給定一些種子）的解決方案。這裏有一個MiniZinc模型一個簡單的問題：

var 20..30: A; 
var 0..10: B;  
solve :: int_search([A,B], first_fail, indomain_random, complete) satisfy; 
constraint A + B <= 25; 
output [ show([A,B])];

這裏的一對夫婦使用Gecode的FlatZinc求解種子的一些解決方案：

Seed Solution 
--------------- 
0  [22,0] 
2  [25,0] 
3  [22,2]

來源

2013-12-24 06:36:08 hakank

感謝您的提示。我的項目是用Java編寫的，之前我已經涉足JaCoP，似乎它支持這種啓發式。我會看看。 –

它似乎像一個魅力工作。用JaCoP很容易實現，我得到了看似隨機的結果。謝謝你的提示！ –

可能有趣的是，知道在啓發式中使用隨機化會給出隨機結果，但它並不能保證在可能的解決方案上進行任何形式的分佈。還有更高級的技術可以用來有效地啓發式地抽樣整個解決方案空間，但這可能比這裏需要的更多。兩個示例是http://books.nips.cc/papers/files/nips19/NIPS2006_0084.pdf和http://www.auai.org/uai2012/papers/160.pdf。 – Zayenz

我會從與其他節點的變量交互的所有節點之間建立關係開始。

對圖進行標記，標記所有不依賴於其他節點的節點。然後遍歷依賴於這些節點的每個節點，縮小它們的範圍（增加min和減少max），使它們的公式保持一致。所以如果你有A.min=10, A.max=20, B.min = 10, A+B=25你可以把A.max改成15（因爲B必須是10，而25-10 = 15）。你剛剛減少了50％的範圍。

如果建立主節點，這會變得更容易：如果A + B = 25，A是依賴於B還是B依賴於A？使圖形成爲有向圖更容易處理，因爲在有向圖中算法更簡單。

一旦你完成了所有這些，你會注意到島嶼出現了：這是一件好事，因爲島嶼代表提供分離牆的單獨圖形 - 如果嘗試試錯法，則只需要重試島嶼未能進入一致的狀態。

來源

2013-12-23 22:46:11 corsiKa

不是一個真正的完整的答案，但也許是有用的，太長評論：

它可以幫助你知道，解空間是凸的。意思是，如果你有兩個解決方案A1, B1, C1和A2, C2, B2，那麼它們之間的任何三元組也是一個解決方案。

（這裏，「在...之間」意味着在該範圍內[0,1]一些實數t，使得：

Anew = t * A1 + (1 - t) * A2
Bnew = t * B1 + (1 - t) * B2
Cnew = t * C1 + (1 - t) * C2

要查看爲什麼，你可以嘗試將這些表達式插入你的不等式中，並且不等式w生病擴大爲真，因爲他們這樣做是爲了A1, B1, C1和A2, B2, C2。）

您可以使用此信息限制您需要搜索的n空間的區域。例如，如果您找到一個解決方案，並且您想知道您的解決方案空間在某個方向上有多遠，則可以將二進制搜索運行到已知解決方案。等...

來源

2013-12-23 22:50:36

隨機解決一組整數約束條件

回答

相關問題