c# - 从多个列表或数组中搜索/过滤(可能数十亿)项目组合的最佳方式

Question

我正在尝试编写一个程序来优化游戏的设备配置。问题如下:

1. 角色有六个不同的装备槽来放置元素。这由代码中每个插槽的 6 个单独项目列表表示，其中包含玩家总共拥有的所有设备。

2. 该程序将针对每个可能的设备组合(每个列表中的 1 个)计算角色的总统计数据。这些计算得出的统计数据可以按特定的统计数据最小值/最大值进行过滤，然后还可以按特定的统计数据进行排序，以查明其角色的特定目标统计数据集。

3. 程序应该能够在不耗尽内存或花费数小时的情况下执行这些查询，当然，主要问题是筛选数十亿种可能的组合。

我不确定完成此任务的任何支持数据结构或搜索算法的名称(以便对解决方案进行更多研究)。我想出了以下想法，但我不确定我是否走在正确的轨道上，或者是否有人可以指出我更有效的方向。

我追求的想法是使用递归，其中每个列表(对于每个可能的设备插槽)都设置为树结构，每个渐进列表充当最后一个列表的子项。例如:

Weapons List
|
-----Armor List
     |
     ------Helm List... etc

树的每一层都会保存它可以采用的每条子路径的字典，其中包含每个列表中的 1 个项目的 ID，并逐步计算赋予角色的统计数据(简单地添加武器 + 盔甲 + Helm 的统计数据)遍历树等等...)

当应用了最小/最大过滤器的任何统计数据达到该统计数据的边界时(即，如果统计数据在到达树的底层之前超过最大值，它就会从字典中删除该“路径”，从而从遍历中删除整条可能的结果)。

这里的主要目标是减少搜索算法可能遍历的树路径，并在树需要计算它们之前删除尽可能多的无效结果，以使搜索尽可能快并避免任何浪费的循环。当基于“最大”过滤器删除项目时，这看起来非常简单，因为当逐步添加每个项目的统计信息时，我们可以快速判断统计信息何时超过预期的最大值——但是当涉及到基于最小总统计信息的停止路径时，我我无法思考如何预测和删除这些路径，这些路径最终不会超过第六项的最小值。

为了简化这个想法，可以这样想:

我有 3 个数字数组

[X][0][1][2]
[0] 5  3  2
[1] 1  0  8 
[2] 3  2  7
[3] 2  1  0

我想从 3 个数组(总和)中找出最小为 9，最大为 11 的所有组合。 每个数组必须至少选择但不超过 1 个项目，并且这些选定值的总和就是要搜索的内容。这将需要能够扩展到基本上搜索 6 个以上的数组，每个数组包含 40 个以上的值。上述方法是否在正确的轨道上，或者最好的方法是什么(主要使用 c#)

Answer 1

您应该能够通过为每个插槽使用下限和上限来过滤掉很多项目:

var minimum = slots.Sum(slot => slot.Minimum);
var maximum = slots.Sum(slot => slot.Maximum);

foreach (var slot in slots)
{
    var maxAvailable = maximum - slot.Maximum;
    var minAvailable = minimum - slot.Minimum;
    var filtered = slot.Items
         // If we choose the strongest item in all the other slots and it's still below the minimum
        .Where(item => item.Value + maxAvailable >= request.MinimumValue)
        // If we choose the weakest item in all the other slots and its still above the maximum
        .Where(item => item.Value + minAvailable <= request.MaximumValue);
}

完成此操作后，您可以保证所有组合都将高于请求的最小值，但是某些组合也可能高于请求的最大值，因此将其与您目前的逻辑结合起来，我认为您应该会得到非常理想的结果性能。