java - 三元组的最佳合并

Question

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

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

对于两个三元组 (A, B, C) 和 (A', B', C')，如果 B == B' 和 C = C，则移除原始三元组并放置三元组 (A | A', B, C) ', 哪里 |是按位或。类似的规则也适用于 B 和 C。

换句话说，如果两个三元组的两个值相等，则删除这两个三元组，对第三个值进行按位或运算并将结果放入集合中。

在类似的情况下，贪婪的方法通常会产生误导，因此对于这个问题，但我找不到一个简单的反例可以找到正确的解决方案。对于包含 250 个项目且正确解为 14 的列表，通过贪婪合并计算的平均大小约为 30(从 20 到 70 不等)。随着列表大小的增加，次优开销变得更大。

我也尝试过设置位计数，但我没有发现任何有意义的结果。显而易见的事实是，如果记录是唯一的(可以安全地假设)，则设置位计数总是增加。

这是愚蠢的贪婪实现(这只是一个概念上的事情，请不要考虑代码风格):

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!");
    }

你知道如何解决这个问题吗？

Answer 1

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

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

1级:贪婪

要使用贪心算法，您需要以一种允许比较选项的方式来制定合并决策，当多个选项可用时。对我来说，合并决策的直观表述是:

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

除了合并三元组 1 和 5 之外的任何选择都可以，如果我们采用第一对，我们会得到与盲算法相同的临时集(这次我将折叠索引以消除间隙):

          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

这就是这个算法的不同之处:它选择了三元组 2 和 4，因为在合并它们之后仍有一个可能的合并 与盲算法的选择相反 :

          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

2级:非常贪婪

现在，这个直观启发式的第二步是进一步展望一次合并，然后提出启发式问题。概括地说，你会向前看k进一步合并并应用上述启发式，回溯并决定最佳选择。现在这变得非常冗长，所以为了举例说明，我将只执行这一新启发式的一个步骤与前瞻 1:

          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.

第 3 级:让我们切掉贪婪

如果您仔细观察，即使是中等输入和前瞻 (*)，先前的方法也具有灾难性的性能。对于超过 20 个三元组的输入，超过 4-merge-lookahead 的任何操作都需要不合理的时间。这里的想法是切断似乎比现有解决方案更糟糕的合并路径。如果我们想要执行前瞻 10，并且特定的合并路径在 3 次合并后产生的可合并量比 5 次合并后的另一条路径少，我们不妨切断当前的合并路径并尝试另一个。这应该可以节省大量时间，并允许进行大的前瞻，这将使我们更接近全局最优解，希望如此。不过，我还没有实现这个进行测试。

_{(*): 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.}

把这一切放在一起

我对这个问题很感兴趣，所以我坐下来用 Python 编写了它。可悲的是，我能够证明不同的前瞻可能会产生不同的结果，即使是盲算法偶尔也会比前瞻 1 或 2 更好。这是解决方案不是最佳的直接证明(至少对于 lookahead ≪ |input| ) . See the source code and helper scripts, as well as proof-triplets on github .请注意，除了内存合并结果之外，我没有尝试按 CPU 周期优化代码。