約束編程及其在單循環(huán)賽編排問題的應(yīng)用研究

宋 楷，胡大裟，蔣玉明

(四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065)

各種競賽活動與人們的生活密不可分，通常在時(shí)間和場地都有保證的情況下，單循環(huán)賽是各種競賽中最常用的賽制。在單循環(huán)賽的整個(gè)賽程中所有參賽隊(duì)伍均能相遇一次，不過要編排一個(gè)單循環(huán)賽的賽程是很復(fù)雜的，因?yàn)橘惓痰木幣欧绞街苯佑绊懙奖荣惖墓叫?、合理性、觀賞性以及競賽的發(fā)展。因此，如何對單循環(huán)賽進(jìn)行合理的編排是眾多學(xué)者的研究方向之一。單循環(huán)賽的編排，常使用輪轉(zhuǎn)法、“貝格”編排法［1］以及“貝格”編排法的改進(jìn)方案［2］。輪轉(zhuǎn)法是最基礎(chǔ)的單循環(huán)賽編排方法，但它有一個(gè)先天的弊端，在參賽隊(duì)伍為奇數(shù)時(shí)，會造成參賽隊(duì)伍之間勞逸分配不均，不利于比賽的公平性?！柏惛穹ā彪m然解決了輪轉(zhuǎn)法存在的先天弊端，但只適用于參賽隊(duì)伍實(shí)力平均的情況。當(dāng)參賽隊(duì)伍實(shí)力懸殊時(shí)，可能導(dǎo)致強(qiáng)隊(duì)過早相遇或者連續(xù)相遇，從而影響賽事的觀賞性。針對“貝格法”的種種不足，人們又研究出了許多改進(jìn)方案。但是這些改進(jìn)方案往往只解決“貝格法”某一方面的不足，并不能兼顧所有。

隨著計(jì)算機(jī)的普及，人們開始通過計(jì)算機(jī)來解決復(fù)雜的單循環(huán)賽編排問題［3－4］。傳統(tǒng)的方式是針對具體的競賽背景(隊(duì)伍規(guī)模、場地、時(shí)間、隊(duì)伍實(shí)力等)［5］設(shè)計(jì)專用的算法來完成特定的單循環(huán)賽編排。然而根據(jù)最近的研究發(fā)現(xiàn)，約束編程在處理單循環(huán)賽等實(shí)際問題時(shí)，是優(yōu)于傳統(tǒng)方式的［6］。因此本文提出了一種基于約束編程的統(tǒng)一編排求解模式用于解決單循環(huán)賽的賽程編排問題。

1 約束編程

約束編程(CP)是圍繞著關(guān)系約束這一數(shù)學(xué)概念建立起來的方法論，是研究基于約束組合優(yōu)化問題的計(jì)算系統(tǒng)［7］，即通過聲明必須被滿足的約束(條件、屬性)來求解問題［8］。

CP主要包含3部分:建模、傳播和搜索。建模是將實(shí)際問題轉(zhuǎn)換為CP中約束的過程;傳播是通過約束中的傳播算法，盡可能的削減搜索空間，減小搜索樹的大小。每一個(gè)約束都獨(dú)立于其他約束盡可能地進(jìn)行局部傳播;搜索是在建模和傳播的基礎(chǔ)上，通過對搜索樹進(jìn)行搜索來求解問題。搜索主要包含2部分:1)搜索算法本身，這一部分決定了搜索的具體方式，如搜索是基于深度優(yōu)先原則或者是廣度優(yōu)先原則進(jìn)行等;2)搜索中的動態(tài)變量選擇策略和動態(tài)變量值選擇策略，這一部分決定了搜索的過程中每一步該如何選擇變量與變量的值。

CP主要分為2個(gè)分支:約束求解(Constraint Solving)和約束滿足問題(Constraint Satisfaction Problem)。約束求解主要應(yīng)用于無限域和連續(xù)值，這類問題往往比較復(fù)雜，即是以一組約束來描述某一問題，并應(yīng)用若干的數(shù)學(xué)技巧來對該問題進(jìn)行求解［9］。約束滿足問題起源于人工智能領(lǐng)域中組合問題的研究以及計(jì)算機(jī)圖形學(xué)對圖像分析的研究［10］。現(xiàn)實(shí)中許多組合優(yōu)化、調(diào)度優(yōu)化問題都可以描述為約束滿足問題［11］?？梢赃@樣描述一個(gè)約束滿足問題:給定一組數(shù)目有限的變量X，以及變量的值域D，有限的約束集合C，對于x∈X都有值域Dx，c∈C是定義在X中某些變量上的約束，規(guī)定這些變量的可能取值。一個(gè)約束滿足問題可以表示成P=(X，D，C)。對約束滿足問題求解就是從組合中找出一組或者幾組特定組合滿足所有約束。

