c++ - 涉及 vector (数组)的快速简单的约束规划

Question

我有很多很多 vector ，我需要用一些非常基本的一阶逻辑来检查数字的重复项。

我可以使用交叉路口，但事实证明那太慢了。我想我可以把它变成一个按位问题。完整的整数集是已知的，每个 vector/数组都可以表示为一个位集，但我只能找到一半的解决方案。

我目前使用循环和 vector 交集，但事实证明它对于我需要检查的问题数量来说太慢了。

举个简单的例子，给定:

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.

我需要验证以上是否可以不重复。

有没有比 900 万次循环更快的检查 vector/数组的方法？约束库是唯一的选择吗？

努力澄清:

容器是 std::vector。

vector 包含任何整数。

我需要一个问题一个问题地检查它们，以确定完整的整数集。

使用指定的条件逻辑选择整个 vector ，是否会出现重复？使用的条件运算符始终只是“AND”和“OR”。我列出的问题是一个简化版本，但实际上仅此而已。只是大小不同。

我不太关心的输出..它可能是一个 bool 值，另一个潜在重复项的 vector 等。我正在尝试为工作找到合适的工具而不是抢救。

在我目前的设置中，我会通过分析像 A 这样的强制项目并删除它与...相交的任何东西来解决这个问题(在这种情况下，N...然后我会再次循环，并执行相同的过程M，现在是一个被迫的选择，删除 E，留下 F。

Answer 1

如果我对问题的理解正确，这是一个集合划分问题，其中应该选择来自某个“宇宙”的值(即集合中的所有值)，以便一个值仅在所选集合之一中。并且这是一个特定的条件，集合的可能组合是可能的。

我已经在 MiniZinc(一个非常高级的约束编程系统，请参阅我的 MiniZinc 页面以获取更多信息和更多链接:http://www.hakank.org/minizinc/)中实现了上述(简单)问题。

模型在这里:http://www.hakank.org/minizinc/set_partition_stackoverflow.mzn并完整复制如下:

include "globals.mzn";int: n = 5; % number of setsarray[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 variablesarray[1..n] of var bool: x; % which set (in s) to selectarray[1..n] of var set of values: xs; % the selected setssolve 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]

如果一个集合是否应该被选择，“x”是一个 bool 数组，“xs”包含被选择的集合(如果一个集合没有被选择那么元素是{}，即空)。集合的划分是使用 partition_set 函数完成的，该函数确保一个值在一个集合中，并且宇宙中的所有值(集合“值”)都在某个集合中。

我不确定这个 MiniZinc 模型是否有任何帮助，但如果没有别的，您可能会将其视为一种灵感。此外，条件的处理在此模型中进行了硬编码，因此此处未解决。

基于 C++ 的 CP 系统 Gecode ( http://www.gecode.org/ ) 支持设置变量和分区约束(在 Gecode 中称为“不相交”)，但我尚未针对此问题对其进行测试。以下是如何在标准分区问题中使用“不相交”的示例:http://www.hakank.org/gecode/set_partition.cpp .