arrays - Minizinc：在这种情况下我怎样才能使集合的并集（定点算法？）

Question

我有一组集合，这意味着集合中的项目必须在实际开始之前完成。例如：

before = [ {},
      {1},
      {},
      {},
      {2}];

我希望每一行都包含递归之前的行。所以在这种情况下，它应该像这样结束：

abans = [ {},
      {1},
      {},
      {},
      {1,2}];

我已经尝试生成一个变量并从空白创建集合，但我没有设法做到这一点。任何想法我怎么能做到这一点？

Answer 1

案例1： before是一个变量。

让我们看一下以下任务列表：

enum TASKS = { A, B, C, D, E };

我们声明一个数组before来保存每个任务的一组阻塞任务：

array [TASKS] of var set of TASKS: before;

任务永远不应该阻塞自己：

constraint forall(i in index_set(before))
    (
        not (i in before[i])
    );

任务i继承每个任务j阻塞任务的块集i：

constraint forall(taskset in before)
    (
        forall(task in taskset)
        (
            before[task] subset taskset
        )
    );

您可以附加：

 solve satisfy;

并找到所有可能的解决方案：

~$ minizinc test.mzn --all-solutions
before = array1d(TASKS, [{}, {A}, {A, B}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{B}, {}, {A, B}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{}, {}, {A, B}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{}, {A, C}, {A}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{}, {A}, {A}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{}, {}, {A}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{B, C}, {}, {B}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{B}, {}, {B}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{}, {}, {B}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{C}, {A, C}, {}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{}, {A, C}, {}, {A, B, C}, {A, B, C, D}]);
----------
before = array1d(TASKS, [{}, {A}, {}, {A, B, C}, {A, B, C, D}]);
...

---

CASE 2： before是一个输入参数。

一个任务i属于abans[j]如果它包含在 中before[j]，或者存在一个任务k在abans[j]这样i的 中before[j]。

编码：

enum TASKS = { A, B, C, D, E };

array [TASKS] of set of TASKS: before = 
    [{C}, {A}, {D}, {}, {B}];

array [TASKS] of var set of TASKS: abans;

constraint forall(i, j in TASKS)
    (
        i in abans[j] <->
        (
            i in before[j]
            \/
            exists(k in abans[j])
            (
                i in before[k]
            )
        )
        % circular dependencies are not allowed!
        /\ not(j in abans[j])
    );

solve satisfy;

输出：

~$ minizinc test.mzn --all-solutions
abans = array1d(TASKS, [{C, D}, {A, C, D}, {D}, {}, {A, B, C, D}]);
----------
==========