Minizinc: как я могу объединить набор в этой ситуации (алгоритм фиксированной точки?)
У меня есть массив наборов, что означает, что элементы внутри набора должны закончиться до того, как начнется фактический. Например:
before = [ {},
{1},
{},
{},
{2}];
Я хочу, чтобы каждая строка включала те, которые идут до рекурсивно. В этом случае все должно получиться так:
abans = [ {},
{1},
{},
{},
{1,2}];
Я пробовал сгенерировать переменную и создать наборы с нуля, но мне это не удалось. Есть идеи, как я мог это сделать?
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}]);
...
СЛУЧАЙ 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}]);
----------
==========