如何$ C C时的最大集装箱算法$？ [英] How to code the maximum set packing algorithm?

问题描述

假设我们有一个有限集合S和S的子集的列表之后，集装箱问题询问某个k子集列表中的是两两不相交。 的问题，最大设定填料，所述的优化版本请求的成对不相交的集合中的列表中的最大数量。

Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint . The optimization version of the problem, maximum set packing, asks for the maximum number of pairwise disjoint sets in the list.

http://en.wikipedia.org/wiki/Set_packing

所以，让 S = {1,2,3,4,5,6,7,8,9,10}

and `Sa = {1,2,3,4}`
and `Sb = {4,5,6}`
and `Sc = {5,6,7,8}`
and `Sd = {9,10}`

随后的两两不相交集的最大数是3（SA，SC，SD）

Then the maximum number of pairwise disjoint sets are 3 ( Sa, Sc, Sd )

我无法找到所涉及的算法的任何物品。你能提供一些线索上一样吗？

I could not find any articles about the algorithm involved. Can you shed some light on the same?

我的方法：

根据大小排序集。开始从设定的最小尺寸。如果下一组没有元素相交的当前集，然后我们凝聚集和增加的最大集的计数。这听起来好给你？更好的想法？

Sort the sets according to the size. Start from the set of the smallest size. If no element of the next set intersects with the current set, then we unite the set and increase the count of maximum sets. Does this sound good to you? Any better ideas?

推荐答案

由于HIVERT指出，这个问题是一个NP难，所以没有有效的方法来做到这一点。但是，如果你输入的是比较小的，你仍然可以把它关闭。指数不等于不可能，毕竟。这只是指数的问题变得不切实际很快，随着输入规模的增长。但是，对于像25套，你可以很容易地蛮力它。

As hivert pointed out, this problem is NP-hard, so there's no efficient way to do this. However, if your input is relatively small, you can still pull it off. Exponential doesn't mean impossible, after all. It's just that exponential problems become impractical very quickly, as the input size grows. But for something like 25 sets, you can easily brute force it.

下面是一种方法。比方说，你已经的 N 的子集，名为 S0 的 S1 的，...等，我们可以尝试子集的每个组合，并挑选之一，最大基数。只有2 ^ 25 = 33554432的选择，所以这可能是不够合理。

Here's one approach. Let's say you have n subsets, called S0, S1, ..., etc. We can try every combination of subsets, and pick the one with maximum cardinality. There are only 2^25 = 33554432 choices, so this is probably reasonable enough.

这是简单的方法来做到这一点是要注意，任何非负数严格低于2 ^ N重presents子集的特定选择。看的数目的二进制重新presentation，并选择集其索引对应于上的位。因此，如果数为11，第0，第一和第三位是上，与此相对应的组合[S0，S1，S3]。然后你只需验证这些三套实际上不相交。

An easy way to do this is to notice that any non-negative number strictly below 2^N represents a particular choice of subsets. Look at the binary representation of the number, and choose the sets whose indices correspond to the bits that are on. So if the number is 11, the 0th, 1st and 3rd bits are on, and this corresponds to the combination [S0, S1, S3]. Then you just verify that these three sets are in fact disjoint.

您的程序如下：

1. 我迭代从0到2 ^ N - 1
2. 对于每个i的值，使用都对位计算出子集的相应组合。
3. 如果这些子集两两不相交，更新与此相结合的最好的答案（即使用这个，如果它是大于你目前最好的）。

另外，使用回溯来生成子集。这两种方法是等效的，模数实现折衷。回溯也会有一些栈的开销，但可以切断计算整行，如果你检查不相交，当您去。例如，如果S1和S2是不相交，则它将永远不会打扰与含有这两个的任何更大的组合，保存一定的时间。迭代方法不能优化本身以这种方式，但是是快的，因为位操作和紧环的和有效的。

Alternatively, use backtracking to generate your subsets. The two approaches are equivalent, modulo implementation tradeoffs. Backtracking will have some stack overhead, but can cut off entire lines of computation if you check disjointness as you go. For example, if S1 and S2 are not disjoint, then it will never bother with any bigger combinations containing those two, saving some time. The iterative method can't optimize itself in this way, but is fast and efficient because of the bitwise operations and tight loop.

这里唯一的非平凡的事情就是如何检查，如果子集两两不相交。有各种各样的技巧，你可以在这里拉动为好，这取决于约束。

The only nontrivial matter here is how to check if the subsets are pairwise disjoint. There are all sorts of tricks you can pull here as well, depending on the constraints.

有一个简单的方法是先建立一个空集结构（选择任何你想从你所选择的语言），并从每个子集逐个添加元素。如果你打一个元素中已有的集合，那么它发生在至少两个子集，你可以放弃这个组合。

A simple approach is to start with an empty set structure (pick whatever you want from the language of your choice) and add elements from each subset one by one. If you ever hit an element that's already in the set, then it occurs in at least two subsets, and you can give up on this combination.

如果原来设置的取值的有 M 的元素，而 M 的是比较小的，可以将每个人映射到范围[0 ，M-1]，并利用位屏蔽的每一组。因此，如果 M＆LT; = 64 的，你可以使用Java长重新present每个子集。打开所有对应于在该子集中的元素的位。这使得因为按位运算的速度超快的设置操作。按位，对应于交集，和位，或者是工会。您可以检查是否两个子集是不相交通过观察，如果交集为空（即AND运算这两个位掩码为您提供0）。

If the original set S has m elements, and m is relatively small, you can map each of them to the range [0, m-1] and use bitmasks for each set. So if m <= 64, you can use a Java long to represent each subset. Turn on all the bits that correspond to the elements in the subset. This allows blazing fast set operation, because of the speed of bitwise operations. Bitwise AND corresponds to set intersection, and bitwise OR is a union. You can check if two subsets are disjoint by seeing if the intersection is empty (i.e., ANDing the two bitmasks gives you 0).

如果你没有这么少的元素，你仍然可以避免重复设置的交点多次。你有非常几集，所以precompute哪些是不相交的开始。你可以只存储一个布尔值矩阵D，使得D [I] [J] =真当且仅当i和j是不相交的。然后，你只要看看所有成对组合，以验证两两不相交，而不是做实际的操作集合。

If you don't have so few elements, you can still avoid repeating the set intersections multiple times. You have very few sets, so precompute which ones are disjoint at the start. You can just store a boolean matrix D, such that D[i][j] = true iff i and j are disjoint. Then you just look up all pairs in a combination to verify pairwise disjointness, rather than doing real set operations.

这篇关于如何$ C C时的最大集装箱算法$？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！