组合拍卖中冲突图的优化实现是什么

Question

给定m个投标可能共享n个项目的子集，我想找到存储投标之间冲突的最佳方法，并检查两个投标是否冲突（即，它们至少共享一个项目）。到目前为止，我已经尝试了一个维度为m x m的矩阵，它不是最优的。我的问题可能有数千次出价，因此当我使用方阵实现时，我经常会收到错误"Java内存不足"。然后，我尝试使用三角形矩阵（因为原始冲突矩阵是对称的），但没有解决内存问题！

有更好的主意吗？

最好的编码方式是什么？

谢谢。

Answer 1

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

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

当你存储一个新的出价时，你会这样做（这假设bid有一个返回Set<Item>的.items()方法）：

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);