最優(yōu)單循環(huán)賽程編程思路及MATLAB實(shí)現(xiàn)

謝曉敏

（川北幼兒師范高等?？茖W(xué)校 初等教育系，四川 廣元 628017）

n支球隊(duì)在同一場地上進(jìn)行單循環(huán)比賽，為了保證公平性，按照文獻(xiàn)[1，2]的編排方法，推廣其結(jié)論可得：n(n≥5)為奇數(shù)時，每兩場相隔場次數(shù)為；n(n≥5)為偶數(shù)時，相隔場次數(shù)為[3]

當(dāng)球隊(duì)數(shù)目較少時，可以手工編排賽程，而球隊(duì)數(shù)目較多時，手工編排就會耗時費(fèi)力。若能將編排方法用程序?qū)崿F(xiàn)，就會省時又省力。

筆者將參賽隊(duì)數(shù)目分為奇數(shù)和偶數(shù)分別進(jìn)行討論，理清編程思路，用MTLAB編程給出賽程編排表，并計算出每個參賽隊(duì)參加的場次數(shù)和每兩場相隔場次數(shù)以及總場次和。

一、參賽隊(duì)數(shù)目為奇數(shù)

（一）構(gòu)造推理法

1.構(gòu)造推理編排法簡述

單循環(huán)賽中每兩個隊(duì)伍都要進(jìn)行一場比賽。對于1號參賽隊(duì)而言，它要和其余的隊(duì)伍進(jìn)行（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）輪，每輪場。使每個球隊(duì)的間隔場次數(shù)達(dá)到。

2.編程思路

（1）將賽程編排表儲存在矩陣A中，當(dāng)參賽隊(duì)有n個時，矩陣A有行，2(n-1)列。第1列與第2列同行的參賽隊(duì)進(jìn)行一場比賽，自上而下形成第一輪賽程安排。第3列與第4列，以此類推，第(2n-3)列與第2(n-1)構(gòu)成的第(n-1)輪只有一場比賽。矩陣A的初始值為零矩陣。

（2）安排每輪的第一場比賽，即矩陣A的第一行。奇數(shù)列為1號參賽隊(duì)，偶數(shù)列從2號隊(duì)遞增到n號隊(duì)。再安排每輪的最后一場比賽，即矩陣A的最后一行。為了后面計算間隔方便，最后一行的第1列為2，第二列為n號參賽隊(duì)，其余奇數(shù)列從3號隊(duì)遞增到(n-1)號隊(duì)，偶數(shù)列為2號參賽隊(duì)。后面的安排中只安排第1至第(n-2)輪的比賽。

（5）其余未安排的位置都是最大號參賽隊(duì)。

3.MATLAB程序

4.賽程安排

將上面的程序保存為gztlf.m文件。在命令窗口輸入〉〉A(chǔ)=gztlf(21)，運(yùn)行程序，根據(jù)程序結(jié)果得n=21時的賽程安排如下：

表1 n=21的構(gòu)造推理法賽程安排

（二）圖論法

1.圖論編排法簡述

將n支球隊(duì)代表的點(diǎn)按順時針方向排列成一個“圈”[4]，每兩個點(diǎn)之間連一條線，就形成了一個無向完全圖Kn，n支球隊(duì)的單循環(huán)賽對應(yīng)于此圖Kn，Kn有條邊，對應(yīng)n支球隊(duì)的場比賽。將場比賽分成輪，每輪n場比賽。每輪的編排方法基本類似。

首先確定奇數(shù)個參賽隊(duì)中不參加比賽的隊(duì)伍，可以是任意一個隊(duì)伍。每輪首先不參加比賽的隊(duì)伍必須為同一個隊(duì)伍。剩余隊(duì)伍數(shù)目為偶數(shù)個，以不參賽隊(duì)所處點(diǎn)為參照點(diǎn)，安排分別從順、逆時針方向看，處在“圈”上對稱位置的兩個隊(duì)伍完成一場比賽，按照由近及遠(yuǎn)的順序，每隊(duì)只能參加一場比賽。共計場比賽。

然后從未參加比賽的隊(duì)伍代表的點(diǎn)走到每輪第一場比賽中的隊(duì)伍，按照先向小號走再向大號走的原則，為第場比賽。沿每輪第一場比賽的路徑行走，走完后向每輪第二場比賽中的隊(duì)伍行走，仍然先向小號走再向大號走，增加一條路徑，每增加一條路徑則安排一場比賽。如此反復(fù)，直到走到每輪第場比賽號數(shù)較大的頂點(diǎn)，共安排場比賽。從剛才結(jié)束的頂點(diǎn)走到起始未參加比賽的隊(duì)伍所處頂點(diǎn)，再安排一場比賽，即第n場比賽。

2.編程思路

（1）將賽程編排表儲存在矩陣A中，當(dāng)參賽隊(duì)有n個時，矩陣A有n行，(n-1)列。第1列與第2列同行的參賽隊(duì)進(jìn)行一場比賽，自上而下形成第一輪賽程安排。第3列與第4列，以此類推，第(n-2)列與第(n-1)列形成第輪比賽。

