约束编程及其在单循环赛编排问题的应用研究

宋 楷，胡大裟，蒋玉明

(四川大学 计算机学院，成都 610065)

各种竞赛活动与人们的生活密不可分，通常在时间和场地都有保证的情况下，单循环赛是各种竞赛中最常用的赛制。在单循环赛的整个赛程中所有参赛队伍均能相遇一次，不过要编排一个单循环赛的赛程是很复杂的，因为赛程的编排方式直接影响到比赛的公平性、合理性、观赏性以及竞赛的发展。因此，如何对单循环赛进行合理的编排是众多学者的研究方向之一。单循环赛的编排，常使用轮转法、“贝格”编排法［1］以及“贝格”编排法的改进方案［2］。轮转法是最基础的单循环赛编排方法，但它有一个先天的弊端，在参赛队伍为奇数时，会造成参赛队伍之间劳逸分配不均，不利于比赛的公平性。“贝格法”虽然解决了轮转法存在的先天弊端，但只适用于参赛队伍实力平均的情况。当参赛队伍实力悬殊时，可能导致强队过早相遇或者连续相遇，从而影响赛事的观赏性。针对“贝格法”的种种不足，人们又研究出了许多改进方案。但是这些改进方案往往只解决“贝格法”某一方面的不足，并不能兼顾所有。

随着计算机的普及，人们开始通过计算机来解决复杂的单循环赛编排问题［3－4］。传统的方式是针对具体的竞赛背景(队伍规模、场地、时间、队伍实力等)［5］设计专用的算法来完成特定的单循环赛编排。然而根据最近的研究发现，约束编程在处理单循环赛等实际问题时，是优于传统方式的［6］。因此本文提出了一种基于约束编程的统一编排求解模式用于解决单循环赛的赛程编排问题。

1 约束编程

约束编程(CP)是围绕着关系约束这一数学概念建立起来的方法论，是研究基于约束组合优化问题的计算系统［7］，即通过声明必须被满足的约束(条件、属性)来求解问题［8］。

CP主要包含3部分:建模、传播和搜索。建模是将实际问题转换为CP中约束的过程;传播是通过约束中的传播算法，尽可能的削减搜索空间，减小搜索树的大小。每一个约束都独立于其他约束尽可能地进行局部传播;搜索是在建模和传播的基础上，通过对搜索树进行搜索来求解问题。搜索主要包含2部分:1)搜索算法本身，这一部分决定了搜索的具体方式，如搜索是基于深度优先原则或者是广度优先原则进行等;2)搜索中的动态变量选择策略和动态变量值选择策略，这一部分决定了搜索的过程中每一步该如何选择变量与变量的值。

CP主要分为2个分支:约束求解(Constraint Solving)和约束满足问题(Constraint Satisfaction Problem)。约束求解主要应用于无限域和连续值，这类问题往往比较复杂，即是以一组约束来描述某一问题，并应用若干的数学技巧来对该问题进行求解［9］。约束满足问题起源于人工智能领域中组合问题的研究以及计算机图形学对图像分析的研究［10］。现实中许多组合优化、调度优化问题都可以描述为约束满足问题［11］。可以这样描述一个约束满足问题:给定一组数目有限的变量X，以及变量的值域D，有限的约束集合C，对于x∈X都有值域Dx，c∈C是定义在X中某些变量上的约束，规定这些变量的可能取值。一个约束满足问题可以表示成P=(X，D，C)。对约束满足问题求解就是从组合中找出一组或者几组特定组合满足所有约束。

单循环赛编排问题就是一个约束满足问题。通过CP可以为单循环赛的编排提供一个通用的求解框架，然后将单循环赛中的涉及到的公平性等因素进行约束建模，CP即可搜索出满足约束的组合，完成单循环赛的编排。

2 图论与单循环赛编排问题的联系

在对约束满足问题建模时，常常会把约束满足问题转变成约束图的形式，约束图中的节点表示变量，图中的弧表示约束［12］。

二分图又称作二部图、两偶图，是图论中的一种特殊模型。设G=(V，E)是一个无向图，如果顶点V可分割为2个互不相交的子集(A，B)，并且图中的每条边(i，j)所关联的2个顶点i和j分别属于这2个不同的顶点集(i in A，j in B)，则称图G是一个二分图。图1就是一个二分图，图中每一个顶点表示一支参赛队伍，每一条弧表示一场比赛，队伍1、2、3表示A部分，队伍4、5、6表示B部分，图1表示了部分A与部分B可能进行的比赛。

假设现有一个二分图G，M是G的一个子图，同时M的边集中任意2条边都不依附于同一个顶点，则称M是G的一个匹配。如果M覆盖了G中所有顶点则M是一个完美匹配，如图2所示。一个完美匹配实际上就是单循环赛中某一轮的编排结果，因此对单循环赛某一轮的编排问题可以转换为寻找完美匹配的问题。

