添加和删​​除人员的循环算法

Question

好的，在这个 codepen 中我已经找到了循环赛调度算法：https://codepen.io/Piconey/pen/mwPamwvar players = [  {    playerName: 'Person 1',  },  {    playerName: 'Person 2',  },  {    playerName: 'Person 3',  },  {    playerName: 'Person 4',  },  {    playerName: 'Person 5',  },  {    playerName: 'Person 6',  },  {    playerName: 'Person 7',  },  {    playerName: 'Person 8',  },  {    playerName: 'Person 9',  },  {    playerName: 'Person 10',  },  {    playerName: 'Person 11',  },  {    playerName: 'Person 12',  },  {    playerName: 'Person 13',  },  {    playerName: 'Person 14',  },  {    playerName: 'Person 15',  },  {    playerName: 'Person 16',  },];var numberOfRounds = players.length - 1;function generateRounds() {  for(i = 0; i < numberOfRounds; i++) {    document.write('<h1 class="round">'+'Round ' + (i+1) + '</h1>');        for (var j = 0; j < players.length / 2; j++) {       document.write('<div class="match">' + players[j].playerName + " - " + players[players.length - 1 - j].playerName +'</div>');    }    players.splice(1, 0, players[15]);    players.pop();  }}generateRounds();我用它来快速约会，即使你可以和每个人约会。我的问题：每轮结束后，新人都可以加入活动或离开活动（如果他们感到无聊；）注意：迟到者不需要和所有人约会，因为他们已经错过了 x 轮。 注 2：如果很多人离开，最好限制轮数，这样人们就不需要在轮次之间等待那么长时间日期

Answer 1

对于二分匹配问题，例如分开的男性和女性组之间的快速约会，您可以使用最大流算法。

构建 4 层图：

1. 源节点S

2. 每个人一个节点

3. 每位女性一个节点

4. 汇聚节点T

• 完全连接第 1 层到第 2 层，边缘容量为 1

• 完全连接第 2 层至第 3 层，边缘容量为 1

• 完全连接第 3 层至第 4 层，边缘容量为 1

当添加一个人时，将其添加为第 2 层或第 3 层中的新节点，并如上所述完全连接到相邻层。

当一个人被移除时，移除他们在第 2 层和第 3 层的节点以及他们节点上的所有边。

在每一轮中，使用最大流算法来识别您的配对。本轮结束后，将参与配对的第2层->第3层边的容量设置为0。这样可以防止相同的两个人在后续轮次中再次匹配。

---

启发式：您可以修改最大流算法，将日期最少或轮次最多的人员配对，因此，如果存在奇数人数，则最新的人和同一个人都不会坐在轮次中。

扩展：您可以通过过滤第 2 层和第 3 层之间添加的边集来实现首选项来限制潜在匹配集。

时间：每轮大约 O(n^3)

---

对于任何人对任何人的匹配问题，您必须将最大流算法替换为更复杂的 Blossom 算法。

与最大流一样，该算法通过查找增广路径然后修改其当前的匹配集来迭代地细化匹配。

该算法的输入是：

• 为每个人添加一个节点

• 完全连接所有节点

与二分情况一样，在每轮结束时，删除与前几轮匹配的所有边，以防止相同的两个人被匹配。

当有新人加入时，添加一个节点并将其与其他人完全连接起来。

当一个人离开时，删除他们的节点和所有连接的边。