單循環(huán)賽賽程排布的遍歷法生成與評價(jià)指標(biāo)分析

摘要：運(yùn)用針對樹形結(jié)構(gòu)以固定搜索路線枚舉去窮盡所有可能性方法的“深度優(yōu)先遍歷法”進(jìn)行單循環(huán)賽賽程排布。并且1）提供了一些降低搜索范圍的手段;2）提供了幾種評價(jià)賽程好壞的指標(biāo);3）提供了一種判斷降低搜索范圍的手段之間針對某些指標(biāo)是否生成結(jié)果有差異的方法。

關(guān)鍵詞：單循環(huán)比賽;對稱;深度優(yōu)先;樹形結(jié)構(gòu);評價(jià)指標(biāo)

中圖分類號：G642? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2022）04-0127-04

1 引言

在兩兩對決的競賽項(xiàng)目中，單循環(huán)是指所有參賽體在競賽中均能且僅相遇一次，最后根據(jù)積分多少排名次的賽制[1]。各領(lǐng)域?qū)τ谘h(huán)賽排法很多，如棋類項(xiàng)目常用“貝格爾法”，球類項(xiàng)目常用“固定1逆時(shí)針輪轉(zhuǎn)法”“奇數(shù)取中輪空法”，根據(jù)各種賽事的特點(diǎn)，發(fā)揚(yáng)該排法的優(yōu)勢，規(guī)避其不利[2]。計(jì)算機(jī)可用作賽程排布的工具，參賽體個(gè)數(shù)為2的方冪時(shí)可用“分治法”實(shí)現(xiàn)[3]，“排除-假設(shè)法”[4]可視作遍歷法的一種。作為被認(rèn)為的一種比較公平合理的比賽制度，循環(huán)賽公平性在于某種對稱性，可以在某個(gè)角度解釋成針對每個(gè)參賽體的對手或是整個(gè)一屆比賽所有的對陣，作為整體集合來看，不因某運(yùn)算（簽位的置換）而集合的整體發(fā)生改變[5]。然而各參賽體在其參與的相鄰兩場比賽中間得到的休整時(shí)間，卻因賽程排布的不同，其均等性可能產(chǎn)生差異，可以運(yùn)用一些指標(biāo)去評價(jià)賽程的優(yōu)劣。本文以Excel中的VBA作為運(yùn)算工具，運(yùn)用 “深度優(yōu)先遍歷法”，進(jìn)行了賽程排布。

2 方法的建立

n個(gè)參賽體，單循環(huán)比賽要進(jìn)行[C2n]場比賽，如不進(jìn)行裁選共有[C2n！]種排布方法。為縮短運(yùn)行時(shí)間，可使用一些手段降低搜索范圍。因統(tǒng)計(jì)手段中兩兩對比的結(jié)論較為清晰，可按照以下步驟，建立手段的比較方法。

第一步，先提供兩種裁選手段A、B;

第二步，根據(jù)兩種裁選手段，計(jì)算機(jī)窮舉出所有的解nA、nB個(gè);

第三步，提供幾種評價(jià)賽程優(yōu)劣的指標(biāo);

第四步，將解帶入指標(biāo)，得出相應(yīng)的指標(biāo)的nA、nB個(gè)值;

第五步，用統(tǒng)計(jì)的辦法，觀測這nA與nB個(gè)指標(biāo)值，分析全面性（有漏）與傾向性（有偏），來判斷各指標(biāo)的分布有沒有什么不同。

第六步，得到結(jié)論——這兩種裁選手段得到的是不是結(jié)果相同的。

本文第3節(jié)為第一步到第二步，為賽程的生成方法，第4節(jié)為第三步到第六步，為所生成賽程的應(yīng)用。

3 裁選手段與窮舉算法描述

簡化表示如下：

mn——各選手每相鄰兩場最小間隔的上界;

Mn——各選手每相鄰兩場最大間隔的下界;

p——待排場次對陣可供選擇選手?jǐn)?shù)量;

方法α——僅使用手段1、手段2 的裁選手段;

方法β——使用手段1、手段2、手段3的裁選手段，交手過與否相同但交手場次不同算作集合改變;

方法γ——使用手段1、手段2、手段3的裁選手段，交手過與否相同但交手場次不同不算作集合改變。

手段與算法如下：

