1

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

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

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

举一个简单的例子，给定：

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 万次循环更快的检查向量/数组的方法？约束库是唯一的选择吗？

为了澄清：

容器是 std::vector。

向量包含任何整数。

我需要逐个问题地检查它们以识别完整的整数集。

使用指定的条件逻辑来选择整个向量，是否会出现重复？使用的条件运算符总是只有“AND”和“OR”。我列出的问题是一个简化版本，但这实际上就是它的全部内容。它只是大小不同。

我不太关心的输出......它可能是一个布尔值，另一个潜在重复的向量等。我试图找到适合这项工作的工具，而不是打捞。

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

4

1 回答 1

1

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

我已经在 MiniZinc（一个非常高级的约束编程系统，请参阅我的 MiniZinc 页面了解更多信息和进一步链接：http ://www.hakank.org/minizinc/）中实现了所述（简单）问题。

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

包括“globals.mzn”；

整数：n = 5；% 套数

数组 [1..n] 的 int 集合：s =
  [
   {1,2}, % E
   {2,4}, % F
   {1,3}, % M
   {4,5}, % N
   {5,6} % A
  ];

% 所有值（“宇宙”）
一组 int：值 = {j | i 在 1..n 中，j 在 s[i]} 中；

% 决策变量
var bool 的数组[1..n]：x; % 选择哪个设置（以秒为单位）
array[1..n] of var 值集：xs; % 选定的集合

解决满足；
% 最小化选择集的数量
％解决最小化总和（i in 1..n）（bool2int（card（xs [i]）> 0））；

约束

  ％ 条件
  % (E || F) && (M || N) && A
  ((x[1] \/ x[2]) /\ (x[3] \/ x[4]) /\ x[5])
  /\
  forall(i in 1..n) (
     % 如果选择了这个集合（在 x[i] 中），将 s[i] 放入 xs[i]
     (x[i] xs[i] = s[i])
     /\ % 确保未选择的集合在 xs 中表示为 {}
     (不是(x[i]) 卡(xs[i]) = 0)
  )
  /\ % 确保在一组中选择了一个值
  partition_set([xs[i] | i in 1..n], values)
;

输出
[
  "x:" ++ 显示(x) ++ "\n" ++
  "xs:" ++ 显示(xs) ++ "\n"
];

这个问题有一个单一的解决方案：

x：[假，真，真，假，真]
xs: [{}, {2, 4}, {1, 3}, {}, 5..6]

其中“x”是一个布尔数组，是否应该选择一个集合，“xs”包含选定的集合（如果没有选择一个集合，则元素为{}，即为空）。集合的划分是通过partition_set确保一个值在一个集合中并且宇宙中的所有值（集合“值”）都在某个集合中的函数完成的。

我不确定这个 MiniZinc 模型是否有帮助，但如果没有别的，您可能会将其视为一种灵感。此外，在此模型中对条件的处理是硬编码的，因此此处不予说明。

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

于 2013-05-09T07:22:11.957 回答