單循環(huán)賽編排問題就是一個(gè)約束滿足問題。通過CP可以為單循環(huán)賽的編排提供一個(gè)通用的求解框架，然后將單循環(huán)賽中的涉及到的公平性等因素進(jìn)行約束建模，CP即可搜索出滿足約束的組合，完成單循環(huán)賽的編排。

2 圖論與單循環(huán)賽編排問題的聯(lián)系

在對約束滿足問題建模時(shí)，常常會把約束滿足問題轉(zhuǎn)變成約束圖的形式，約束圖中的節(jié)點(diǎn)表示變量，圖中的弧表示約束［12］。

二分圖又稱作二部圖、兩偶圖，是圖論中的一種特殊模型。設(shè)G=(V，E)是一個(gè)無向圖，如果頂點(diǎn)V可分割為2個(gè)互不相交的子集(A，B)，并且圖中的每條邊(i，j)所關(guān)聯(lián)的2個(gè)頂點(diǎn)i和j分別屬于這2個(gè)不同的頂點(diǎn)集(i in A，j in B)，則稱圖G是一個(gè)二分圖。圖1就是一個(gè)二分圖，圖中每一個(gè)頂點(diǎn)表示一支參賽隊(duì)伍，每一條弧表示一場比賽，隊(duì)伍1、2、3表示A部分，隊(duì)伍4、5、6表示B部分，圖1表示了部分A與部分B可能進(jìn)行的比賽。

假設(shè)現(xiàn)有一個(gè)二分圖G，M是G的一個(gè)子圖，同時(shí)M的邊集中任意2條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是G的一個(gè)匹配。如果M覆蓋了G中所有頂點(diǎn)則M是一個(gè)完美匹配，如圖2所示。一個(gè)完美匹配實(shí)際上就是單循環(huán)賽中某一輪的編排結(jié)果，因此對單循環(huán)賽某一輪的編排問題可以轉(zhuǎn)換為尋找完美匹配的問題。

再結(jié)合約束編程的理論，假設(shè)約束圖G=(V，E)是對單循環(huán)賽某一輪進(jìn)行編排的約束圖，頂點(diǎn)集V中的每一個(gè)頂點(diǎn)表示一支隊(duì)伍，弧集E中的每一條弧表示比賽。那么使用CP求解單循環(huán)賽某一輪編排問題，就是使圖G中每一個(gè)頂點(diǎn)都要滿足完美匹配這樣的約束。

圖1 二分圖

圖2 二分圖完美匹配

3 完美匹配約束

由于常用的CP平臺通常只提供了基本的、有限的約束，如eq(等于約束)、nq(不等約束)等，而沒提供類似完美匹配這樣的約束。因此本文通過在CP平臺Gecode上設(shè)計(jì)并實(shí)現(xiàn)了完美匹配約束。

如前所述，可以定義完美匹配約束為:完美匹配約束接受一個(gè)數(shù)組x［n］作為輸入，使得x［n］中的每一個(gè)元素滿足以下條件:

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

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

假設(shè)有一個(gè)數(shù)組 x［6］，數(shù)組中每一個(gè)元素的值域分別是 D0={1，2，3，5}，D1={1，4，5}，D2={3，4}，D3={0，1，2，3}，D4={1，3}，D5={0，3}。根據(jù)完美匹配約束的定義中的第一個(gè)條件，可以 nq 約束將 1 從 D1移除，將3從D3中移除。但是要滿足第2個(gè)條件，只能在數(shù)組中的某個(gè)元素被賦值后才能使用eq和nq約束實(shí)現(xiàn)，在此之前不能對值域做出任何削減。

CP解決的約束滿足問題常常是NP完全問題，在使用CP進(jìn)行求解時(shí)，實(shí)際上就是采用搜索算法來進(jìn)行求解，所以對于CP而言，搜索的效率是非常重要的。而CP的搜索效率又受搜索樹大小的影響，約束中的傳播算法是至關(guān)重要的。如何設(shè)計(jì)有效的傳播算法，盡可能地削減值域空間，縮小搜索樹的大小是約束設(shè)計(jì)與實(shí)現(xiàn)的核心。

在CP的傳播算法中，一致性算法得到了最廣泛的應(yīng)用。一致性算法是群體一致性研究的重要內(nèi)容［13］，常用的一致性算法包括節(jié)點(diǎn)一致性、弧一致性、邊界一致性以及路徑一致性等算法。其中節(jié)點(diǎn)一致性算法最簡單，主要針對一元約束，其思想是將不滿足約束的值從相關(guān)的變量中移除;而弧一致性主要針對的是二元約束;邊界一致性則多用于連續(xù)域的問題;路徑一致性則考慮了3個(gè)相互連接的節(jié)點(diǎn)之間的約束。而完美匹配約束的第2個(gè)條件是實(shí)際上是關(guān)于x［i］與x［j］的二元約束，弧一致性算法是適合完美匹配約束的。