抽簽或根據(jù)實(shí)情況定序。

步驟①：隨即形成第一步的賽程，即每個(gè)參賽體都完成亮相，如表1。

為了追求間隔的盡量大而均，不妨假定已經(jīng)達(dá)到了間隔最大，且其間隔區(qū)間也取在了其最小范圍。事實(shí)上，因?yàn)楸蛔C明是有辦法可行的[6]：

n為奇數(shù)時(shí)，p=3，每兩場間比賽間隔場次數(shù)為（n-3）/2、（n-1）/2;

n為偶數(shù)時(shí)，p=4，每兩場間比賽間隔場次數(shù)為n/2-2、n/2-1、n/2。? ? ?（1）

步驟②：使用三種手段降低范圍，進(jìn)行深度優(yōu)先遍歷：

手段1：使用結(jié)論“mn=[（n-3）/2]” [7]，凝練分叉。（全文公式中，中括號為取整）

具體算法描述為：待排場次的前1、2、…mn場比賽所涉及的參與對陣選手，全部予以排除，挑出p個(gè)備選參賽體。

手段2：在使用手段1的所有結(jié)果中，使用結(jié)論“Mn=[n/2] ”[7]，剪除分枝。

具體算法描述為：在（1）范圍內(nèi)的p-1場已完成比賽，要覆蓋所有的手段1確定的備選參賽體（起頭的除外，即第[n/2]+1場）。

手段3：利用對稱性質(zhì)，歸納同型。

對稱性的解釋為：不因簽位的置換——單對單置換，針對每個(gè)備選參賽體的交過手對手，不含雙方，集合整體不變。

具體算法因作用由排除變?yōu)榧糁?，描述為：先確定等價(jià)體個(gè)數(shù)，根據(jù)等價(jià)體個(gè)數(shù)多少，先試填各等價(jià)體各取一個(gè)，再在等價(jià)體內(nèi)，試試能不能取出等價(jià)體內(nèi)兩元素，取了一組就不再執(zhí)行，以防兩兩等價(jià)。

可能的選項(xiàng)最多只有p個(gè)參賽體可供選擇，是樹形結(jié)構(gòu)，為少占用計(jì)算機(jī)內(nèi)存，可深度優(yōu)先遍歷進(jìn)行枚舉。

因此稱之“深度優(yōu)先遍歷法”。流程圖如圖1。

當(dāng)n為大于3的奇數(shù)時(shí)，方案數(shù)都為2，結(jié)果如表2。此二者之間，于方法β、方法γ都不具前文對稱意義的等價(jià)性。

當(dāng)n為大于2的偶數(shù)時(shí)，方案數(shù)有多種。在交手過與否相同但交手場次不同算不算作同型的理解下，其倍數(shù)關(guān)系如表3。

深度優(yōu)先遍歷法可行性可通過遞歸執(zhí)行次數(shù)判斷。

對于任何大于1的整數(shù)n都可以執(zhí)行該法，有限步內(nèi)可以完成，僅僅是運(yùn)行時(shí)間的問題。甚至當(dāng)n較小時(shí)，可手動(dòng)推演。具體方案數(shù)與遞歸次數(shù)見表4。

可以看出對稱性的實(shí)現(xiàn)機(jī)制：對比對稱性參與與否，方案數(shù)呈2[n/2]倍關(guān)系。可得知這些數(shù)據(jù)的內(nèi)在意義是：步驟①完成的[n/2]場對陣，形成了[n/2]個(gè)對稱性，對稱性會在對陣雙方接下來進(jìn)行的第一場中實(shí)現(xiàn)掉。

由圖2、圖3統(tǒng)計(jì)結(jié)果，可推測遞歸數(shù)對數(shù)與n呈線性關(guān)系，算法歸為指數(shù)算法，進(jìn)而推測此法運(yùn)行時(shí)間，將時(shí)間復(fù)雜度過高難以解決的n找出。偶數(shù)n>10，奇數(shù)n>23則因遞歸數(shù)過多導(dǎo)致運(yùn)算時(shí)間過長，不宜推廣。

4 評價(jià)指標(biāo)分析

簡化表示如下：

cij——第i隊(duì)第j個(gè)間隔場次數(shù);

[r]、R——“平均相隔場次”及其無分母表示;

