Minizinc:在这种情况下如何使集合的并集(定点算法?

Question

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

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

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

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

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

Answer 1

CASE 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}]);
...

---

案例 2：before是一个输入参数。

如果任务i包含在before[j]中，或者存在kabans[j]中的任务，则ibefore[j]，则该任务属于abans[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}]);
----------
==========