最优单循环赛程编程思路及MATLAB实现

谢晓敏

（川北幼儿师范高等专科学校 初等教育系，四川 广元 628017）

n支球队在同一场地上进行单循环比赛，为了保证公平性，按照文献[1，2]的编排方法，推广其结论可得：n(n≥5)为奇数时，每两场相隔场次数为；n(n≥5)为偶数时，相隔场次数为[3]

当球队数目较少时，可以手工编排赛程，而球队数目较多时，手工编排就会耗时费力。若能将编排方法用程序实现，就会省时又省力。

笔者将参赛队数目分为奇数和偶数分别进行讨论，理清编程思路，用MTLAB编程给出赛程编排表，并计算出每个参赛队参加的场次数和每两场相隔场次数以及总场次和。

一、参赛队数目为奇数

（一）构造推理法

1.构造推理编排法简述

单循环赛中每两个队伍都要进行一场比赛。对于1号参赛队而言，它要和其余的队伍进行（n-1）场比赛，按照 1-2，1-3，…,1-n的顺序安排（n-1）轮的第一场比赛。最后一轮只安排一场比赛，其余每轮场比赛。从第1轮到第（n-2）轮的最后一场比赛分别为：2-n,2-3,2-4，…，2-（n-1）。剩余的比赛平均的插入第 1轮至第（n-2）轮，每轮场。使每个球队的间隔场次数达到。

2.编程思路

（1）将赛程编排表储存在矩阵A中，当参赛队有n个时，矩阵A有行，2(n-1)列。第1列与第2列同行的参赛队进行一场比赛，自上而下形成第一轮赛程安排。第3列与第4列，以此类推，第(2n-3)列与第2(n-1)构成的第(n-1)轮只有一场比赛。矩阵A的初始值为零矩阵。

（2）安排每轮的第一场比赛，即矩阵A的第一行。奇数列为1号参赛队，偶数列从2号队递增到n号队。再安排每轮的最后一场比赛，即矩阵A的最后一行。为了后面计算间隔方便，最后一行的第1列为2，第二列为n号参赛队，其余奇数列从3号队递增到(n-1)号队，偶数列为2号参赛队。后面的安排中只安排第1至第(n-2)轮的比赛。

（5）其余未安排的位置都是最大号参赛队。

3.MATLAB程序

4.赛程安排

将上面的程序保存为gztlf.m文件。在命令窗口输入〉〉A=gztlf(21)，运行程序，根据程序结果得n=21时的赛程安排如下：

表1 n=21的构造推理法赛程安排

（二）图论法

1.图论编排法简述

将n支球队代表的点按顺时针方向排列成一个“圈”[4]，每两个点之间连一条线，就形成了一个无向完全图Kn，n支球队的单循环赛对应于此图Kn，Kn有条边，对应n支球队的场比赛。将场比赛分成轮，每轮n场比赛。每轮的编排方法基本类似。

首先确定奇数个参赛队中不参加比赛的队伍，可以是任意一个队伍。每轮首先不参加比赛的队伍必须为同一个队伍。剩余队伍数目为偶数个，以不参赛队所处点为参照点，安排分别从顺、逆时针方向看，处在“圈”上对称位置的两个队伍完成一场比赛，按照由近及远的顺序，每队只能参加一场比赛。共计场比赛。

然后从未参加比赛的队伍代表的点走到每轮第一场比赛中的队伍，按照先向小号走再向大号走的原则，为第场比赛。沿每轮第一场比赛的路径行走，走完后向每轮第二场比赛中的队伍行走，仍然先向小号走再向大号走，增加一条路径，每增加一条路径则安排一场比赛。如此反复，直到走到每轮第场比赛号数较大的顶点，共安排场比赛。从刚才结束的顶点走到起始未参加比赛的队伍所处顶点，再安排一场比赛，即第n场比赛。

2.编程思路

（1）将赛程编排表储存在矩阵A中，当参赛队有n个时，矩阵A有n行，(n-1)列。第1列与第2列同行的参赛队进行一场比赛，自上而下形成第一轮赛程安排。第3列与第4列，以此类推，第(n-2)列与第(n-1)列形成第轮比赛。

