我有 N 个实体，我想为这些实体找到大小为 3 的所有组合。组合的数量如此之多，以至于无法实际计算所有这些组合。因此，我将使用启发式方法：每个实体的分数等于 ，(number of times this entity was used in a combination with the combination score >= threshold) / (number of times this entity was used in a combination)并且我想找到一个组合，其具有combination score >= threshold. （如果您能找到得分最高的组合或能证明得分在某个最高百分位，则加分。）
请注意，如果不提供此问题背后的大量上下文，很难描述如何计算组合分数，但可以说很难预测且计算速度不快。
由于这是一个持续的过程，我想要一个数据结构，我可以在其中存储我尝试的每个组合，以便下次我可以跳过它们。这个数据结构也应该有助于找到我还没有尝试过的潜在高分组合。
一个直接的方法是：
sorted_entities = sorted(entities, key=lambda entity: entity.score, reverse=True)
for e1 in sorted_entities:
for e2 in sorted_entities:
for e3 in sorted_entities:
if not data_structure.already_have(e1, e2, e3):
data_structure.add(e1, e2, e3)
return (e1, e2, e3)
几个明显的问题：
我能想到的另一种方法是概率性的：选择一个随机实体，更有可能选择一个得分较高的实体。然后根据这两个实体的总分按比例选择下一个实体。然后可以在 O(N) 中强制执行最优的第三个选择。（我认为这听起来很像贝叶斯优化，所以这可能是这种方法的最佳版本。）
这是我目前确定的答案：
步骤1）找到e1使用它的组合最少的。
步骤 2) 找到combos1包含的组合列表e1。
步骤3）找到使用它的e2组合最少的combos1。
步骤 4) 找到combos2包含e1和的组合列表e2(注意：它将是 的严格子集combos1。)
步骤 5) 遍历combos2并创建一组使用的所有实体：existing_e3_set
步骤 6) set_of_all_entities-existing_e3_set为您提供所有e3s您可以结合e1和e2创建尚不存在的组合。
运行时间在实体和组合的数量上是线性的。
我认为您可以修改第 1 步和第 3 步以使用某种实体分数，但我还没有想过这可能会失去在第 6 步中最终得到非空集合的保证。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句