弧一致性定義:假設(shè)將一個(gè)約束滿足問題P=(X，D，C)轉(zhuǎn)換為約束圖G，X和Y是G中的節(jié)點(diǎn)，(X，Y)是G中的一條弧，如果X值域中的每個(gè)值都能在Y的值域中找到一個(gè)值，使得弧(X，Y)成立，那么，可以認(rèn)為弧(X，Y)是滿足弧一致性的。

由此可知弧一致性算法的核心思想是:如果一個(gè)節(jié)點(diǎn)的某一取值不能取得與其有約束關(guān)系的節(jié)點(diǎn)的值域中至少一個(gè)取值的支持，那么就將該值從該節(jié)點(diǎn)的值域中刪除。通過弧一致性算法，可以將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}，對比值域空間可以發(fā)現(xiàn)弧一致性算法極大地削減了值域空間。

綜上所述，完美匹配約束的實(shí)現(xiàn)中主要包含了2個(gè)傳播算法:1)x［i］≠i，從x［i］的值域中移除i值;2)弧一致性算法，使得數(shù)組x［n］滿足弧一致性。

需要注意的是，實(shí)現(xiàn)弧一致性算法本身也是有消耗的。因此在特定情況下，弧一致性算法雖然能夠有助于削減值域空間，但不一定能夠提高搜索效率。

4 使用完美匹配約束對單循環(huán)賽問題建模

假設(shè)有n支隊(duì)伍，一共需要進(jìn)行r輪比賽，用數(shù)字0到n－1表示各支球隊(duì)，有一個(gè)二維數(shù)組a［n］［r］存儲了每支隊(duì)伍每一輪的對手。于是有約束滿足問題P單循環(huán)賽=(X，D，C)，對于 a［i］［j］∈X(0 ＜i＜n －1，0 ＜j＜r－1)存在值域Di，j={0，…，n －1}，C 是作用于a［n］［r］上的約束集合，使得每一個(gè) 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約束使得數(shù)組 a［i］［］中的每一個(gè)元素各不相等，perfect-matching約束也就是上述設(shè)計(jì)實(shí)現(xiàn)的完美匹配約束，使得數(shù)組a［］［j］的每一個(gè)元素滿足完美匹配。

這樣就完成了最簡單的單循環(huán)賽的建模。在此基礎(chǔ)上，根據(jù)競賽中的公平性、合理性、觀賞性以及競賽的發(fā)展等問題我們可以添加更多的約束條件完成這些問題的建模。然后通過CP平臺對問題進(jìn)行求解，表1即為n=6，r=5時(shí)的求解結(jié)果之一。

表1 5輪6隊(duì)單循環(huán)賽編排CP求解結(jié)果

5 實(shí)驗(yàn)結(jié)果與評估

本文實(shí)驗(yàn)是基于CP平臺Gecode實(shí)現(xiàn)的，借助Gecode提供各模塊接口，采用了從第一個(gè)元素開始選擇的動態(tài)變量選擇策略，從最小值開始選擇的動態(tài)變量值選擇策略，以及深度優(yōu)先的搜索算法。在實(shí)驗(yàn)中，分別采用了Gecode原有約束(即eq、nq等約束)和本文實(shí)現(xiàn)的perfect-matching約束對單循環(huán)賽編排問題建模。通過對比使用不同約束建模的求解時(shí)間、搜索樹大小以及失敗次數(shù)等實(shí)驗(yàn)數(shù)據(jù)分析perfect-matching約束及弧一致性算法對單循環(huán)賽編排問題求解的影響。在本文實(shí)驗(yàn)中，所有實(shí)驗(yàn)數(shù)據(jù)都是基于5次運(yùn)行結(jié)果的平均數(shù)據(jù)。實(shí)驗(yàn)機(jī)搭載了至強(qiáng)六核雙路處理器和32 GB內(nèi)存，操作系統(tǒng)采用了Linux系統(tǒng)。

由于在對簡單單循環(huán)賽進(jìn)行求解時(shí)，隨著隊(duì)伍規(guī)模增大，當(dāng)隊(duì)伍數(shù)目＞8時(shí)，編排問題解的數(shù)目已經(jīng)超過了千萬，所以在該實(shí)驗(yàn)中只記錄了求出一個(gè)解時(shí)的實(shí)驗(yàn)數(shù)據(jù)。表2中Gecode表示使用Gecode現(xiàn)有約束進(jìn)行建模的求解結(jié)果，perfect-matching表示使用本文中實(shí)現(xiàn)的perfect-matching約束進(jìn)行建模的求解結(jié)果。如表2所示，隨著隊(duì)伍規(guī)模的增加，求解的時(shí)間消耗是遞增的。對于簡單單循環(huán)賽，perfect-matching約束并沒有減少求解時(shí)間和搜索樹大小，反而隨著隊(duì)伍規(guī)模的增大，由于使用弧一致性算法的原因，花費(fèi)了更多的時(shí)間，導(dǎo)致使用perfect-matching約束求解所消耗的時(shí)間增長更快。

