摘要：运用针对树形结构以固定搜索路线枚举去穷尽所有可能性方法的“深度优先遍历法”进行单循环赛赛程排布。并且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—），男，北京人，助理研究员，学士，主要研究方向为分析化学。