3

首先：不，这不是作业！这适合我正在为游戏编写的求解器。我只是将问题简化为这个简洁的陈述：

给定一组集合 S，找出并删除 S 的任何元素，这些元素是 S 的其他元素的子集。

领域

1 <= |S| <= C^K

1 <= |S i | <= ķ

2 <= C <= 10

10 <= K <= 500

细节

S i是 [0, K) 的子集

min(|S i |) >= log C (|S|)

我目前的方法是通过我所说的“NatSet”将每个集合保持在 S 中，这只是一个bool[K]. 然后我按 |S i |对 S 进行排序 并进行 O(|S|^2) 搜索以查找作为其他元素子集的元素。不幸的是，这对于我的目标值 C=6 和 K=16*9 来说太慢了。

4

2 回答 2

2

考虑到我无法尝试（set 的输入S对我来说是不可见的）并决定以下是否有帮助，我只能为您提供一些提示：

  1. 比较两个集合时：“减少” binary search：当您比较集合 A (x1...xn) 是否是集合 B(y1...ym) 的子集时，假设您找到yk = x1(n <= m)

        y1, y2, ...,yk, yk+1 ... ym
                |
               x1

    然后您可以x2在[yk+1, ym]. 其他的都是一样的。

  2. 选择两组比较时： 选择大的（即，s1and sk，thens1和sk-1），你说按大小排序，大的更可能包含它。
  3. 排序Si？我不确定 sort 是否S可以提高您的性能，您可以尝试不进行排序或使用 a max-heap（见技巧 4）
  4. 使用最大堆： 将叶子与根和根的儿子之一进行比较......如图所示）。

在此处输入图像描述

如果叶子没有被删除（即不是它父亲的子集），只需将它从堆中删除，您就可以将它交换到叶子被删除的地方。（如下图）

在此处输入图像描述

注意：使用堆不能保证所有子集都被删除。

  1. 如何排序？：在您的情况下，计数排序似乎是一种合适的排序方式，即线性排序。

更多的：

1.你说你正在修剪树，你要Alpha-beta修剪吗？

2.高效的列表交集算法

希望这会有所帮助。

于 2015-01-25T02:04:30.493 回答
0

这里的内在问题是，给定两个集合，一个包含 p 个元素，另一个包含 q 个元素（不失一般性，我们可以说 p < q），获得两者并集的最快方法是 O(p) . 这是因为如果您使用 HashSets，您可以将查找减少到 O(1)。

据我了解，您正在进行 O(K^2) 搜索，因此您总共得到 O((n^2)*(K^2))，其中 n 是 S 的元素数。您可以使用 HashSet 方法将其减少到 O((n^2)K)。这是 Java http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html的链接，几乎所有主要语言在其标准库中都有一些实现。尽管如果您的集合 S 在 n= 6^(16*9) 附近的任何地方，那么我认为这不会有太大帮助（我什至不确定您是否可以在这种大小的现代计算机中容纳任何相关数据）。

如果您可以将 k 降低到 <= 64（或 32 位系统中的 32），您可以使用位图将每个集合存储在 S 中，并使用并行位操作将您的时间减少到 O(n^2)。它等同于您当前的方法，但您只需按位或检查它是否等于相同的数字： ((a1 | a2) == a1) || ((a1 | a2) == a2)。这样你就可以在恒定时间内进行联合操作。

于 2015-01-24T05:07:30.783 回答