Минизин c: как я могу сделать объединение множества в этой ситуации (алгоритм фиксированной точки?) - PullRequest
Новая
       40

Минизин c: как я могу сделать объединение множества в этой ситуации (алгоритм фиксированной точки?)

1 голос
/ 24 января 2020

У меня есть массив наборов, который означает, что элементы внутри набора должны завершиться sh до того, как начнется фактический. Например: 

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

Я хочу, чтобы каждая строка включала те, которые go были рекурсивно. Так что в этом случае все должно закончиться так: 

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

Я пытался сгенерировать переменную и создать наборы из пустых, но мне не удалось это сделать. Есть идеи, как я мог это сделать?

1 Ответ

1 голос
/ 25 января 2020

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

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