f、F——“整個(gè)賽程間隔場次的最大偏差”及其無分母表示;

g、G——“選手之間相隔場次的最大偏差”及其無分母表示;

d——“平均相對離差”;

[s]、S——“平均離差”及其無分母表示;

z、Z——“離差的離差”及其無分母表示。

指標(biāo)的選?。?/p>

選取R、F、G、S、Z，用作衡量賽程優(yōu)劣的依據(jù)。

以上指標(biāo)源于姜啟源總結(jié)的衡量賽程優(yōu)劣的指標(biāo) [6]：“平均相隔場次”[r]、“平均相對離差”d、“整個(gè)賽程間隔場次的最大偏差”f 、“球隊(duì)之間相隔場次的最大偏差”g。本文也沿用這幾個(gè)指標(biāo)，作為判斷依據(jù)。

本文關(guān)注點(diǎn)還有不均勻性的不均勻性：

記表征各參賽體i其各自賽程內(nèi)不均勻性的值為si，各si間不均勻性的比較，更可體現(xiàn)各參賽體不公平的差異性。為避免開方等非有理運(yùn)算引出浮點(diǎn)計(jì)算與舍入誤差，用離差代替方差進(jìn)行評價(jià)。

d與[s]的差距僅在于“相對”二字。概念d是[s]“相對”意義的引申。將整體進(jìn)行考慮的話，平均離差[s]在表達(dá)不公平的普遍性量化意義上更具優(yōu)勢，同時(shí)避免了在去分母過程中，測量作為分母的尷尬。

為了不引進(jìn)浮點(diǎn)數(shù)而造成舍入引起的等值誤判，保持各指標(biāo)大小形容賽程優(yōu)劣的意義，其僅與n和常數(shù)相關(guān)的分母均可舍去，只保留分子。

得到R、F、G、S、Z五個(gè)指標(biāo)。

在五個(gè)指標(biāo)中，R越大越好。在滿足手段1的排法中，F(xiàn)、G越小越好 [8]。S與Z都是越小越好。

這些指標(biāo)能否同時(shí)達(dá)到最佳需要用以下過程驗(yàn)證。

n為大于3的奇數(shù)時(shí)，遍歷法獲得的這僅有兩種的方案，五個(gè)指標(biāo)完全一致，五個(gè)指標(biāo)同時(shí)達(dá)到極值。這更印證了此兩種方案，有著某些意義上的等價(jià)性。

n為大于2的偶數(shù)時(shí)，各裁選手段下全部解可以通過遍歷法得到。

表5通過n=4、6、8篩選極值后觀測得到，可知指標(biāo)能否同時(shí)達(dá)到極優(yōu)值：

F與R等價(jià)（分類討論可推出F=n2（n-2）/2-R），G包含于F、R，S相拮于其余所有，Z獨(dú)立于F、R而相拮于G。不能說這些指標(biāo)沒有意義，但其中某些指標(biāo)取到最優(yōu)是與其他指標(biāo)最優(yōu)不一定甚至一定不兼容的。選何種指標(biāo)作為判定依據(jù)，需要根據(jù)具體需要做出抉擇。

在實(shí)際的應(yīng)用過程中，往往并不需要所有符合裁選手段的結(jié)果。在n越來越大時(shí)，尤其是偶數(shù)，方案數(shù)過多，更需要裁掉一些不希望保留的。確定評價(jià)賽程優(yōu)劣的指標(biāo)以及了解各種指標(biāo)在各種裁選手段下的好壞變化，就成為判定裁選手段是否滿足需要的一個(gè)重要依據(jù)。

裁選手段生成的解，可以將其指標(biāo)全部求出，而后從全面性和傾向性來進(jìn)行統(tǒng)計(jì)意義的比較。

全面性：是否每個(gè)指標(biāo)的每個(gè)值都被保留。

F、G、R、S、Z五個(gè)參數(shù)及其組合的等價(jià)類中，F(xiàn)與R等價(jià)，以某幾種指標(biāo)全等作為一個(gè)等價(jià)類，等價(jià)類個(gè)數(shù)隨指標(biāo)選取的變化見表6所示。

從以上數(shù)據(jù)中，可見得，方法β與方法α比較，所有指標(biāo)都是互相保全的。方法γ與方法β比較，G、S、Z均不一定是具有保全性的指標(biāo)。指標(biāo)結(jié)合越復(fù)雜，全面性越不一致。