（2）规定：每轮起始未参加比赛的队伍是号数最大的队伍。第行奇数列的参赛队从1依次增加到。偶数列的参赛队为n。第n行奇数列参赛队为n,偶数列参赛队从依次增加到(n-1)。

3.MATLAB程序

4.赛程安排

将上面的程序保存为tulun.m文件。在命令窗口输入〉〉A=tulun(21)，运行程序，根据运行结果得n=21时的赛程安排如下：

表2 n=21的图论法赛程安排

表2 n=21的图论法赛程安排（续）

二、参赛队数目为偶数

（一）改进的贝格尔编排法简述

著名的贝格尔编排法[5]编排的赛程共有n-1轮，第一轮按照1至n的顺序逆时针按U形走向分成均等两边。n号队安排在每轮的第一场比赛中，第一轮在右边，第二轮在左边，第三轮回到右边，如此反复，第n-1轮又回到右边。从第二轮起，将前一轮右下角的参赛队伍提到本轮第一场比赛中来，其余参赛队伍按照逆时针轮转。贝格尔编排法不能达到最优的场次间隔。

改进的贝格尔编排法从第二轮起，将前一轮第二场比赛右边的参赛队提到本轮第一场比赛中来，其余的队伍编排方法不变。

（二)编程思路

1.将赛程编排表储存在矩阵A中，当参赛队有n个时，矩阵A有行，2(n-1)列。第1列与第2列同行的参赛队进行一场比赛，自上而下形成第一轮赛程安排。第3列与第4列，以此类推，第(2n-3)列与第2(n-1)列构成第(n-1)轮赛程安排。

2.安排每轮的第一场比赛，即矩阵A的第一行。第 2，3，6，7，…,2(n-1)列，均为 n 号参赛队，第1列为1号参赛队，其余列按照从左到右的顺序，参赛队从(n-1)至2的顺序依次递减。

（三）MATLAB程序

（四）赛程安排

将上面的程序保存为gjb.m文件。在命令窗口输入〉〉A=gjb(20)，运行程序，根据运行结果得n=20时的赛程安排如下：

表3 n=20的改进贝格尔编排法赛程安排

三、每个参赛队的参赛场次、两场间隔和总场次数

（一）编程思路

1.输入参赛队数目n和赛程安排表储存矩阵A，输出每个参赛队的参赛场次矩阵P，间隔场次数矩阵J，其中从第一行到第n行分别为1号到n号参赛队的参赛场次和间隔场次。输出每个参赛队的总间隔场次数向量D。

2.先按奇数列和偶数列分别计算每个参赛队参加的场次数，储存在矩阵T中。若T中有0，去除0后，储存在P中。若T中没有0,对于矩阵P的行，按从小到大的顺序排列，即对应每个参赛队参加的场次数从小到大的顺序。对于矩阵P，按行计算间隔场次数后储存在矩阵J中输出，即为每个队的间隔场次数。对于矩阵J按行求和后储存在向量D中输出，即为每个参赛队的总场次数。

（二）MATLAB程序

（三）结果验证

1.构造推理法

在命令窗口输入〉〉n=21;A=gztlf(n);[P J D]=jg(n,A)，运行程序，根据运行结果得n=21时每个参赛队参加的场次数、每两场间隔场次数和总场次和如下：

表4 n=21时参赛队参加的场次数

表5 n=21时每两场间隔场次数和总场次和

2.图论法

在命令窗口输入〉〉n=21;A=tulun(n);[P J D]=jg(n,A)，运行程序，根据运行结果，笔者发现图论法得到的每个参赛队参加的场次数、每两场间隔场次数和总场次与构造推理法的结论表4、表5行不同而已。

3.改进的贝格尔编排法

在命令窗口输入〉〉n=20;A=gjb(n);[P J D]=jg(n,A)，运行程序，根据运行结果得n=20时每个参赛队参加的场次数、每两场间隔场次数和总场次和如下：

表6 n=20时参赛队参加的场次数

表7 n=20时每两场间隔场次数和总场次和

表7 n=20时每两场间隔场次数和总场次和