быстрое и простое программирование ограничений с использованием векторов (массивов)

Question

У меня есть много, много и много векторов, которые мне нужны для проверки дубликатов чисел с помощью очень простой логики первого порядка.

Я могу использовать перекрестки, но это оказывается слишком медленным. Я думал, что могу превратить это в поразрядную проблему. Полный набор целых чисел известен, и каждый вектор/массив может быть представлен как битовый набор, но я могу найти только половину решения.

В настоящее время я использую цикл и векторное пересечение, но оно оказывается слишком медленным для количества проблем, которые мне нужно проверить.

Для простого примера, учитывая:

E: 1 2 
F: 2 4 
M: 1 3 
N: 4 5 
A: 5 6 

Проблема Я пытаюсь определить, всегда больший формат:

(E || F) && (M || N) && A -> which is proven as possible by selecting F,M,A. 

мне нужно проверить, если выше можно без дубликаты.

Есть ли средство для изучения векторов/массивов, таких как более 9 миллионов циклов? Являются ли библиотеки ограничений единственной возможностью?

В попытке уточнить:

контейнеры станд :: вектор.

Векторы содержат любое целое число.

Мне нужно было бы изучить их проблему по проблеме, чтобы идентифицировать полный набор целых чисел.

Использование условной логики, заданной для выбора целых векторов, произойдет дубликат? Используемые условные операторы всегда будут только «И» и «ИЛИ». Проблема, которую я перечислил, - это упрощенная версия, но на самом деле это все. Он просто отличается по размеру.

Результат, о котором я забочусь меньше ... это может быть булев, другой вектор потенциальных дубликатов и т. Д. Я пытаюсь найти правильный инструмент для работы, а не для спасения.

В моем текущем настроении я решил бы это, проанализировав для принудительных элементов, таких как A, и удалив все, с чем он пересекается ... (в этом случае N ... тогда я бы снова начал цикл и выполнял тот же процесс с M, который теперь является принудительным выбором и удалением E, оставив меня с F.

Answer 1

Если я правильно понял проблему, это проблема с заданием раздела, где значения из определенной «вселенной» (т.е. все значения в наборы) должны быть выбраны так, чтобы одно значение находилось только в одном из выбранных наборов. И для этого есть определенное условие возможной комбинации наборов.

Я реализовал указанную (простую) проблему в MiniZinc (очень система программирования Constraint высокого уровня, см. мою страницу MiniZinc для получения дополнительной информации и дальнейших ссылок: http://www.hakank.org/minizinc/).

Модель здесь: http://www.hakank.org/minizinc/set_partition_stackoverflow.mzn и копируется ниже полностью:

 
include "globals.mzn"; 

int: n = 5; % number of sets 

array[1..n] of set of int: s = 
    [ 
    {1,2}, % E 
    {2,4}, % F 
    {1,3}, % M 
    {4,5}, % N 
    {5,6} % A 
    ]; 

% All values (the "universe") 
set of int: values = {j | i in 1..n, j in s[i]}; 

% decision variables 
array[1..n] of var bool: x; % which set (in s) to select 
array[1..n] of var set of values: xs; % the selected sets 

solve satisfy; 
% Minimize the number of selected sets 
% solve minimize sum(i in 1..n) (bool2int(card(xs[i]) > 0)); 

constraint 

    % The condition 
    % (E || F) && (M || N) && A 
    ((x[1] \/ x[2]) /\ (x[3] \/ x[4]) /\ x[5]) 
    /\ 
    forall(i in 1..n) (
    % If this set is selected (in x[i]), put s[i] in xs[i] 
    (x[i] xs[i] = s[i]) 
    /\ % ensure not selected sets are represented as {} in xs 
    (not(x[i]) card(xs[i]) = 0) 
) 
    /\ % make sure that a value is selected in exactly one set 
    partition_set([xs[i] | i in 1..n], values) 
; 

output 
[ 
    "x: " ++ show(x) ++ "\n" ++ 
    "xs: " ++ show(xs) ++ "\n" 
]; 

Существует единственное решение этой проблемы:

 
x: [false, true, true, false, true] 
xs: [{}, {2, 4}, {1, 3}, {}, 5..6] 

, где «х» является логическим массивом, если следует выбрать набор или нет, а «xs» содержит выбранные наборы (если набор не выбран, то элемент {}, т.е. пустой). Разделение наборов выполняется с помощью функции partition_set, которая гарантирует, что значение находится в одном наборе и что все значения в юниверсе (установленные «значения») находятся в некотором наборе.

Я не уверен, что эта модель MiniZinc помогает вообще, но вы можете видеть ее как своего рода вдохновение, если ничего другого. Кроме того, обработка этого условия жестко закодирована в этой модели, поэтому здесь не рассматривается.

Система CP на базе C++ Gecode (http://www.gecode.org/) имеет поддержку заданных переменных и ограничение раздела (называемое «disjoint» в Gecode), хотя я не тестировал его для этой проблемы. Вот пример того, как «disjoint» можно использовать в стандартной проблеме раздела: http://www.hakank.org/gecode/set_partition.cpp.