1、1（20_届）本科毕业设计信息与计算科学赛程安排问题的研究2正文目录摘要1关键词11引言32赛程的类型及其应用321淘汰赛322单循环赛423分组循环赛824举例93总结12参考文献12ABSTRACT13致谢143赛程安排问题的研究摘要赛程安排问题在现实生活中具有广泛的应用。由于参赛人员、时间、场地等限制，使得比赛的类型多种多样，实际中常见的比赛类型包括单淘汰制、单循环制、双循环制、分组循环制等。本文主要对单淘汰制与单循环制的编排方法进行了总结，并分析了世界杯的赛程安排对各球队的利弊，最后简单介绍了NBA赛程的公平性指标问题关键词赛程安排单循环分组循环41引言随着现代体育赛事的规模的日益庞大
2、，对于传统的纯手工管理水平上的竞赛编排已经与现代体育的发展产生差距。当然，对于一项规模较大的赛事，编制一套完整的、使各个球队之间的比赛尽可能的公平的赛程是一件相当不容易的事，也是相对复杂的。一个合理而科学的赛程的安排方案能对球队实力的发挥和成绩的走向有着莫大的影响，然而各种竞赛的编排又是一项繁重而细心的工作，不得有半点马虎，否则会影响比赛的正常进行。然而赛程编排的思路的方法往往是根据比赛的需要来定的，如单循环赛、双循环赛、淘汰制都是体育赛事中所常常遇到的赛制。例如世界杯的赛程就是以小组单循环赛加上复赛淘汰制的赛制构成的。不同的比赛，编排者往往都会细心的为该比赛去设计一套最合适的赛制，通过文献的
3、查找发现，不少人也对赛程合理的诸多条件和会对赛程公平性产生影响的一些因素进行了探讨。然而大部分关于赛程安排方面的问题还是集中在场次间隔方面，如“贝格尔编排法”5被认为是现阶段最合理、最先进的竞赛编排法，它解决了传统编排法中对第二轮中轮空队非常不合理的问题，相关文献中就对此编排法在单循环竞赛中的应用进行了分析。单循环制“全旋”法8，也较为合理的解决了劳逸方面的问题。2赛程的类型在体育比赛中由于不同时间、场地等方面的限制而为了使竞赛更加的合理、客观和公正，大赛主办方往往采用淘汰制和循环制来安排赛程，其中循环制又分为单循环、双循环、分组循环三种方法。21淘汰赛淘汰赛是现代体育竞技比赛中最为常见也最为
4、普遍用到的一种比赛体制。淘汰赛是指体育比赛和其它各种比赛中的一种赛制，在这种赛制中赛员两两相对，输一场即淘汰出局。每一轮淘汰掉一半选手，直至产生最后的冠军。在单淘汰赛制中赛会组委会事先会将全部选手按预赛名次或种子顺序进行编排，也支持部分种子选手直接从中间某轮开始参加比赛的安排（即轮空）。这样做的目的是避免实力强的选手过早相遇，导致后面的比赛中对阵双方的实力相差过于悬殊，影响比赛的悬念和精彩程度。例1某校组织乒乓球比赛，因报名人数较多，决定采用单淘汰形式进行比赛。请问如何合理地安排赛程方案1允许第一轮中有轮空现象。设有N人报名参赛，下面我们为不同的值进行讨论。5（1）若NK2ZK，第一轮比赛有1
5、2K场，四分之一决赛有2场，半决赛有2场，冠亚军比赛1场，合计场数PP21212K1N（2）若MN2ZM，则存在一个正整数K，使得KKN221，第一轮比赛次数是12KN，NK2人轮空，剩下的人数为12KNN12K，这样之后的1K轮比赛中的场数为121K，所以一共要比赛12KN121K1N方案2设有N人报名参赛，每一轮都允许有轮空现象。则存在一个正整数K，使得KKN221。若本轮比赛人数为偶数，则没有轮空；若人数为奇数，则有1人轮空。从而比赛轮空的人数不大于1K人。22单循环赛单循环赛，是所有参加比赛的队均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次。如果参赛队不多，而且时间和场地
6、都有保证，通常都采用这种竞赛方法。1）关于单循环赛比赛的轮数和场数的计算比赛的轮数在循环制比赛中，各队都参加完一场比赛即为一轮。参加比赛的队数为奇数时，比赛的轮数等于队数。如5个队参加比赛，即比赛轮数为5轮；参加队数是偶数时，则比赛轮数为队数减1。如8个队参加比赛，比赛的轮数为817轮。计算轮数的目的，在于计算比赛所需的总时间。2）单循环比赛的场次计算设有N队参加比赛，则每队都要与其余的N1支队分别比赛一场。当N为偶数时，则要举行N1轮比赛；当N为奇数时，则要举行N轮比赛，且每轮有1队轮空，其中轮空问题也是值得探讨的。定理设有N支球队参加比赛，则比赛的总场数是2NC如果有N支队伍参加比赛，A队
7、和B队不分主客场只比赛一次，第N支队伍只需要跟N1支队伍各比赛一场，第N1支队伍只需要跟剩下的N2只队伍各比赛一场，以此类推，单循环比赛场次计算的公式为XN1N2N30N（N1）/2，即队数（队数1）/2。例如68个队参加比赛，比赛的总场数是28场。场次计算的目的，也是在于计算比赛所需的场地数量，并由此考虑裁判员的数量，以及如何编排竞赛日程表等。例2参加排球比赛的26个班级，先分成3个小组，其中两个组为9队，另一个组为8队，在小组中，先用单循环赛产生每个小组的前两名，接下来，每小组的前两名共6个队再进行单循环赛。以8支队的小组为例，对赛程进行合理安排。解在第一阶段100283636282929
8、CCC场在第二阶段1526C场一共比赛的场次数为10015115场。3）整个赛场的公平性指标实际上，例如在5个队进行比赛时，如果要保证每个队不连续比赛，必定有一个队的比赛场次为1，4，7，10，另外一个队的比赛场次为2，4，6，8（或3，5，7，9），这两队的比赛间隔相差了比较多，不符合常理。对于N比较大的情况下，这种矛盾也是肯定存在的。为了来衡量只能赛程的整体公平性，保证每两场比赛间相隔场次数尽可能均匀,我们也可以用到方差分析7的方法进行验证。4）单循环比赛的编排在球类单循环比赛中，无论参加比赛队数对少，都要解决偶数队和奇数队的编排方法和把高潮（种子队1种子队2）安排在什么轮次上的问题。对偶
9、数队、奇数队以及高潮的编排，总是按照大赛竞赛组织者的意图去进行的。尽管编排的方法有着多种多样，任何一种编排都应该严格遵循以下的原则去考虑1参赛队机会相等，利益均衡。2能反映出运动的规律。利于各队在比赛中打出风格，赛出真正的水平。3能体现出竞赛编排工作的规律。编排起来有规可循，顺理成章。4符合运动员、竞赛组织者和观众的愿望。在单循环比赛顺序的编排，我们会根据参赛队数是奇数还是偶数，采用多种不同类型的轮转方法加以实现。下面我们以8支球队（偶数）为例用逆时针轮转法对单循环赛进行编排用IA，81I表示八支代表对，则87654321AAAAAAAA75836241AAAAAAAA53728461AAAA
10、AAAA32547681AAAAAAAA24365871AAAAAAAA46283751AAAAAAAA68472531AAAAAAAA7场队队次A1A2A3A4A5A6A7A8间隔场次间隔总数A11255219171333333318A211620266112344432219A325162121922744322217A452021524271024443219A521261215381843222417A69619243142822444319A717112227814432224417A813237101828422244418从上表可知，这样的排法下场次间隔比较平均，是公平比赛的合理
11、编排方案。当参赛队为7支时，将奇数队按偶数队编排，也就是在最后一位数后面加一个“0”使之变为偶数，凡是遇“0”的队就表示轮空一次。见下表表17队参加比赛第一轮第二轮第三轮第四轮第五轮第六轮第七轮10171615141312270675645342303625047362504745342302706756我们从表中可以看出，1号位置固定不动，其他位置每轮按逆时针方向转动一个位置，即得出了下一轮的比赛顺序。这种编排方法存在着一些不足按表1的编排不难看出,当奇数队参赛按单循环原方法编排,有这样一个规律即参赛队为奇数队N时,则N1号队从第四轮开始所遇到的对手都是前一轮轮空的队如参赛的奇数队越多,则N
12、1号队所遇到的前一轮轮空的队就越多,其总数为N3个前一轮轮空队。如表1中,“6”号队从第四轮起所遇的“4、2、7、5”四个队均为前一轮的轮空队。所以这样编排的比赛程序,明显严重存在着劳逸不均的问题,很难做到相对公平、合理。其实我们可以换一种轮转的方法，就可以巧妙的避免上述方法所带来的问题。我们采用将“0”号位置固定中间不动，其他位置每轮逆时针方向转动一个位置，即可以排列出下一轮的比赛顺序，其中遇到“0”者，亦为该轮轮空。第一轮第二轮第三轮第四轮第五轮第六轮第七轮177665544332212615746352413783524137261574640302010706050从上表中可以看出，不
13、存在哪个对（人）总是和上一轮休息好的队（人）进行比赛，这样就很好的解决了劳逸不均所造成比赛公平性方面的问题，同时也还能把焦点战（种子队1对阵种子队2）放在最后阶段，保证了比赛的观赏性。这样的安排方式就能将比赛的机遇或者说是偶然性降低到一个较小的水准，赛出的成绩也能基本反映出各队的真是水平。下面我们再来看看场次间隔的问题13351113场51223311场23511212场61233514场35112312场72335114场41123310场从上面各队场次统计可以看出，每队的场次间隔还是很不平均，这样仍热会对整个赛程的公平性造成影响。为了进一步解决上述因为休息场次不均衡所带来的问题，我们采用以
14、下方法设IA7,2,1I表示7支参赛队根据单循环赛的要求，得到7支队的比赛总场次为21126727C场，总的场次为7轮，因为每一轮都有一支队伍轮空，所以依次将每两小轮连接为一大轮，每支球队参加且仅参加完两次比赛为一大轮，然后利用“最小号固定双向轮转法”14对比赛进行编排，具体排法如下（1）7654321AAAAAAA6472531AAAAAAA4263751AAAAAAA（2）第七场第六场第五场第四场第三场第二场第一场76543217654321AAAAAAAAAAAAAA第十四场第十三场第十二场第十一场第十场第九场第八场64725316472531AAAAAAAAAAAAAA第二十一场第二十
15、场第十九场第十八场第十七场第十六场第十五场42637514263751AAAAAAAAAAAAAA我们用上述排法实际上总共进行了3次排序，共7轮比赛的一个方案，以下表格显示了场次间隔的情况，场队队次A1A2A3A4A5A6A7场次间隔间隔总数9A11818151142323212A21521917133333315A38521220162233313A418212614103333214A51591263192222311A611172014373322212A741316101972222210从上面的表格中可知各支队伍的每两场比赛之间的休息场次还是比较均匀的，这样就很好的解决了场次间隔的问
16、题，比赛的公平性得到了质的提升。23分组循环分组循环，是将所有参加比赛的队先分成若干个小组进行第一阶段预赛，然后每组的优胜队之间再进行第二阶段的决赛，决定第1名和以下的名次。在分组预赛中采用单循环的比赛方法，在决赛中可采用单循环赛、同名次赛、交叉赛等，故也称这种竞赛方法为混合循环制或“两阶段制”。分组循环适用于有较多的队参加的竞赛，可以在不长的期限内较合理较公平地完成竞赛任务。分组循环的不足之处，是参赛队由于实力不同，如果分布不均，可能造成强队先期被削减、弱队反而名次排列在前面的局面。为了克服这个缺陷，在编排中应设立“种子队”。所谓“种子队”，就是实力和成绩相对较强的队，应被合理地分开种子队“
17、可以通过协商确定，也可以根据上一届比赛的名次来确定。为了照顾主办竞赛的单位，有时也将竞赛规程中应作出规定，还要经过一定会议的讨论和认可。分组循环的具体编排如下例如，有16支球队参加比赛，为了使各组的队数相均，在预赛中可以分成4个小组，每组4个队。如果时间、经费允许，又希望多打比赛，也可以分成两个小组，每组8个队。在分成4个小组中，“种子队”可以设立4个队，也可以设立8个队，经抽签编到小组内进行单循环赛，然后决出每小组出线球队，在复赛中则可以通过同名次赛、交叉淘汰赛等方式决出最后的冠军。24举例国际足坛最高级别的足球赛事世界杯就是分组循环的一个典型例子。在98年盛夏举行的法兰西世界杯想必是我们8
18、0后一代的球迷对足球最初的回忆，在赛程方面它就是通过小组单循环赛加上复赛交叉淘汰的方式决出最后的冠军。虽然比赛已经成为过去，然而作为一项世界性的大型体育赛事，它的赛程编制方面还是值得我们来研究与探讨的。世界杯足球赛属于赛会制的比赛,而时间短、比赛多、强度大又是赛会制比赛的特点,越是在10短时间内连续比赛的话,球队的疲劳累积程度就越高,之后的比赛的难度就越大,所以无论哪支球队，只要想走的更远就必须做好经受体能上严酷考验的准备。特别是淘汰赛阶段,由于淘汰赛采用的是一场定胜负的淘汰制,所以赛程的安排对每支从小组出线的球队都至关重要。这里假设每支球队都有夺冠的可能,重点通过小组赛最后一轮及淘汰赛阶段比
19、赛的赛程安排来分析不同阶段的比赛对每个小组出线球队影响的不同程度。1）巴西队、意大利队、东道主法国队、西班牙队、荷兰队、德国队、罗马尼亚队、阿根廷队为种子球队，分组表1ABCDEFGH巴西意大利法国西班牙荷兰德国罗马尼亚阿根廷摩洛哥喀麦隆南非尼日利亚比利时南斯拉夫英格兰克罗地亚苏格兰奥地利丹麦保加利亚墨西哥美国突尼斯牙买加挪威智利沙特巴拉圭韩国伊朗哥伦比亚日本2）比赛的赛制和赛程分为8个小组，每个小组均为单循环比赛，其中小组前两名获得出线进行复赛。小组赛时间表2表2ABCDEFGH第一轮时间610和611611612612和613613614614和615615第二轮时间616616和6176
20、17和618617和618618和619619620620和621第三轮时间621622622623624623624625复赛采用淘汰制表3八分之一决赛时间表1112345678对阵双方A1,B2C1,D2D1,C2B1,A2E1,F2G1,H2F1,E2H1,G2时间安排625626626627627628628629注A1为A组第一名，以此类推表4四分之一决赛时间表表5半决赛时间表注WI为1/8决赛第I场的胜者注SI为1/4决赛第I场的胜者从以上的赛程表可以看出，赛程的安排比较紧了，大多数的球队都是要在3到4天内打两场比赛。3赛程结构图在图EVG,中的每一个顶点V表示比赛，弧E表示每两场
21、比赛间隔的天数完全赛程结构图如图1图1其中顶点V1至V8代表A组至H组的最后一轮比赛顶点V9至V16分别表示A1对B2、C1对D2、E1对F2、G1对H2、B1对A2、D1对C2、F1对E2、H1对G2，V17至V20表示4场1/4决赛V21和1234对阵双方W5,W6W1,W2W3,W4W7,W8时间安排7172727312对阵双方S1,S2S3,S4时间安排7677V1V2V3V4V5V6V7V8V9V10V11V12V13V14V15V16V17V18V19V20V21V22V2312V22表示两场半决赛，V23代表最后决赛4我们由图1可知，这是一个有向图，它的每一个顶点代表比赛，弧上的
22、权值W代表每两场比赛间间隔的天数，根据表2、3、4、5以及最后决赛的时间安排就可得出各条弧上的权值5我们通过得出该带权有向图的初始化邻接矩阵并对其实施行FLOYD法16，得到每对顶点间的最短路径，从中分析结果1在1/8决赛时,对于B组第二名和D组出线的两支球队以及E组的头名和H组的第二名都是最不利的,因为他们要在四天内打两场比赛两场比赛间的间隔天数加上比赛日的天数,即弧的权值之和加顶点数对A组第二出线的球队最有利,他们中间有5天的时间没有比赛。2在1/4决赛时,对H组的第二名来说是最不利的,他们将在7天内打3场比赛3在半决赛时,对H组的第二名来说是最不利的,若想进决赛的话,他们将在12天内打完
23、4场比赛4如果想要从小组赛最后一轮开始一直打到最后的冠军争夺战的话,对A组的两只出线球队是最有利的,因为他们只要在20天内打5场比赛而对H组的两只出线球队来说是最不利的,他们必须在16天内打5场比赛。3总结体育竞赛是社会及校园文化生活的主要内容，也是推动各项运动的普及，促进运动水平提高的有效方法；是培养社会主义体育道德风尚的一个重要阵地；是检查教学、训练、管理质量、交流经验、互相学习、增进友谊、促进发展的重要手段。为了使竞赛达到预期的目的，复杂而细致的竞赛组织、编排工作是关键的一环。在体育竞赛中，组织与编排是整个竞赛能否顺利进行的关键。关系到整个比赛是否合理、有序、公正、公平。众所周知，体育竞
24、赛具有神秘性、戏剧性、残酷性和悬念感。体育精神讲究的是“公平、公正”。应当遵循公开、公正、公平的原则。公平竞争才是体育竞赛的灵魂。我们从上边的介绍和分析可以大致了解到赛程安排的一些原理和它在体育赛事当中的一些应用，当然如果我们学好了赛程编排，对我们今后在体育运动等相关方面的工作将有很大的作用。主要参考文献1董东风，篮球赛程安排流程研究J，长沙通信职业技术学院学报，200822姜启源，赛程安排中的数学问题J，工程数学学报，200353张春平，两种赛程安排问题的研究J，南通纺织职业技术学院学报，200344傅本路，单循环赛程的优化数学模型J，肇庆学院学报，2003105张如海，浅析“贝格尔编排法”
25、J，体育数学，2007136李建春，一种任意数量选手循环赛程填表构造算法J，郑州轻工业学报学报，200967刘玉红，方差分析计算中可能出现的问题及解决方法的探讨J，中国卫生检测杂志，201028孙光明，篮球比赛奇数队单循环制编排的探讨J，达县师范高等专科学校学报，200369余元生，对体育竞赛中奇数编排的探讨J，科技信息，200910王涛，世界杯足球赛中的数学问题J，数学通讯，200211田蓓艺，单循环赛赛程安排几个参考的极值J，数学的实践与认识，2005712张佳，球赛赛程安排的模型求解J，工程数学学报，2003513程焕林，关于赛程安排的数学模型J，达县师范高等专科学校学报，2003214
26、崔凯，赛程安排J，工程数学学报，2003315程国忠，赛程问题分治算法J，西化师范大学学报，2004316林竞，基于最短路径的世界杯赛赛程分析J，赣南师范学院学报，2010617ARWAHRABIE,SYNTHESISANDSCHEDULINGOFOPTIMALBATCHWATERRECYCLENETWORKSCHINESEJOURNALOFCHEMICALENGINEERING，200818TYRELRUSSELL，MANIPULATINGTOURNAMENTSINCUPANDROUNDROBINCOMPETITIONSRESEARCHOFMATCHARRANGEMENTABSTRACTMA
27、TCHARRANGEMENTISWIDELYUSEDINPRACTICEDUETOTHEPARTICIPANTS,TIME,SITESANDOTHERRESTRICTIONS,THEREAREMANYTYPESOFCOMPETITIONELIMINATION、ROUNDROBIN、DOUBLEROUNDROBIN、GROUPEDROUNDROBINANDSOONTHISCOMPOSITIONFOCUSESONTHEROUNDROBINANDGROUPEDROBIN,ANDSUMMARIZETHEPROCESSOFTHESEMETHODSINADDITION,THECOMPOSITIONANAL
28、YZESTHEADVANTAGESANDDISADVANTAGESOFEACHTEAMINTHEWORLDCUPCOMPETITIONKEYWORDSMATCHARRANGEMENTROUNDROBINGROUPEDROUNDROBIN14致谢本论文自始至终在导师孙高济老师的悉心指导下进行。孙老师治学严谨，精益求精的作风深深地感染和激励着我。从课题的选择到项目的最终完成，孙老师都始终给予我细心的指导和不懈的支持，在这里向孙老师表示深深的感谢。在此，我还要感谢同一论文小组的其它同学，正是由于你们的帮助和支持，我才能克服一个一个的困难和疑惑，直至本文的顺利完成。在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我无言的帮助，在这里请接受我诚挚的谢意最后，感谢父母对我在学业和生活上的关心和支持。
