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}]);
----------
==========
Другие вопросы по тегам