查找範圍我對21個變量以下不等式：本21變不平等
http://pastebin.com/raw.php?i=FTU970Em
當我運行「減少[ineq，整數]」，數學掛起了 很長一段時間。
這是有道理的：x [1] .. x [21]有許多值， 滿足不等式。
我真正想要的是每個變量（例如，「2 < = x [i] < = 7」 ）。
我怎樣纔能有效地得到這個數學/ Mathematica？有沒有更好的 這個程序？
注：這是更大的項目的一部分：
Partially re-create Risk-like game based on incomplete log files
不平等的整個可怕的名單：http://pastebin.com/CyX9f70J
運行 「減少[ineq，整數]」 上述收益率「假「，所以我 可能不正確的翻譯： http://conquerclub.barrycarter.info/ONEOFF/7460216.html
是否有多組值滿足不等式？
我跑通過數學以下命令：
In[14]:= ineqs = {x0 == 3, x1 >= 1, x1 <= x0, x2 >= 1, x2 <= x1,
x3 >= 1, x3 <= x2, x4 >= 1, x4 <= x3, x5 <= x4 + 3, x5 >= 1,
x6 >= 1, x6 <= x5, x7 >= 1, x7 <= x6, x8 >= 1, x8 <= x7, x9 >= 1,
x9 <= x8, x10 >= 1, x10 <= x9, x11 >= 1, x11 <= x10, x12 >= 1,
x12 <= x11, x13 >= 1, x13 <= x12, x14 <= x13 + 4, x14 >= 1,
x15 >= 1, x15 <= x14, x16 >= 1, x16 <= x15, x17 <= x16 + 6,
x17 >= 1, x18 >= 1, x18 <= x17, x19 >= 1, x19 <= x18, x20 >= 1,
x20 <= x19, x21 >= 1, x21 <= x20, x21 == 1};
In[15]:= vars =
Union[{x0, x1, x1, x2, x2, x3, x3, x4, x4, x5, x5, x6, x6, x7, x7,
x8, x8, x9, x9, x10, x10, x11, x11, x12, x12, x13, x13, x14, x14,
x15, x15, x16, x16, x17, x17, x18, x18, x19, x19, x20, x20, x21,
x21, x21}];
In[16]:= FindInstance[ineqs, vars]
，並得到了結果：
Out[16]= {{x0 -> 3, x1 -> 1, x10 -> 1, x11 -> 1, x12 -> 1, x13 -> 1,
x14 -> 1, x15 -> 1, x16 -> 1, x17 -> 1, x18 -> 1, x19 -> 1, x2 -> 1,
x20 -> 1, x21 -> 1, x3 -> 1, x4 -> 1, x5 -> 1, x6 -> 1, x7 -> 1,
x8 -> 1, x9 -> 1}}
我一直沒能說服數學提供另一組的任務和一些工作用鉛筆和紙不會指向其他任務組。但是這裏遲到了，我可能錯過了一些明顯的東西。
我很確定將x1更改爲2也可以。實際上，我認爲很多形式的序列（3,3,3 ..，1,1,1）也可以工作。大多數xi（x0，x5，x14，x17，x21除外）的方程式是相同的，所以我很確定在x1和x4之間的任何點都會發生從3到1的下降（例如）。 – barrycarter 2010-10-01 23:30:11
OK，事實證明，解決這個特殊的方程組是 容易，一旦你重寫他們中的一些稍微：
x5 <= x4 + 3 becomes x5 - 3 <= x4
x6 <= x5 becomes x6 - 3 <= x5 - 3
，並依此類推，直至：
x13 <= x12 becomes x13 - 3 <= x12 - 3
x14 <= x13 + 4 becomes x14 - 7 <= x13 -3
通過這樣做，{x0，x1，x2，x3，x4，x5-3，x6-3，...，x13-3，x14-7，...，x21} 成爲從3開始的嚴格遞減的整數序列 並以1結尾。
事實上，任何序列w /該屬性的作品，因爲xi> = 1是微不足道的 滿意。
然而，雖然這可以解決這一特定的 不等式組合，但它通常不起作用，所以我不認爲它是一個完整的解決方案。
我第二次在另一個線程給出的CLP（FD）建議。使用SWI-Prolog 5。10：
:- use_module(library(clpfd)).
vars([X0,X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14,X15,X16,X17,X18,
X19,X20,X21]) :-
X0 #= 3, X1 #>= 1, X1 #=< X0, X2 #>= 1, X2 #=< X1,
X3 #>= 1, X3 #=< X2, X4 #>= 1, X4 #=< X3, X5 #=< X4 + 3,
X5 #>= 1, X6 #>= 1, X6 #=< X5, X7 #>= 1, X7 #=< X6,
X8 #>= 1, X8 #=< X7, X9 #>= 1, X9 #=< X8, X10 #>= 1,
X10 #=< X9, X11 #>= 1, X11 #=< X10, X12 #>= 1, X12 #=< X11,
X13 #>= 1, X13 #=< X12, X14 #=< X13 + 4, X14 #>= 1, X15 #>= 1,
X15 #=< X14, X16 #>= 1, X16 #=< X15, X17 #=< X16 + 6, X17 #>= 1,
X18 #>= 1, X18 #=< X17, X19 #>= 1, X19 #=< X18, X20 #>= 1,
X20 #=< X19, X21 #>= 1, X21 #=< X20, X21 #= 1.
查詢示例：
?- vars(Vs), maplist(fd_dom, Vs, Ds).
Ds = [3..3, 1..3, 1..3, 1..3, 1..3, 1..6, 1..6, 1..6, ... .. ...|...]
?- vars(Vs), label(Vs).
Vs = [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ;
Vs = [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1] ;
Vs = [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1] ;
etc.
已經夠晚了，有可能是一些華而不實的削減，但這個工程......
ineq={...};
pivotAt[set_, j_] := Select[set, And[
Not[FreeQ[#, x[u_] /; u <= j]],
FreeQ[#, x[u_] /; u > j]
] &]
triangularize[set_] := Module[{left, i, new},
left = set;
Reap[
For[i = 0, i <= 21, i++,
new = pivotAt[left, i];
Sow[new];
left = Complement[left, new];
]][[2, 1]]
]
Module[{
tri,
workingIntervals,
partials, increment, i
},
tri = triangularize[ineq];
workingIntervals[set_] := set /. {
t_ <= c_ :> {t, Interval[{-\[Infinity], Max[c]}]},
t_ == c_ :> {t, Interval[{Min[c], Max[c]}]},
t_ >= c_ :> {t, Interval[{Max[c], \[Infinity]}]}};
partials = {};
increment[slice_] :=
Rule[#[[1, 1]], IntervalIntersection @@ #[[All, 2]]] &[
workingIntervals[slice /. partials ] ];
For[i = 1, i <= Length[tri], i++,
partials = Join[partials, {increment[tri[[i]]]}];
];
partials
]
這是在相關許可變量之間（「這個高意味着低」）沒有考慮。
- 編輯 -
的上面是結果，當然
{x[0] -> Interval[{3, 3}], x[1] -> Interval[{1, 3}],
x[2] -> Interval[{1, 3}], x[3] -> Interval[{1, 3}],
x[4] -> Interval[{1, 3}], x[5] -> Interval[{1, 6}],
x[6] -> Interval[{1, 6}], x[7] -> Interval[{1, 6}],
x[8] -> Interval[{1, 6}], x[9] -> Interval[{1, 6}],
x[10] -> Interval[{1, 6}], x[11] -> Interval[{1, 6}],
x[12] -> Interval[{1, 6}], x[13] -> Interval[{1, 6}],
x[14] -> Interval[{1, 10}], x[15] -> Interval[{1, 10}],
x[16] -> Interval[{1, 10}], x[17] -> Interval[{1, 16}],
x[18] -> Interval[{1, 16}], x[19] -> Interval[{1, 16}],
x[20] -> Interval[{1, 16}], x[21] -> Interval[{1, 1}]}
的雖然可以得到外部邊界等2 <= X [I] <= 7對於每個i，我不要以爲這樣的系統就等同於ineq。我認爲20維區域（x [i]，i = 1,20）不會是矩形的。 – Simon 2010-10-02 00:36:49
你絕對正確。我所說的是我會*解決*限制。我不需要有效點的整個20維點陣。那麼，有沒有辦法解決高效的界限？ – barrycarter 2010-10-02 05:17:04