MiniZinc: закрепление пар ненулевых элементов в списке

У меня есть ситуация, когда я моделирую массив S, который содержит набор значений (расписание) из предопределенного домена 1..t, плюс 0, который является специальным значением для "не существует / не используется".

Теперь я хочу опубликовать ограничение для суммирования функции стоимости, представленной как 2D-массив C, для списка S', содержащего каждый ненулевой элемент S в том же порядке, например:

constraint x = sum([C[S'[d], S'[d + 1]] | d in 1..max - 1])

Однако сделать это нелегко. Вещи, которые я пробовал:

  • Using the function form of roots to get the set of indices to S whose data is non-zero. The problem with that solution is:
    • the result is a set, and so cannot be zipped into pairs or easily cast to a list, even though I know their number from provided instance data.
    • roots, похоже, требует, чтобы все значения участвовали в массиве, тогда как я хотел бы иметь только полный домен, кроме 0.
  • Использование понимания списка (например, [S[i] | i in 1..max where S[i] != 0]) для выбора только элементов, значения которых не равны нулю: это также не работает, поскольку предложение where в понимании списка приводит к тому, что список имеет тип opt, а также имеет неправильный номер элементов (где я предполагаю, что некоторые из них будут <>), по сути сводя проблему фильтрации нулей к той же проблеме снова с <>: s.
  • Обработка функции стоимости как DFA и значений 0 как петель: это не позволяет (во всяком случае, я могу определить) подсчет; только проверка переходов, которые меня не волнуют.

Мне бы очень хотелось здесь либо filter, либо zip, которые могли бы легко решить мою проблему, но я предполагаю, что есть какое-то стандартное решение, которое мне не хватает. В противном случае мне пришлось бы переделывать модель.


arrays minizinc
person albins    schedule 02.02.2018    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Вы можете решить вашу проблему, используя рекурсивную функцию, которая вычисляет затраты, перебирая индексы вашего массива S. Я проиллюстрирую функцию calculate_cost() на небольшом примере:

int: t = 10; int: N = 5;

% cost array
array[1..t,1..t] of int: C = array2d(1..t,1..t,[ i | i in 1..t, j in 1..t]);

% variables
array[1..N] of var 0..t: S;
var 0..1000: x;

% constraints
constraint S[1] = 4; % setting some arbitrary values
constraint S[2] = 7;
constraint S[3] = 0;
constraint S[4] = 6;

constraint x =  calculate_cost(1,2);

function var int: calculate_cost(int: index1, int:index2) =
  if index1 > N then 0 
  elseif index2 > N then 0
  else 
    let {
       var bool: value_at_index1_is_zero = S[index1] == 0;
       var bool: value_at_index2_is_zero = S[index2] == 0;
    }
    in 
      if value_at_index1_is_zero 
         then calculate_cost(index1+1, index1+2)
      elseif value_at_index2_is_zero 
         then calculate_cost(index1, index2 + 1) 
      else 
        C[S[index1],S[index2]] + calculate_cost(index2, index2+1)   
      endif
  endif;

solve satisfy;

В этом примере S = [4, 7, 0, 6, 0] и вычисляются затраты x = C[4,7] + C[7,6] = 4 + 7 = 11.

В функции calculate_cost() я рекурсивно вычисляю сумму, пропуская индексы, которые имеют нулевое значение в S. В первых нескольких строках я проверяю, выходят ли индексы за границы, и в этом случае возвращаю 0 (базовый случай рекурсии). Затем я создаю две локальные переменные, которые равны true, если значение в S[index] равно нулю для index. Затем, если один из этих случаев верен, я игнорирую эти индексы и снова рекурсивно вызываю функцию и увеличиваю / адаптирую соответствующий индекс в рекурсивном вызове.

Это работает, но, вероятно, это не очень хороший способ решения этой проблемы, потому что он вводит множество вспомогательных переменных в модель FlatZinc, поэтому все же может быть лучше переформулировать проблему.

person Andrea Rendl-Pitrey    schedule 02.02.2018
comment
Очень приятно, спасибо! Я протестирую его на модифицированной модели и посмотрю, насколько плохи эти дополнительные переменные в сравнении, потому что любой другой солитон, вероятно, также вводит ряд избыточных переменных решения. - person albins; 03.02.2018