再结合约束编程的理论，假设约束图G=(V，E)是对单循环赛某一轮进行编排的约束图，顶点集V中的每一个顶点表示一支队伍，弧集E中的每一条弧表示比赛。那么使用CP求解单循环赛某一轮编排问题，就是使图G中每一个顶点都要满足完美匹配这样的约束。

图1 二分图

图2 二分图完美匹配

3 完美匹配约束

由于常用的CP平台通常只提供了基本的、有限的约束，如eq(等于约束)、nq(不等约束)等，而没提供类似完美匹配这样的约束。因此本文通过在CP平台Gecode上设计并实现了完美匹配约束。

如前所述，可以定义完美匹配约束为:完美匹配约束接受一个数组x［n］作为输入，使得x［n］中的每一个元素满足以下条件:

1)x［i］≠i(0 ＜ i，j＜ n)

2)x［i］=j↔x［j］=i(0 ＜ i，j＜ n)

假设有一个数组 x［6］，数组中每一个元素的值域分别是 D0={1，2，3，5}，D1={1，4，5}，D2={3，4}，D3={0，1，2，3}，D4={1，3}，D5={0，3}。根据完美匹配约束的定义中的第一个条件，可以 nq 约束将 1 从 D1移除，将3从D3中移除。但是要满足第2个条件，只能在数组中的某个元素被赋值后才能使用eq和nq约束实现，在此之前不能对值域做出任何削减。

CP解决的约束满足问题常常是NP完全问题，在使用CP进行求解时，实际上就是采用搜索算法来进行求解，所以对于CP而言，搜索的效率是非常重要的。而CP的搜索效率又受搜索树大小的影响，约束中的传播算法是至关重要的。如何设计有效的传播算法，尽可能地削减值域空间，缩小搜索树的大小是约束设计与实现的核心。

在CP的传播算法中，一致性算法得到了最广泛的应用。一致性算法是群体一致性研究的重要内容［13］，常用的一致性算法包括节点一致性、弧一致性、边界一致性以及路径一致性等算法。其中节点一致性算法最简单，主要针对一元约束，其思想是将不满足约束的值从相关的变量中移除;而弧一致性主要针对的是二元约束;边界一致性则多用于连续域的问题;路径一致性则考虑了3个相互连接的节点之间的约束。而完美匹配约束的第2个条件是实际上是关于x［i］与x［j］的二元约束，弧一致性算法是适合完美匹配约束的。

弧一致性定义:假设将一个约束满足问题P=(X，D，C)转换为约束图G，X和Y是G中的节点，(X，Y)是G中的一条弧，如果X值域中的每个值都能在Y的值域中找到一个值，使得弧(X，Y)成立，那么，可以认为弧(X，Y)是满足弧一致性的。

由此可知弧一致性算法的核心思想是:如果一个节点的某一取值不能取得与其有约束关系的节点的值域中至少一个取值的支持，那么就将该值从该节点的值域中删除。通过弧一致性算法，可以将1，2从D0中移除，将5从D1中移除，将4从D2中移除，将1从D3中移除，将3从D4中移除，将3从D5中移除，那么新的值域是 D0={3，5}，D1={4}，D2={3}，D3={0，2}，D4={1}，D5={0}，对比值域空间可以发现弧一致性算法极大地削减了值域空间。

综上所述，完美匹配约束的实现中主要包含了2个传播算法:1)x［i］≠i，从x［i］的值域中移除i值;2)弧一致性算法，使得数组x［n］满足弧一致性。

需要注意的是，实现弧一致性算法本身也是有消耗的。因此在特定情况下，弧一致性算法虽然能够有助于削减值域空间，但不一定能够提高搜索效率。

4 使用完美匹配约束对单循环赛问题建模

假设有n支队伍，一共需要进行r轮比赛，用数字0到n－1表示各支球队，有一个二维数组a［n］［r］存储了每支队伍每一轮的对手。于是有约束满足问题P单循环赛=(X，D，C)，对于 a［i］［j］∈X(0 ＜i＜n －1，0 ＜j＜r－1)存在值域Di，j={0，…，n －1}，C 是作用于a［n］［r］上的约束集合，使得每一个 a［i］［j］(0 ＜ i＜ n －1，0 ＜j＜r－1)满足以下约束:

distinct(a［i］［0］，…，a［i］［r－1］)i∈(0，…，n －1)

perfect－matching(a［0］［j］，…，a［n－1］［j］)j∈(0，…，r－1)

distinct约束使得数组 a［i］［］中的每一个元素各不相等，perfect-matching约束也就是上述设计实现的完美匹配约束，使得数组a［］［j］的每一个元素满足完美匹配。

这样就完成了最简单的单循环赛的建模。在此基础上，根据竞赛中的公平性、合理性、观赏性以及竞赛的发展等问题我们可以添加更多的约束条件完成这些问题的建模。然后通过CP平台对问题进行求解，表1即为n=6，r=5时的求解结果之一。

