3

我对 21 个变量有以下不等式：

http://pastebin.com/raw.php?i=FTU970Em

当我对此运行“Reduce[ineq,Integers]”时，Mathematica 会挂起很长时间。

这是有道理的：x[1]..x[21] 有许多满足不等式的值集。

我真正想要的只是每个变量的界限（例如，每个 i 的“2 <= x[i] <= 7”）。

我怎样才能通过 Mathematica 有效地得到这个？有没有更好的程序呢？

注意：这是较大项目的一部分：

根据不完整的日志文件部分重新创建类似风险的游戏

整个可怕的不平等列表：http: //pastebin.com/CyX9f70J

在上面运行“Reduce[ineq,Integers]”会产生“false”，所以我可能翻译错误： http ://conquerclub.barrycarter.info/ONEOFF/7460216.html

4

4 回答 4

3

我支持另一个线程中给出的 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.
于 2010-10-03T00:06:47.220 回答
0

是否有许多组满足不等式的值？

我通过 Mathematica 运行了以下命令：

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}}

我无法说服 Mathematica 提供另一组作业，并且用铅笔和纸做一点工作并没有将我指向其他作业集。但是这里已经很晚了，我可能错过了一些明显的东西。

于 2010-10-01T23:03:28.307 回答
0

好的，事实证明，求解这组特定的方程很容易，只要稍微重写其中一些方程：

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 结束。

事实上，任何具有该属性的序列都有效，因为 xi>=1 非常满足。

然而，虽然这可以解决这组特定的不等式，但它通常不起作用，所以我不认为它是一个完整的解决方案。

于 2010-10-02T00:00:54.360 回答
0

已经很晚了，可能会有一些巧妙的减少，但这有效......

    不等式={...};
    pivotAt[set_, j_] := 选择[set, And[
            不是[FreeQ[#, x[u_] /; u <= j]],
                FreeQ[#, x[u_] /; u > j]
        ] &]
    三角化[set_] := 模块[{left, i, new},
        左=设置；
        收获[
            对于[i = 0, i <= 21, i++,
                新 = pivotAt[left, i];
                母猪[新];
                左=补[左，新]；
        ]][[2, 1]]
    ]
    模块[{
        三，
        工作间隔，
        部分，增量，我
        },

        tri = 三角化 [ineq];

        工作间隔[set_] := 设置 /。{
            t_ <= c_ :> {t, 区间[{-\[Infinity], Max[c]}]},
            t_ == c_ :> {t, 间隔[{Min[c], Max[c]}]},
            t_ >= c_ :> {t, 区间[{Max[c], \[Infinity]}]}};

        部分 = {};
        增量[slice_] :=
            规则[#[[1, 1]]，IntervalIntersection @@ #[[All, 2]]] &[
                工作间隔[切片/。部分]];
        For[i = 1, i <= 长度[tri], i++,
            partials = Join[partials, {increment[tri[[i]]]}];
        ];
        部分
    ]

允许变量之间的相关性（“这个高意味着那个低”）没有被考虑在内。

- 编辑 -

上面的结果当然是

{x[0] -> 区间[{3, 3}], x[1] -> 区间[{1, 3}],
 x[2] -> 区间[{1, 3}], x[3] -> 区间[{1, 3}],
 x[4] -> 区间[{1, 3}], x[5] -> 区间[{1, 6}],
 x[6] -> 区间[{1, 6}], x[7] -> 区间[{1, 6}],
 x[8] -> 区间[{1, 6}], x[9] -> 区间[{1, 6}],
 x[10] -> 区间[{1, 6}], x[11] -> 区间[{1, 6}],
 x[12] -> 区间[{1, 6}], x[13] -> 区间[{1, 6}],
 x[14] -> 区间[{1, 10}], x[15] -> 区间[{1, 10}],
 x[16] -> 区间[{1, 10}], x[17] -> 区间[{1, 16}],
 x[18] -> 区间[{1, 16}], x[19] -> 区间[{1, 16}],
 x[20] -> 区间[{1, 16}], x[21] -> 区间[{1, 1}]}
于 2010-11-04T03:54:25.410 回答