我正在尝试为以下问题提出一种算法:

我有一组整数的三元组 - 让我们称这些整数为 A、B、C。其中存储的值可能很大，因此通常不可能创建大小为 A、B 或 C 的数组。目标是最小化集合的大小。为此，我们提供了一个简单的规则，允许我们合并三元组:

public class Record {
    long A;
    long B;
    long C;

    public static void main(String[] args) {
        List<Record> data = new ArrayList<>();
        // Fill it with some data

        boolean found;

        do {
            found = false;
            outer:
            for (int i = 0; i < data.size(); ++i) {
                for (int j = i+1; j < data.size(); ++j) {
                    try {
                        Record r = merge(data.get(i), data.get(j));
                        found = true;
                        data.remove(j);
                        data.remove(i);
                        data.add(r);
                        break outer;
                    } catch (IllegalArgumentException ignored) {
                    }
                }
            }
        } while (found);
    }

    public static Record merge(Record r1, Record r2) {
        if (r1.A == r2.A && r1.B == r2.B) {
            Record r = new Record();
            r.A = r1.A;
            r.B = r1.B;
            r.C = r1.C | r2.C;
            return r;
        }
        if (r1.A == r2.A && r1.C == r2.C) {
            Record r = new Record();
            r.A = r1.A;
            r.B = r1.B | r2.B;
            r.C = r1.C;
            return r;
        }
        if (r1.B == r2.B && r1.C == r2.C) {
            Record r = new Record();
            r.A = r1.A | r2.A;
            r.B = r1.B;
            r.C = r1.C;
            return r;
        }
        throw new IllegalArgumentException("Unable to merge these two records!");
    }

最佳答案

这将是一个很长的答案，遗憾的是没有最佳解决方案(抱歉)。然而，这是将贪婪问题解决应用于您的问题的认真尝试，因此原则上它可能有用。我没有实现讨论的最后一种方法，也许这种方法可以产生最佳解决方案——不过我不能保证。

0级:不是很贪心

根据定义，贪心算法具有一种启发式方法，可以以局部最优的方式选择下一步，即当前最优，希望达到全局最优，这可能总是可能也可能不总是可能的。

您的算法选择任何可合并对并将它们合并，然后继续前进。它不评估此合并意味着什么以及是否有更好的本地解决方案。因此，我根本不会称您的方法为贪婪。这只是一个解决方案，一种方法。我将其称为盲算法，以便我可以在我的回答中简洁地引用它。我还将使用您算法的稍微修改版本，该版本不是删除两个三元组并附加合并的三元组，而是仅删除第二个三元组并将第一个替换为合并的三元组。结果三元组的顺序不同，因此最终结果也可能不同。让我在代表性数据集上运行这个修改后的算法，用 * 标记要合并的三元组。 :

0: 3 2 3   3 2 3   3 2 3
1: 0 1 0*  0 1 2   0 1 2
2: 1 2 0   1 2 0*  1 2 1
3: 0 1 2*
4: 1 2 1   1 2 1*
5: 0 2 0   0 2 0   0 2 0

Result: 4

If I merge these two triplets, will the resulting set have the maximum possible number of mergable triplets, when compared to the result of merging any other two triplets from the current set?

          mergables
0: 3 2 3  (1,3)->2
1: 0 1 0  (1,5)->1
2: 1 2 0  (2,4)->2
3: 0 1 2  (2,5)->2
4: 1 2 1
5: 0 2 0

          mergables
0: 3 2 3  (2,3)->0
1: 0 1 2  (2,4)->1
2: 1 2 0
3: 1 2 1
4: 0 2 0

          mergables
0: 3 2 3  (2,3)->0   3 2 3
1: 0 1 2             0 1 2
2: 1 2 0             1 2 1
3: 1 2 1

Result: 3

          mergables
0: 3 2 3  (1,3)->(2,3)->0
1: 0 1 0         (2,4)->1*
2: 1 2 0  (1,5)->(2,4)->0
3: 0 1 2  (2,4)->(1,3)->0
4: 1 2 1         (1,4)->0
5: 0 2 0  (2,5)->(1,3)->1*
                 (2,4)->1*

Instead of checking how many merges are possible after each possible merge for the starting set; this time we check how many merges are possible after each possible merge for each resulting set after each possible merge for the starting set. And this is for lookahead 1. For lookahead n, you'd be seeing a very long sentence repeating the part after each possible merge for each resulting set n times.

_{(*): Assuming a large reduction of input sets is possible, the number of merges is proportional to input size, and lookahead approximately indicates how much you permute those merges. So you have choose lookahead from |input|, which is the binomial coefficient that for lookahead ≪ |input| can be approximated as O(|input|^lookahead) -- which is also (rightfully) written as you are thoroughly screwed.}

关于java - 三元组的最佳合并，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22222994/