如表3所示，在該實(shí)驗(yàn)中，假設(shè)單循環(huán)賽受公平性、合理性、觀賞性以及競賽的發(fā)展等問題影響，對單循環(huán)賽問題進(jìn)行了更加嚴(yán)格的約束，規(guī)定了某些隊(duì)伍在某一輪只能跟有限的幾支球隊(duì)比賽，減少了解的數(shù)量。從實(shí)驗(yàn)數(shù)據(jù)可以看出，當(dāng)隊(duì)伍規(guī)模較小時(shí)，perfect-matching約束依舊不能對搜索樹進(jìn)行有效地削減，但是能夠通過較少的調(diào)用傳播器次數(shù)來達(dá)到對值域的同等程度的削減，從而減少了求解時(shí)間。同時(shí)隨著隊(duì)伍規(guī)模增大，問題的復(fù)雜度增加，perfectmatching約束的弧一致性算法能夠在眾多限制條件的基礎(chǔ)上進(jìn)行有效的傳播，極大地削減搜索樹的大小，提高了搜索效率，降低求解所需的時(shí)間。

表2 簡單單循環(huán)賽編排實(shí)驗(yàn)結(jié)果

表3 不同隊(duì)伍數(shù)目復(fù)雜單循環(huán)賽編排實(shí)驗(yàn)結(jié)果

6 結(jié)語

針對單循環(huán)賽編排中遇到公平性、合理性、觀賞性以及競賽的發(fā)展等問題，本文提出了基于CP的統(tǒng)一求解模式。通過約束建模，可以將單循環(huán)賽編排中各種復(fù)雜因素轉(zhuǎn)換為約束，繼而通過CP完成問題的求解。同時(shí)，結(jié)合圖論本文還設(shè)計(jì)與實(shí)現(xiàn)perfect-matching約束用于單循環(huán)賽編排問題的建模，實(shí)驗(yàn)表明，在針對大規(guī)模的復(fù)雜的單循環(huán)賽編排問題時(shí)，perfect-matching約束能夠極大地削減搜索樹大小，減少失敗次數(shù)，從而提高求解的效率。本文沒有研究動態(tài)變量選擇策略、動態(tài)變量值選擇策略以及搜索算法對單循環(huán)賽編排問題的影響，這是進(jìn)一步研究的方向。

［1］黃曉英.單循環(huán)賽編排法的改進(jìn)與對比分析研究［J］.體育世界，2008(5):27－29.

［2］許滸.國際體育競賽編排制度中循環(huán)制“貝格爾編排法”剖析與改革創(chuàng)新之研究［J］.中國體育科技，2002，38(2):59－61.

［3］楊建，卯福啟，席軍林，等.循環(huán)賽競賽編排的算法實(shí)現(xiàn)［J］.現(xiàn)代計(jì)算機(jī)，2012，2(6):18 －20.

［4］陳堅(jiān)，董東風(fēng)，肖波.循環(huán)賽理想輪次編排算法研究［J］.湖北財(cái)經(jīng)高等?？茖W(xué)校學(xué)報(bào)，2010，22(5):54－56.

［5］董東風(fēng)，肖波.論循環(huán)賽“貝格爾”編排法［J］.長沙通信職業(yè)技術(shù)學(xué)院學(xué)報(bào)，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］張居陽.“明月”約束調(diào)度求解器的設(shè)計(jì)與實(shí)現(xiàn)［D］.吉林:吉林大學(xué)，2003.

［8］陳尚偉.基于Java的約束求解器的設(shè)計(jì)與實(shí)現(xiàn)［D］.吉林:吉林大學(xué)，2005.

［9］姚向華，施仁.約束編程及其在產(chǎn)品配置器中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用與軟件，2004，21(3):36－37.

［10］朱星輝，朱金福，高強(qiáng).基于約束編程的飛機(jī)排班問題研究［J］.交通運(yùn)輸系統(tǒng)工程與信息，2011，11(6):151－156.

［11］李云.飛機(jī)一體化排班研究［D］.南京:南京航天航空大學(xué)，2010.

［12］姚向華，楊清宇，施仁.約束滿足問題中一致性算法的分析與研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2007，24(8):11－13.

［13］孟子陽，張弛，李冠華，等.有限時(shí)間的多領(lǐng)航者一致性算法［J］.清華大學(xué)學(xué)報(bào)，2011，51(11):1545－1549.