算法：从一组游戏中选择成对的球队 [英] Algorithm: Selecting pairs of teams from a set of games

问题描述

我正在尝试为体育联赛创建一个调度程序，并且希望按组调度团队，以便每个团队每个组获得一场比赛。我认为我想做的事情是计算机科学中的一个现存问题，但是我不知道它叫什么，而且在查找有关它的信息时遇到了麻烦。无论哪种情况，都是这种情况：

I'm trying to create a scheduler for a sports league and I'd like to schedule the teams in groups so every team gets one game per group. I think the thing I'm trying to do is an existing problem in computer science, but I don't know what it's called and I'm having trouble finding information about it. Either way, here's the situation:

假设我有一组团队 A = {1,2,3，...，n } 和一组成对的球队 B = {（1,2 ,,（1,3），（2,4），（6,9）,。 ..} 。 B不可能拥有来自A的团队的所有可能组合。假设A拥有偶数的团队。我的程序正在尝试创建B的子集（将其称为S子集），以使A中的每个团队都在S中出现一次。它通过一次将一对从B移到S来实现。假设它已经在S中放置了几对。在当前情况下，如何确定是否可以成功创建S？

Let's say I have a set of teams A = {1,2,3,...,n} and a set of pairs of those teams B = {(1,2), (1,3), (2,4), (6,9),...}. B does not have every possible combination of teams from A. Assume that A has an even number of teams. My program is trying to create a subset of B (lets call that subset S) such that every team from A appears in S exactly once. It does this by moving the pairs from B to S, one at a time. Let's say that it has already placed several pairs into S. How can I find out whether it is possible to successfully create S given the current situation?

示例：

A = {1,2,3,4}, B = {(1,2), (1,3), (1,4), (3,4)}

If after one move, S = {(1,2)}, then it can be completed by moving (3,4).
If after one move, S = {(1,3)}, then it cannot be completed.

更新：
此算法将是启发式算法之一我在时间表生成器中使用。目标是将日程表隐式拆分为波浪，每个团队每波浪一局。假设我有16个团队，每个团队与该团队中的其他团队有5场比赛。理想的日程安排将确保在每个团队至少进行一场比赛之前，没有任何团队进行第二场比赛。调度程序一次选择一个游戏，并为其分配一个日期。因此，其想法是让调度程序跟踪在此浪潮中安排的比赛，并且永远不要选择会阻止每个团队在当前浪潮中只玩一次的游戏。调度程序还使用了许多其他启发式方法，因此我无法明确订购游戏并将其按顺序进行。

Update: This algorithm will be one of the heuristics I use in my schedule generator. The goal is to implicitly split the schedule into "waves" where each team has one game per wave. So let's say that I have a pool of 16 teams and each team will have 5 games against other teams in the pool. An ideal schedule would make sure that no team has their second game before every team has had at least one game. The scheduler picks games one at a time and assigns them a date. So the idea is to have the scheduler keep track of the games scheduled in this "wave" and to never pick a game that would prevent each team from playing exactly once in the current wave. The scheduler also uses a bunch of other heuristics, so I can't explicitly order the games and have it go in order.

很抱歉，如果不清楚或不是很严格。随时要求进行澄清，我会尽力进一步解释。

I'm sorry if this is unclear or not very rigorous. Feel free to ask for clarification and I'll do my best to explain further.

推荐答案

它是图论中的最大匹配问题。有一些已知的算法可以解决这个问题。

It's Maximum matching problem in graph theory. There are some known algorithms to solve it.

在问题图中G（V-顶点集，E-边集），其中V = A，E = B 。还向图形添加相反的边缘。每个边缘的权重为1。

In your problem graph G (V - set of vertexes, E - set of edges) where V = A, E = B. Also add opposite edges to graph. Weight of each edge is 1.

我建议您使用 Edmond的方法的tutorials& d2 = hungarianAlgorithm rel = nofollow>匈牙利算法算法。

I suggest you to use Hungarian Algorithm for bipartite graphs and Edmond's algorithm for others.

这篇关于算法：从一组游戏中选择成对的球队的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！