寻找最佳得分组合的算法

Question

我正在寻找一种算法来识别可使总分最大化的游戏结果组合。组合规则 如下:

• 一共有N场比赛
• 每场比赛有 3 种可能的结果(赢、输或平)
• 每个结果都有正面或负面的分数

找到大小为 N 的最佳结果组合以使总分最大化

例如，N = 2:

Game 1, Outcome 1 = +3 points
Game 1, Outcome 2 = -1 points
Game 1, Outcome 3 = -3 points

Game 2, Outcome 1 = -3 points
Game 2, Outcome 2 = +1 points
Game 2, Outcome 3 = +3 points

有了这 2 场比赛和每种可能结果的分值，这里是我希望看到的有序组合列表。请注意，组合 4、5 和 6 是平局，因此它们在这里的顺序可以是任意的。

Combination 1 = (Game 1, Outcome 1) + (Game 2, Outcome 3) -> Total +6 points
Combination 2 = (Game 1, Outcome 1) + (Game 2, Outcome 2) -> Total +4 points
Combination 3 = (Game 1, Outcome 2) + (Game 2, Outcome 3) -> Total +2 points
Combination 4 = (Game 1, Outcome 1) + (Game 2, Outcome 1) -> Total  0 points
Combination 5 = (Game 1, Outcome 2) + (Game 2, Outcome 2) -> Total  0 points
Combination 6 = (Game 1, Outcome 3) + (Game 2, Outcome 3) -> Total  0 points
Combination 7 = (Game 1, Outcome 3) + (Game 2, Outcome 2) -> Total -2 points
Combination 8 = (Game 1, Outcome 2) + (Game 2, Outcome 1) -> Total -4 points
Combination 9 = (Game 1, Outcome 3) + (Game 2, Outcome 1) -> Total -6 points

对于较小的 N 值，我可以通过蛮力计算这些有序组合，但考虑到总共有 3^N 种组合，并且 N 可以大到 128，我不希望蛮力适用于很长。因此，我正在寻找一种方法来识别前 M 个组合，其中 M << 组合总数 (3^N)。

我花了很多时间试图想出一种算法来选择这些组合，但我做空了。如果能给我指明正确方向的任何建议，我将不胜感激。

谢谢

Answer 1

您可以使用 Priority Queue 迭代生成 M 组合.首先，您需要创建一个表示单个组合的数据结构，以及一个计算其分数的函数。例如，您可以使用 N 小整数数组来表示结果的数量。使用评分函数对队列内的组合进行排序。

您还需要一种方法来快速识别您看到的特定组合。为此，您的组合表示需要具有哈希函数。为您探索过的组合创建一个哈希集。

计算最佳组合很简单:您可以通过获取 N 游戏中每一个游戏的最高值(value)结果来实现。将此组合添加到优先级队列中，然后运行以下循环:

• 将下一个最佳组合出列，并将其添加到结果列表中。
• 如果结果列表的长度是M，你就完成了
• 否则，遍历当前组合，并从中产生最多 2N 个“派生”组合
• 在单个游戏结果中，每个派生组合都不同于当前组合
• 将每场比赛的结果从最好到第二好，再到最差。
• 根据您探索过的组合的哈希集检查具有“翻转”结果的组合
• 如果这是一个新的组合，将其添加到哈希集和优先级队列中
• 完成派生组合后，将队列缩减为 M-res 个项目，其中 res 是结果列表中的项目数
• 继续下一次迭代。