表1 5轮6队单循环赛编排CP求解结果

5 实验结果与评估

本文实验是基于CP平台Gecode实现的，借助Gecode提供各模块接口，采用了从第一个元素开始选择的动态变量选择策略，从最小值开始选择的动态变量值选择策略，以及深度优先的搜索算法。在实验中，分别采用了Gecode原有约束(即eq、nq等约束)和本文实现的perfect-matching约束对单循环赛编排问题建模。通过对比使用不同约束建模的求解时间、搜索树大小以及失败次数等实验数据分析perfect-matching约束及弧一致性算法对单循环赛编排问题求解的影响。在本文实验中，所有实验数据都是基于5次运行结果的平均数据。实验机搭载了至强六核双路处理器和32 GB内存，操作系统采用了Linux系统。

由于在对简单单循环赛进行求解时，随着队伍规模增大，当队伍数目＞8时，编排问题解的数目已经超过了千万，所以在该实验中只记录了求出一个解时的实验数据。表2中Gecode表示使用Gecode现有约束进行建模的求解结果，perfect-matching表示使用本文中实现的perfect-matching约束进行建模的求解结果。如表2所示，随着队伍规模的增加，求解的时间消耗是递增的。对于简单单循环赛，perfect-matching约束并没有减少求解时间和搜索树大小，反而随着队伍规模的增大，由于使用弧一致性算法的原因，花费了更多的时间，导致使用perfect-matching约束求解所消耗的时间增长更快。

如表3所示，在该实验中，假设单循环赛受公平性、合理性、观赏性以及竞赛的发展等问题影响，对单循环赛问题进行了更加严格的约束，规定了某些队伍在某一轮只能跟有限的几支球队比赛，减少了解的数量。从实验数据可以看出，当队伍规模较小时，perfect-matching约束依旧不能对搜索树进行有效地削减，但是能够通过较少的调用传播器次数来达到对值域的同等程度的削减，从而减少了求解时间。同时随着队伍规模增大，问题的复杂度增加，perfectmatching约束的弧一致性算法能够在众多限制条件的基础上进行有效的传播，极大地削减搜索树的大小，提高了搜索效率，降低求解所需的时间。

表2 简单单循环赛编排实验结果

表3 不同队伍数目复杂单循环赛编排实验结果

6 结语

针对单循环赛编排中遇到公平性、合理性、观赏性以及竞赛的发展等问题，本文提出了基于CP的统一求解模式。通过约束建模，可以将单循环赛编排中各种复杂因素转换为约束，继而通过CP完成问题的求解。同时，结合图论本文还设计与实现perfect-matching约束用于单循环赛编排问题的建模，实验表明，在针对大规模的复杂的单循环赛编排问题时，perfect-matching约束能够极大地削减搜索树大小，减少失败次数，从而提高求解的效率。本文没有研究动态变量选择策略、动态变量值选择策略以及搜索算法对单循环赛编排问题的影响，这是进一步研究的方向。

［1］黄晓英.单循环赛编排法的改进与对比分析研究［J］.体育世界，2008(5):27－29.

［2］许浒.国际体育竞赛编排制度中循环制“贝格尔编排法”剖析与改革创新之研究［J］.中国体育科技，2002，38(2):59－61.

［3］杨建，卯福启，席军林，等.循环赛竞赛编排的算法实现［J］.现代计算机，2012，2(6):18 －20.

［4］陈坚，董东风，肖波.循环赛理想轮次编排算法研究［J］.湖北财经高等专科学校学报，2010，22(5):54－56.

［5］董东风，肖波.论循环赛“贝格尔”编排法［J］.长沙通信职业技术学院学报，2010，9(3):92－95.

［6］HENZ M.Constraint－ based round robin tournament planning:Proceedings of the International Conference on Logic Programming，1999［C］.Las Cruces，New Mexico:The MIT Press，1999:545 －557.

［7］张居阳.“明月”约束调度求解器的设计与实现［D］.吉林:吉林大学，2003.

［8］陈尚伟.基于Java的约束求解器的设计与实现［D］.吉林:吉林大学，2005.

［9］姚向华，施仁.约束编程及其在产品配置器中的应用［J］.计算机应用与软件，2004，21(3):36－37.

［10］朱星辉，朱金福，高强.基于约束编程的飞机排班问题研究［J］.交通运输系统工程与信息，2011，11(6):151－156.

［11］李云.飞机一体化排班研究［D］.南京:南京航天航空大学，2010.

［12］姚向华，杨清宇，施仁.约束满足问题中一致性算法的分析与研究［J］.计算机应用与软件，2007，24(8):11－13.

［13］孟子阳，张弛，李冠华，等.有限时间的多领航者一致性算法［J］.清华大学学报，2011，51(11):1545－1549.