單循環賽賽程排布的遍歷法生成與評價指標分析

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

關鍵詞：單循環比賽;對稱;深度優先;樹形結構;評價指標

中圖分類號：G642? ? ? 文獻標識碼：A

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

1 引言

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

2 方法的建立

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

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

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

第三步，提供幾種評價賽程優劣的指標;

第四步，將解帶入指標，得出相應的指標的nA、nB個值;

第五步，用統計的辦法，觀測這nA與nB個指標值，分析全面性（有漏）與傾向性（有偏），來判斷各指標的分布有沒有什么不同。

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

本文第3節為第一步到第二步，為賽程的生成方法，第4節為第三步到第六步，為所生成賽程的應用。

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

簡化表示如下：

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

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

p——待排場次對陣可供選擇選手數量;

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

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

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

手段與算法如下：

抽簽或根據實情況定序。

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

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

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

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

步驟②：使用三種手段降低范圍，進行深度優先遍歷：

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

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

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

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

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

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

具體算法因作用由排除變為剪枝，描述為：先確定等價體個數，根據等價體個數多少，先試填各等價體各取一個，再在等價體內，試試能不能取出等價體內兩元素，取了一組就不再執行，以防兩兩等價。

可能的選項最多只有p個參賽體可供選擇，是樹形結構，為少占用計算機內存，可深度優先遍歷進行枚舉。

因此稱之“深度優先遍歷法”。流程圖如圖1。

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

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

深度優先遍歷法可行性可通過遞歸執行次數判斷。

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

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

由圖2、圖3統計結果，可推測遞歸數對數與n呈線性關系，算法歸為指數算法，進而推測此法運行時間，將時間復雜度過高難以解決的n找出。偶數n>10，奇數n>23則因遞歸數過多導致運算時間過長，不宜推廣。

4 評價指標分析

簡化表示如下：

cij——第i隊第j個間隔場次數;

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

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

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

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

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

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

指標的選取：

選取R、F、G、S、Z，用作衡量賽程優劣的依據。

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

本文關注點還有不均勻性的不均勻性：

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

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

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

得到R、F、G、S、Z五個指標。

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

這些指標能否同時達到最佳需要用以下過程驗證。

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

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

表5通過n=4、6、8篩選極值后觀測得到，可知指標能否同時達到極優值：

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

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

裁選手段生成的解，可以將其指標全部求出，而后從全面性和傾向性來進行統計意義的比較。

全面性：是否每個指標的每個值都被保留。

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

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

傾向性：是否朝著更優或更劣的方向有所變動。

從分布的角度，可用均值與標準差來進行比較，數據見表7。

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

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

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

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

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

以上就成為一種評價裁選結果好壞的一種評判依據。

5 結論

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

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

6 結束語

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

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

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

指標間關系可以相等價、相包含、相拮、相獨立，需根據具體需要選取指標。

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

參考文獻：

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

[2] 董東風.循環賽通用編排方法研究[J].湖南郵電職業技術學院學報，2018，17（1）：14-17.

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

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

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

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

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

[8] 田蓓藝，錢鋒.單循環賽賽程安排幾個參數的極值[J].數學的實踐與認識，2005，35（7）：141-146.

收稿日期：2021-08-11

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