algorithm - 从一系列可能有噪声、不一致或不完整的传递关系构建排名

Question

我有一个包含约 1000 种不同 Assets 的列表，我想根据我正在制作的游戏的值(value)对其进行排名。

玩家有机会选择两个 Assets 篮之一。例如，他们可能会被问及他们更愿意选择 A + B 还是 C。

从一个巨大的篮子偏好列表中，我希望按感知值(value)对 Assets 进行排名。

这是一些示例输入，相应地玩家说:

A > B
A + A > B + C
C > B

即他们宁愿有一个 A 而不是一个 B。他们宁愿有 2 个 A 而不是一个 B 和一个 C。等等。

根据这个输入，我认为最有可能的值(value)排名是:

A > C > B

我应该使用哪种算法来解决这个问题？

有时偏好列表会相互矛盾(一些玩家认为 A > B，其他人可能会说 B > A)。如果我有一个单独的玩家技能水平衡量标准，我该如何利用它来获得更准确的排名？

我还需要能够处理篮子之间的关系中存在“孤岛”的情况。例如:

A > B
C > D

即你不能说如果 A <> C.

这在我看来像是一个类似于各种打包算法的优化问题。这个排名问题是 NP-hard 问题吗？

Answer 1

对我来说，它实际上听起来更像是图论。

假设您有一个 A -> B 表示 A < B 的二合字母。那么你可以

• 运行 minimum feedback set algorithm用于排序(在没有矛盾的情况下，就是 Topological Sort )。

• 为您提到的“岛屿”运行 DFS。

---

所以问题是如何构建这样的图。我有一种预感(不幸的是还没有预感)，唯一重要的多变量规则是以下形式:

A_1 + A1 + ... + A_i < A_{i + 1}

它们应该被简化为

A_j < A_{i + 1}, j = 1, .., i。

(除此之外，RHS 多值规则的唯一用途是传递推论(根据我的直觉)，即

A < B + C 和 B + C < D 表示 A < D。但这可以通过使用虚拟变量求和来解决。)

---

也许你应该看看你是否可以验证或反驳这一点。