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

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

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

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

1 引言

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

2 方法的建立

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

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

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

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

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

第五步，用統(tǒng)計的辦法，觀測這nA與nB個指標(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ù)實情況定序。

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

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

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

n為偶數(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個備選參賽體。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

簡化表示如下：

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

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

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

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、“整個賽程間隔場次的最大偏差”f 、“球隊之間相隔場次的最大偏差”g。本文也沿用這幾個指標(biāo)，作為判斷依據(jù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

6 結(jié)束語

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

收稿日期：2021-08-11

作者簡介：張齊（1986—），男，北京人，助理研究員，學(xué)士，主要研究方向為分析化學(xué)。