傾向性：是否朝著更優(yōu)或更劣的方向有所變動(dòng)。

從分布的角度，可用均值與標(biāo)準(zhǔn)差來進(jìn)行比較，數(shù)據(jù)見表7。

方法β與方法α相較全無差異。

方法γ與方法β從均值與標(biāo)準(zhǔn)差來開看，有所變動(dòng)，但浮動(dòng)范圍不大，無顯著傾向性。如必要，可用t-檢驗(yàn)的方法來進(jìn)行判斷分布有無顯著性差異。

此外傾向性還可以用極值保全性來判斷。

均值和標(biāo)準(zhǔn)差的比較固然可以生成更有傾向性的解，但如果極值沒有被保全，則最優(yōu)或最劣解被否決。方法γ與方法β相較，n=4，S極劣不保全;n=6時(shí)，極值保全;n=8時(shí)，S的極優(yōu)值、Z的極劣值不保全。

方法γ與方法β相較，對于S與Z兩種指標(biāo)而言，有極值不保全的可能存在。

以上就成為一種評價(jià)裁選結(jié)果好壞的一種評判依據(jù)。

5 結(jié)論

方法β與方法α相較，全面性與傾向性沒有任何改變，是無差別手段。

方法γ與方法β相較，則針對某指標(biāo)如S、Z，在全面性和傾向性上均有劣勢，不是無差別手段。

6 結(jié)束語

計(jì)算機(jī)作為工具可代工一些重復(fù)運(yùn)算，這使得遍歷、枚舉變成了可能，可以使得循環(huán)賽賽程排布這一實(shí)際的問題變得可以求解。

使用遍歷法時(shí)，將一些并不直觀的結(jié)論描述為手段進(jìn)行裁選，可以凝練出更小范圍，使得運(yùn)算時(shí)間減少。此方向上還有潛藏的優(yōu)化運(yùn)行時(shí)間手段可以繼續(xù)挖掘。其結(jié)果甚至可反過來幫助我們理解一些概念——如“對稱”的實(shí)現(xiàn)機(jī)制。

當(dāng)n過大時(shí)，運(yùn)算量的提升致使求解過程變得不現(xiàn)實(shí)，當(dāng)n過大時(shí)并不是很好的排布方法。

指標(biāo)間關(guān)系可以相等價(jià)、相包含、相拮、相獨(dú)立，需根據(jù)具體需要選取指標(biāo)。

當(dāng)設(shè)計(jì)一些手段使得方案數(shù)縮小時(shí)，可通過全面性和傾向性的判斷，來指出裁選手段之間，針對某指標(biāo)是不是無差別手段。此方向尚有性質(zhì)刻畫、衡量手段上發(fā)展的余地。

參考文獻(xiàn)：

[1] 王丹華，楊海文，劉詠梅.初等數(shù)論[M].北京：北京航空航天大學(xué)出版社，2008.

[2] 董東風(fēng).循環(huán)賽通用編排方法研究[J].湖南郵電職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2018，17（1）：14-17.

[3] 吳秀梅，蔣婧，王少華，等.循環(huán)賽日程表的遞歸和非遞解[J].電腦知識與技術(shù)，2008，4（25）：1445-1448.

[4] 崔凱，楊飛，張艷，等.賽程安排[J].工程數(shù)學(xué)學(xué)報(bào)，2003，20（5）：117-123.

[5] 顧沛.對稱與群[M].北京：高等教育出版社，2001（3）：17-25.

[6] 姜啟源.賽程安排中的數(shù)學(xué)問題[J].工程數(shù)學(xué)學(xué)報(bào)，2003，20（5）：130-133.

[7] 程鋒，梁方楚，蔡軍偉.單循環(huán)賽賽程安排公平性問題的數(shù)學(xué)模型[J].寧波大學(xué)學(xué)報(bào)（理工版），2004，17（1）：70-73.

[8] 田蓓藝，錢鋒.單循環(huán)賽賽程安排幾個(gè)參數(shù)的極值[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2005，35（7）：141-146.

收稿日期：2021-08-11

作者簡介：張齊（1986—），男，北京人，助理研究員，學(xué)士，主要研究方向?yàn)榉治龌瘜W(xué)。