algorithm - 如何在多个条件下选择项目

Question

我正在创建一个小软件，遇到了一个概念问题。我将尝试用一个小例子来解释这种情况：

我有一个包含多个点的坐标系。
每个点都由它在 x 和 y 轴上的位置描述（到目前为止正常），可以是蓝色或红色。
现在我想创建事件。
每个事件包含一个蓝色点和一个红色点，并且有几个关于如何选择它们的条件。
- 例如：蓝色（x）和红色（x）之和（=蓝色和红色点的x值）必须是偶数。
- 同时，可能存在 y 值的校验和不能是素数的条件。
每个点都可以是多个事件的一部分。
在我的情况下，每个点都有在创建事件时“使用”的特定资源，并且只要它具有所需数量的资源，该点就可以成为新事件的一部分。

我需要的是创建尽可能多的事件（即直到蓝色或红色组的资源耗尽）。假设我有 2 个红点和 2 个蓝点。Yes 和 No 表示它们是否满足给定条件：

B1 R1 是
B1 R2 是
B2 R1 是
B2 R2 没有

如果我匹配 B1 和 R1（每个列表的顶部），我只会得到一个事件，因为 B2 和 R2 不匹配。另一方面，如果我将 B1 与 R2 匹配，将 B2 与 R1 匹配，我会收到 2 个事件。这就是我需要的。

此外，我的事件的平均距离（从蓝点到红点）应该尽可能低。

我考虑过通过随机选择符合条件的蓝点和红点来创建事件，多次执行整个过程并保持事件数量最多和平均距离最短的结果。但我不太喜欢它，因为我无法提供任何关于结果质量的声明。结果也不是确定性的。

任何帮助都感激不尽。

score 0 · Accepted Answer

如有疑问，请从蛮力开始（至少这样您可以检查其他解决方案的有效性） - 在非常小的测试数据集上*（例如 4+3 点 => n=4*3 可能的对）：

从所有可能对的乘积中创建一个可能的事件数组（与标准匹配的蓝-红对的列表，还预先计算此步骤中的距离）
- 最坏情况大小n = red_count * blue_count
将此数组复制到一组集合中，每个集合只有一个事件：{{(r1,b1)}, {(r1,b2)}, ...}
对于每组：
- 更新积分上的资源（每组课程单独存储）
- 如果还有要匹配的资源，则通过再添加 1 对来拆分当前集（对可以添加的每一对进行此操作）并删除当前的不完整集，如下所示：
```
4 sets of 1 event     10 sets of 2 events
e1 e2 e3 e4              e1 e2 e3 e4
x  x  x  x            e1 x  x  x  x
                  ->  e2    x  x  x
                      e3       x  x
                      e4          x
```
- 重复直到没有任何集合可以被新的对改进（没有更多的资源或使用所有对）

=> 最坏情况O(n ^2k ) (n=r*b=所有可能的红色/蓝色对，k = 最大集合中的事件数)

然后受到全局优化技术的启发，不确定如何在没有更详细的规范的情况下组合您的需求，想...

第 1 步和第 2 步是 O(n) =>5000*300 = 1.5m对对来说可能是可以接受的

我会尝试按距离对事件数组进行排序- O(nlogn) - 并且只使用x最短的事件作为我的启发式算法的起点（测试 1-10 最短以查看性能/准确性权衡）+ 之后只保留x最短的集合分裂...

score 0 · Accepted Answer

这是一个有趣的问题，但似乎有很多参数需要考虑。

作为第一步，我会尝试使用兼容性矩阵来简化问题/参数的呈现。矩阵的行将对应于蓝色点，矩阵的列将代表红色点。对于您的示例问题，矩阵将如下所示：

     R1    R2

B1   1     1

B2   1     0

因此，该矩阵表示哪些点可以与哪些其他点配对以产生事件。

接下来，让我们尝试使用此矩阵解决您描述中的示例问题。这可以使用一些动态编程来完成：

假设所有R点都存在，但唯一可用的蓝点是B1。构建一个解决方案向量，列出可能的组合。所以你会得到[(R1, B1)], [(R2, B1)].
现在我们逐步引入B2上一步构建的解向量。对于解向量的第一个分量，注意R1在上一步已经用完了，R2不能与相减B2，所以这个解不能改进。然而，解向量的第二个分量可以被改进，因为(R1, B2)可以添加到它。这样我们就得到了最终的解向量[(R1, B1)],[(R2, B1), (R1, B2)]。
现在，您可以计算解决方案向量的各个组件，并选择其中包含最多项目的组件（或事件，在您的情况下）。

我认为可以将这种方法扩展到您的问题的完整版本，但它需要更多的内务管理（因为您还必须跟踪资源使用情况）。R1与您的示例不同，B1在第一步中配对并不一定意味着R1完成......它可能有足够的资源以便可以重复使用。

我希望这至少能给你一些见解。祝你好运！:)

2 回答 2