三元组的最佳合并
2022-09-03 16:10:44
我正在尝试为以下问题提出一种算法：
我有一个整数的三元组的集合 - 让我们称这些整数为A，B，C。存储在其中的值可能很大，因此通常不可能创建大小为 A、B 或 C 的数组。目标是最小化集合的大小。为此，我们提供了一个简单的规则，允许我们合并三元组：
- 对于两个三元组（A，B，C）和（A'，B'，C'），删除原始三元组并将三元组（A|A'， B， C） 如果 B == B' 且 C = C'，其中 |是按位 OR。类似的规则也适用于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!");
}
你知道如何解决这个问题吗？
