Dan*_*ahr 15 java algorithm optimization
我正在尝试针对以下问题提出算法:
我有一个整数三元组的集合 - 让我们称这些整数为A,B,C.存储在里面的值可能很大,所以通常不可能创建一个大小为A,B或C的数组.目标是最小化集合的大小.为此,我们提供了一个简单的规则,允许我们合并三元组:
换句话说,如果两个三元组的两个值相等,则删除这两个三元组,按位或删除第三个值,并将结果放入集合中.
贪婪的方法在类似的情况下通常会产生误导,所以这是针对这个问题,但我找不到一个简单的反例,它会导致正确的解决方案.对于包含正确解为14的250项的列表,通过贪婪合并计算的平均大小约为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!");
}
你知道如何解决这个问题吗？
这将是一个很长的答案，遗憾的是没有最佳解决方案（抱歉）。然而，这是将贪婪问题解决应用于您的问题的认真尝试，因此原则上它可能有用。我没有实现最后讨论的方法，也许该方法可以产生最佳解决方案——但我不能保证这一点。
\n\n根据定义，贪心算法具有启发式方法，用于以局部最优（即当前最优）的方式选择下一步，希望达到全局最优，这可能始终是可能的，也可能不可能。
\n\n您的算法选择任何可合并对并将它们合并，然后继续。它没有评估这次合并意味着什么以及是否有更好的本地解决方案。因此，我根本不会称您的方法为贪婪。这只是一个解决方案、一种方法。我将其称为盲算法，以便我可以在答案中简洁地引用它。我还将使用您的算法的稍微修改版本，该算法不是删除两个三元组并附加合并的三元组，而是仅删除第二个三元组并用合并的三元组替换第一个三元组。生成的三元组的顺序不同，因此最终结果也可能不同。让我在代表性数据集上运行这个修改后的算法，用 标记要合并的三元组*：
0: 3 2 3 3 2 3 3 2 3\n1: 0 1 0* 0 1 2 0 1 2\n2: 1 2 0 1 2 0* 1 2 1\n3: 0 1 2*\n4: 1 2 1 1 2 1*\n5: 0 2 0 0 2 0 0 2 0\n\nResult: 4\n要使用贪婪算法，您需要以允许在多个可用选项时进行比较的方式制定合并决策。对我来说，合并决策的直观表述是：
\n\n\n\n\n如果我合并这两个三元组，与合并当前集中的任何其他两个三元组的结果相比，结果集是否具有最大可能数量的可合并三元组？
\n
我再说一遍，这对我来说很直观。我没有证据证明这会带来全局最优解，甚至无法证明它会带来比盲算法更好或相等的解决方案——但它符合贪婪的定义（并且很容易实现）。让我们在上面的数据集上尝试一下，显示每个步骤之间可能的合并（通过指示三元组对的索引）以及每个可能合并的可合并数：
\n\n mergables\n0: 3 2 3 (1,3)->2\n1: 0 1 0 (1,5)->1\n2: 1 2 0 (2,4)->2\n3: 0 1 2 (2,5)->2\n4: 1 2 1\n5: 0 2 0\n除了合并三元组 1 和 5 之外的任何选择都可以，如果我们采用第一对，我们会得到与盲算法相同的临时集（这次我将折叠索引以消除间隙）：
\n\n mergables\n0: 3 2 3 (2,3)->0\n1: 0 1 2 (2,4)->1\n2: 1 2 0\n3: 1 2 1\n4: 0 2 0\n这就是该算法的不同之处：它选择三元组 2 和 4，因为与盲算法所做的选择相比，在合并它们之后仍然有可能进行一次合并：
\n\n mergables\n0: 3 2 3 (2,3)->0 3 2 3\n1: 0 1 2 0 1 2\n2: 1 2 0 1 2 1\n3: 1 2 1\n\nResult: 3\n现在，这种直观启发式的第二步是进一步展望合并，然后提出启发式问题。一般来说，您将进一步展望k合并并应用上述启发式、回溯并决定最佳选项。现在这变得非常冗长，因此为了举例说明，我将仅使用前瞻 1 执行这一新启发式的一个步骤：
mergables\n0: 3 2 3 (1,3)->(2,3)->0\n1: 0 1 0 (2,4)->1*\n2: 1 2 0 (1,5)->(2,4)->0\n3: 0 1 2 (2,4)->(1,3)->0\n4: 1 2 1 (1,4)->0\n5: 0 2 0 (2,5)->(1,3)->1*\n (2,4)->1*\n应用此新启发式时，标有星号的合并序列是最佳选择。
\n\n如果需要口头解释：
\n\n\n\n\n而不是在起始集合的每个可能的合并之后检查有多少个可能的合并；这次，我们检查在起始集的每个可能的合并之后，每个结果集的每个可能的合并之后可能有多少次合并。这是为了前瞻
\n1。对于 Lookaheadn，您会看到一个很长的句子，在每个结果集的每次可能合并之后n重复该部分。
如果仔细观察，即使对于中等输入和前瞻（*），以前的方法也会产生灾难性的性能。对于超过 20 个三元组的输入，任何超过 4 次合并前瞻的操作都需要非常长的时间。这里的想法是删除似乎比现有解决方案更糟糕的合并路径。如果我们想要执行前瞻 10，并且特定合并路径在 3 次合并后产生的可合并项少于另一条路径在 5 次合并后产生的可合并项，那么我们也可以将当前的合并路径并尝试另一个合并路径。这应该可以节省大量时间并允许大的前瞻，这将使我们更接近全局最优解，希望如此。不过我还没有实现这个来进行测试。
\n\n\n\n\n(*): 假设可以大量减少输入集，则合并数量\n 与输入大小成正比，并且\n 前瞻大约表示您对这些合并进行排列的程度。\n 因此，您可以从 中进行选择，
\nlookahead即|input|\ n 的二项式系数lookahead \xe2\x89\xaa |input|可以近似为\n——O(|input|^lookahead)这也是（正确地）写成的，因为你彻底搞砸了。
我对这个问题非常感兴趣，所以我坐下来用 Python 编写了它。遗憾的是，我能够证明不同的前瞻可能会产生不同的结果，而且即使是盲算法有时也会比前瞻 1 或 2 更好。这是解决方案不是最优的直接证明（至少对于 ）lookahead \xe2\x89\xaa |input|。请参阅 github 上的源代码和帮助程序脚本以及证明三元组。请注意，除了合并结果的记忆之外，我没有尝试按 CPU 周期优化代码。
| 归档时间： |
|
| 查看次数： |
701 次 |
| 最近记录： |