防止超销售，分配有限的资源与重叠属性

Question

我正在尝试解决防止有限资源的问题。

考虑由每个属性属于不同类别的属性的资源（人）（人）（来自四个类别的示例属性：男性，25-30岁，2个孩子，对游戏感兴趣）。

买家想分配访问资源。买家可以从每个类别中指定类别的子集和一个属性（示例：分配1000名男性，年龄25-30岁或分配100名女性，年龄在25-30岁，对音乐感兴趣）。

在我的现实生活示例中，我有6m+可能的属性集（配置文件），在其中，对于每组属性，我知道存在多少个配置文件。

我最初的方法是在下面构建图形：

然后使用边缘重量进行遍历，例如验证如果对100名女性的需求，可以满足Age2的需求：

1. 检查大小（女性，年龄2）<100
2. 对于每个父母：
   1. 检查大小（父）<100，然后转到2。
3. 每个孩子：
   1. 检查大小（儿童）<100 *重量（edge（node，child））转到1。

（上面的算法被简化，不会阻止多次访问相同的节点）

当图形很小时，一切都很好，但是当节点（配置文件群体组）之间的节点和边缘数（依赖关系）的数量增长时，它的扩展不是很好。

考虑示例：

• 大图，6m节点，20m+边缘
• 买方想分配1000名男性（性别类别中只有男性和女性）

算法将从顶级的“男性”节点开始，该节点可能具有10m+外的边缘，并且需要10m+检查（并且大概每个10m外的边缘中的每个边缘都有传入的边缘，也需要检查）。

我试图找到不同的方法，但失败了。我试图搜索现有的解决方案，但似乎我甚至无法正确命名问题。任何与此问题类似的引用对我来说都是好处。

感谢您的评论/帮助。

另外两个图表以呈现图形的指数增长：3个类别

4个类别

更新

关于大小，假设每个类别具有8个类别的属性：2、6、6、6、6、8、1140、150值，然后估计的配置文件数：2*6^4*8*1140*150〜= 3.5 = 3.5 * 10^9。图中的节点数：至少7 * 10^9，图中的边数：至少140 * 10^9。

更新＃2

节点数的公式为：

$ sum_ {i

其中$ n $是类别数，$ s_x $是类别$ x $的大小。

因此，在我的示例中，将有11'169'108'657节点。

更新＃3

根据@Raphael建议 - 我减少了节点的数量，现在公式是：

$ sum_ {i

其中$ m

尺寸减少的示例：

Answer 1

因此，对于分类器的每种可能组合，数据结构都有指针是巨大的。当然，但是为什么要构建它呢？不要过度工程！

只需将配置文件存储在数据库中，然后为每个查询进行一个（线性时间）过滤扫描，即选择/计数按需。对于数百万张记录，不应需要进一步的预处理。

如果请求的数量很大和/或您需要 真的 响应时间很小，您可以考虑缓存或沿着一些流行的分类器或几乎没有大型类别的分类器创建等价类。然后，线性扫描必须仅在小列表上进行。

例如，您可以按性别和年龄划分数据库（假设这些数据库包含在大多数客户查询中）

$ qquad {m，w，o } times {0..5，10..15， dots，95..100 } $

值的值显然取决于您的数据。然后，每个查询只需要这些小列表中的几个，甚至可以单独存储单个块，甚至可以并行。