1

给定一个有N 个人的类（这由数组 int[] a 表示），其中每个人都与所有其他人玩游戏。每场比赛将只涉及 2 名玩家。所以对于 N 个人，总共会有NC2游戏。

所有游戏的结果都与您同在。您必须将每个人安排在队列中，条件是a[i] 应该用 a[i-1] 赢得比赛。这对于 i 的所有值都是正确的。

我们不需要关心 a[i] 和 a[i-2] 之间的结果。a[i] 可以用 a[i-2] 赢得或输掉比赛。

我的方法（我使用回溯来解决这个问题）：

  • 对于每个人，我们将维护与该人一起赢得比赛的人的列表。
  • 将创建一个新的结果数组（长度等于玩家总数）。
  • 第一个位置由每个人迭代填充。
  • 结果数组中的下一个位置由与前一个人赢得比赛的人填充。这个人将通过迭代该数组从前一个人的相应获奖名单中挑选出来。

上述解决方案将使用递归方法尝试每条路径。没有更好的算法吗？

4

2 回答 2

3

从数学上讲，您所拥有的是一种称为锦标赛图的东西，并且您正试图在该锦标赛图中找到一条哈密顿路径。尽管在任意图中找到哈密顿路径的问题是 NP 困难的，但众所周知，每个锦标赛图都必须有哈密顿路径，幸运的是它们并不难找到。

一种简单的方法是使用递归。如果图中只有一个节点，解决这个问题很简单：只需列出图中的一个人。否则，任意选择某个节点。将锦标赛分为子锦标赛：击败该人的所有人之一和该人输给的所有人之一。在每个子锦标赛中递归地获得一条哈密顿路径。然后，将哈密顿路径连接在一起，将您在第一步中挑出的人放在它们之间的适当位置。

那么这个算法的效率如何呢？与快速排序一样，算法的效率取决于您如何将锦标赛分成更小的部分。假设当你选择一个人将比赛分成更小的部分时，你选择的人的获胜次数尽可能接近 n/2。这将产生两个规模大约为 n/2 的小型锦标赛。确定选择哪个人需要二次时间，因为您必须查看每场比赛的结果才能计算玩家的胜负数。这给了我们以下递归关系：

T(n) = 2T(n/2) + O(n 2 )

使用主定理，我们得到这个递归求解到 O(n 2 )，这比你最初的想法要快得多。

希望这可以帮助！

于 2013-10-24T17:34:46.297 回答
1

这里有一个提示：

假设我们已经对满足约束的前 i-1 人进行了排序。是否总是可以将人 i 插入此列表中的某个地方？

考虑以下情况：要么我击败了所有前 i-1 人，要么一个人都没有，或者他们中的一些人但不是全部。在前两种情况下，我可以插入哪里？（到目前为止，将 1 或 0 分配给列表中的每个 i-1 人可能会有所帮助，表明该人是否击败了第 i 个人。）在第三种情况下，我们可以在他们击败的任何人之间插入第 i 个人和任何击败他们的人。这样的一对总是存在吗？如果没有，是否还有其他地方可以保证我们能够安全地插入人员 i？

于 2013-10-24T17:34:20.857 回答