（2）規(guī)定：每輪起始未參加比賽的隊(duì)伍是號數(shù)最大的隊(duì)伍。第行奇數(shù)列的參賽隊(duì)從1依次增加到。偶數(shù)列的參賽隊(duì)為n。第n行奇數(shù)列參賽隊(duì)為n,偶數(shù)列參賽隊(duì)從依次增加到(n-1)。

3.MATLAB程序

4.賽程安排

將上面的程序保存為tulun.m文件。在命令窗口輸入〉〉A(chǔ)=tulun(21)，運(yùn)行程序，根據(jù)運(yùn)行結(jié)果得n=21時的賽程安排如下：

表2 n=21的圖論法賽程安排

表2 n=21的圖論法賽程安排（續(xù)）

二、參賽隊(duì)數(shù)目為偶數(shù)

（一）改進(jìn)的貝格爾編排法簡述

著名的貝格爾編排法[5]編排的賽程共有n-1輪，第一輪按照1至n的順序逆時針按U形走向分成均等兩邊。n號隊(duì)安排在每輪的第一場比賽中，第一輪在右邊，第二輪在左邊，第三輪回到右邊，如此反復(fù)，第n-1輪又回到右邊。從第二輪起，將前一輪右下角的參賽隊(duì)伍提到本輪第一場比賽中來，其余參賽隊(duì)伍按照逆時針輪轉(zhuǎn)。貝格爾編排法不能達(dá)到最優(yōu)的場次間隔。

改進(jìn)的貝格爾編排法從第二輪起，將前一輪第二場比賽右邊的參賽隊(duì)提到本輪第一場比賽中來，其余的隊(duì)伍編排方法不變。

（二)編程思路

1.將賽程編排表儲存在矩陣A中，當(dāng)參賽隊(duì)有n個時，矩陣A有行，2(n-1)列。第1列與第2列同行的參賽隊(duì)進(jìn)行一場比賽，自上而下形成第一輪賽程安排。第3列與第4列，以此類推，第(2n-3)列與第2(n-1)列構(gòu)成第(n-1)輪賽程安排。

2.安排每輪的第一場比賽，即矩陣A的第一行。第 2，3，6，7，…,2(n-1)列，均為 n 號參賽隊(duì)，第1列為1號參賽隊(duì)，其余列按照從左到右的順序，參賽隊(duì)從(n-1)至2的順序依次遞減。

（三）MATLAB程序

（四）賽程安排

將上面的程序保存為gjb.m文件。在命令窗口輸入〉〉A(chǔ)=gjb(20)，運(yùn)行程序，根據(jù)運(yùn)行結(jié)果得n=20時的賽程安排如下：

表3 n=20的改進(jìn)貝格爾編排法賽程安排

三、每個參賽隊(duì)的參賽場次、兩場間隔和總場次數(shù)

（一）編程思路

1.輸入?yún)①愱?duì)數(shù)目n和賽程安排表儲存矩陣A，輸出每個參賽隊(duì)的參賽場次矩陣P，間隔場次數(shù)矩陣J，其中從第一行到第n行分別為1號到n號參賽隊(duì)的參賽場次和間隔場次。輸出每個參賽隊(duì)的總間隔場次數(shù)向量D。

2.先按奇數(shù)列和偶數(shù)列分別計算每個參賽隊(duì)參加的場次數(shù)，儲存在矩陣T中。若T中有0，去除0后，儲存在P中。若T中沒有0,對于矩陣P的行，按從小到大的順序排列，即對應(yīng)每個參賽隊(duì)參加的場次數(shù)從小到大的順序。對于矩陣P，按行計算間隔場次數(shù)后儲存在矩陣J中輸出，即為每個隊(duì)的間隔場次數(shù)。對于矩陣J按行求和后儲存在向量D中輸出，即為每個參賽隊(duì)的總場次數(shù)。

（二）MATLAB程序

（三）結(jié)果驗(yàn)證

1.構(gòu)造推理法

在命令窗口輸入〉〉n=21;A=gztlf(n);[P J D]=jg(n,A)，運(yùn)行程序，根據(jù)運(yùn)行結(jié)果得n=21時每個參賽隊(duì)參加的場次數(shù)、每兩場間隔場次數(shù)和總場次和如下：

表4 n=21時參賽隊(duì)參加的場次數(shù)

表5 n=21時每兩場間隔場次數(shù)和總場次和

2.圖論法

在命令窗口輸入〉〉n=21;A=tulun(n);[P J D]=jg(n,A)，運(yùn)行程序，根據(jù)運(yùn)行結(jié)果，筆者發(fā)現(xiàn)圖論法得到的每個參賽隊(duì)參加的場次數(shù)、每兩場間隔場次數(shù)和總場次與構(gòu)造推理法的結(jié)論表4、表5行不同而已。

3.改進(jìn)的貝格爾編排法

在命令窗口輸入〉〉n=20;A=gjb(n);[P J D]=jg(n,A)，運(yùn)行程序，根據(jù)運(yùn)行結(jié)果得n=20時每個參賽隊(duì)參加的場次數(shù)、每兩場間隔場次數(shù)和總場次和如下：

表6 n=20時參賽隊(duì)參加的場次數(shù)

表7 n=20時每兩場間隔場次數(shù)和總場次和

表7 n=20時每兩場間隔場次數(shù)和總場次和