4

考虑N = 4k玩家、k桌子和许多部落，这样每个成员都可以属于一个部落。一个氏族最多可以包含k玩家。

我们希望组织 3 轮游戏，这样，对于每张正好坐 4 名玩家的桌子，没有 2 名坐在那儿的玩家属于同一个部落，并且在后面的几轮中，没有 2 名坐在那儿的玩家坐在同一个位置表前。所有玩家都玩所有回合。

如果N可以~80很大，我们如何有效地做到这一点？

我想到了这个：

for each table T:
  repeat until 4 players have been seated at T:
    pick a random player X that is not currently seated anywhere
    if X has not sat at the same table as anyone currently at T AND
       X is not from the same clan as anyone currently at T
       seat X at T
       break

我不确定这是否会一直完成，或者即使有有效的分配它也会卡住。即使这有效，还有更好的方法吗？

4

2 回答 2

3

如果每个氏族总是正好有 k 个玩家（即 4 个氏族），那么您知道在一张桌子上应该始终有 1 个氏族的人。在这种情况下，我认为可以提出一些预定义的轮换方案，每个玩家，根据他来自的氏族，进一步移动固定数量的桌子。

如果氏族的数量可以超过4，我认为这是不可能的（或者我看不到，反正）

我觉得你的算法很不错。您可以防止它永远不会终止（如果没有有效的解决方案）同时仍然保持随机行为的一种方法是不要无限地选择随机玩家，而是将未坐下的玩家列表洗牌一次，并处理此列表中的每个玩家转动：

编辑：我忘了遍历轮次，也将其包含在算法中。

for each round R in {1, 2, 3}
  for each table T:
    UP = a randomly shuffled list of unseated players
    for each player X from UP
      if there are less than 4 people seated at T AND
         X has not previously sat with any of the players currently at T AND
         X is not from the same clan as anyone currently at T
           seat X at T

    //No more players left to try for this table
    if T has less than 4 people seated
      abort;  //No solution possible (at least, with the decisions taken so far)

  //All tables filled with players, prepare for the next round.
  for each table T:
    for each player X on T:
      Register on X that he has sat with each of the other 3 players at T
    Unseat all players at T

这样，对于单轮，算法在每张桌子上最多尝试所有玩家一次，因此单次运行在终止之前最多尝试 3*T*N 次让玩家入座（有或没有解决方案）。换句话说，单次运行应该很快完成。

请注意，由于它仍然是随机的，因此多次运行相同的算法是完全可以接受的，因为它每次都会尝试不同的座位组合（使其成为所谓的拉斯维加斯算法）。

编辑 2：用 5 个氏族（每个氏族 16 名玩家）尝试并测试了此算法。通常，它需要大约 400 次运行才能找到第一个解决方案，但总运行时间仍然只有 1 秒左右。

于 2012-10-26T11:01:44.010 回答
1

它卡住了

卡在座位上

我不确定这是否会一直完成，或者即使有有效的分配它也会卡住。

它可能会卡住。假设k = 4 张桌子，N = 16 名玩家，4 个部落，每个部落 4 人。让A1到A4成为氏族A中的玩家，其他氏族也是如此。然后以下是可能由您的算法引起的手工制作情况的示例：

Round 1:
 Table 1: A1, B1, C1, D1
 Table 2: A2, B2, C2, D2
 Table 3: A3, B3, C3, D3
 Table 4: A4, B4, C4, D4

Round 2:
 Table 1: A1, B2, C3, D4
 Table 2: A2, B3, C1 !!!

卡在圆形水平？

一个有趣的问题仍然存在：如果所有三轮的有效分配都是可能的，你能否找到排除第三轮所有有效分配的两轮有效分配？如果是这种情况，您可能会卡在回合级别，因此在执行一些回溯算法时，您有时可能必须撤消完整的回合才能获得有效的解决方案。我没有发生这种情况的例子，也没有强烈的直觉。

更好的方法

有没有更好的方法来做到这一点

我想只要付出足够的努力，就可以将其压缩到一些标准图算法的框架中。最有可能的是，该图形问题将是 NP 难题，因此也不会有多项式时间算法可用于此。

Donald Knuth 写了一篇关于跳舞链接及其在解决精确封面问题中的应用的好论文。在最坏的情况下，它仍然使用回溯和指数时间，但是对于完成大部分工作的搜索树的那些部分，它会保持较小的数据结构，从而加快搜索速度。也许其中一些想法也可以应用于您的情况。不过，只是猜测，还没有考虑到特定的实现。

另一个想法：也许您可以采用增加路径的概念，因为它在计算匹配时使用。这个想法是这样的：如果没有空位的人，从其他玩家中选择一个任意的人。如果该人与当前表兼容，请将其移至该表。这样一来，另一张桌子就会少一个玩家，而您可以尝试使用一些未就座的玩家来填补这个空白。如果这不起作用，您将再次重新安排现有玩家。您可能不应该立即开始移动玩家。相反，您应该首先尝试找到一条完整的增强路径，从一个空座位开始，到一个没有座位的人结束。只有在你验证了这样的链条存在之后，你才能开始根据它来移动人们。

于 2012-10-26T10:57:48.943 回答