java - 组合拍卖冲突图的优化实现是什么？

Question

给定可能共享 n 个项目子集的 m 个投标，我想找到存储投标之间冲突的最佳方法，并检查两个投标是否存在冲突（即，它们至少共享一个项目）。到目前为止，我已经尝试了一个尺寸为 mxm 的矩阵，这不是最优的。我的问题可能有成千上万的出价，因此当我使用方阵实现时，我经常收到错误“Java 内存空间不足”。然后，我尝试使用三角矩阵（因为原始冲突矩阵是对称的）但没有摆脱内存问题！

有更好的主意吗？

最好的编码方式？

谢谢。

Answer 1

一种解决方案是使用番石榴Table并将其与List<Bid>包含所有出价的组合。注意：下面的代码使用了很多 Guava 的优点：

final List<Bid> allBids = Lists.newArrayList();
final Table<Bid, Bid, Void> conflicts = HashBasedTable.create();

当您存储新出价时，您将执行以下操作（假设bid有一个.items()返回 a 的方法Set<Item>）：

for (final Bid bid: allBids)
    if (!Sets.intersection(newBid.items(), bid.items()).isEmpty())
        conflicts.put(newBid, bid, null);
allBids.add(newBid);

然后，当您想检测两个出价之间的冲突时：

return table.contains(bid1, bid2) || table.contains(bid2, bid1);

---

您甚至可以通过将Void值替换为Set<Item>s 来存储冲突的项目，并将结果Sets.intersection()放入其中：

// Table becomes Table<Bid, Bid, Set<Item>>
Sets.SetView<Item> set;
for (final Bid bid: allBids) {
    set = Sets.intersection(newBid.items(), bid.items())
    if (!set.isEmpty())
        conflicts.put(newBid, bid, set.immutableCopy());
}
allBids.add(newBid);