1、任意數量選手的循環賽賽程分治算法第22卷第4期.鄭州輕工業學院(自然科學版)2007年8月JOURNALOFZHENGZHOUUNIVERSITYOFLIGHTINDUSTRY(NaturalScience)文章編號:10041478(2007)04012204任意數量選手的循環賽賽程分治算法李健勇,李曄,劉艷紅,張杰,李建春,黃道穎(1.鄭州輕工業學院計算機與通信工程學院,河南鄭州450002;2.鄭州大學電氣工程學院,河南鄭州450001)程安排問題偶數化,解決了分解及合并過程中子問題解的交疊問題,證明了原問題解的存在性,最后通過C+語言編程對該分治算法進行了實現與驗證.關鍵詞:循環賽算法

2、;分治算法;分解;合并中圖分類號:TP391文獻標識碼:A?DivisionandconqueralgorithmfortheroundrobincalendarproblemwitharbitrarycompetitorsLIJian.yong,LIYe,LIUYan.hong,ZHANGJie,LIJianchun,HUANGDaoying(1.CollegeofComp.andCorn.Eng.,ZhengzhouUniv.ofLightInd.,Zhengzhou,450002,China;2.CollegeofElectr.Eng.,ZhengzhouUniv.,Zhengzhou4

3、50001,China)Abstract:Anoveldivisionandconqueralgorithmwasproposedfortheroundrobincalendarproblemwitharbitrarycompetitors.First,thenon2k-competitorcalendarproblemwastranslatedtoaproblemwithevencompetitors,whichwasessentialtotackletheintersectionofdifferentelementproblemsduringthedecomwitharbitrarycom

4、petitors.AC+programwasfinallyputforwardtodemonstratetheeffectivenessoftheproposedalgorithm.Keywords:roundrobincalendaralgorithm;divisionandconqueralgorithm;decomposition;combinationIJ引吾分治法是一種典型的計算機算法,其根本思想是把一個規模為的問題分解為k個規模較小的子問題,這些子問題相互獨立且與原問題相同,通過法能夠大幅度降低計算規模,被廣泛應用于二分搜索,大整數乘法,Strassen矩陣乘法等經典計算問題以及復

5、雜電路設計等.采用分治法能有效地解決2個選手的循環賽賽程安排問題uj,程國忠證明了該方法的正確性,并指出對非2個選手的賽程安排問題,可能不循環賽賽程安排問題,劉超等提出了擴展循環賽收稿日期:20070106基金工程:河南省杰出青年科學基金工程(0612000600);河南省自然科學基金工程(0611052300)作者簡介:李健勇(1969一),男,河南省孟州市人,鄭州輕工業學院講師,碩士,主要研究方向:網絡控制,對等網絡第4期李健勇等:任意數量選手的循環賽賽程分治算法?123?Et程表算法,羅宇等H那么提出了一種行向變換排列的算法.對2名運發動的單循環賽程安排問題,俞萬禧采用圖論方法研究了其對

6、集構造.采用分治法能方便地解決2個選手的循環賽賽程安排問題的原因在于,當把每個原問題化為2個子問題時,各子問題的解之間不存在交集,通過循環賽賽程安排,如果采用二分方法進行分解,各子問題的解之間存在交集,必須經過復雜處理之后才能得到原問題的解.本文擬采用分治法來解決非2個選手的循環賽賽程安排問題,通過解決各子問題的解之間的交疊問題,證明其分治算法的存在性,并用c+語言實現該算法.12個選手循環賽賽程分治算法2個選手的循環賽程安排要求如下.問題1設有2個選手進行某類循環比賽,比賽場地資源充足,現要求設計滿足如下條件的比賽Et程表:1)每個選手必須與其余選手各賽1次;2)每個選手每天只能參賽1次;3

7、)在2一1天內結束比賽.比賽Et程表可以設計成n×n的表A,其中元素a表示選手i在第天所遇到的選手,i=1,n=1,n一1.當J=0時,a表示選手的編號,這里設a=i.采用分治算法解決問題的根本步驟為:1)分解,將原問題分解為k個規模較小,相互獨立,且與原問題形式相同的子問題.2)治理,假設子問題規模較小且易被求解那么直接求解;否那么,遞歸地求解k個子問題.3)合并,將k個子問題的解合并為原問題的解.比賽Et程表可以直接生成,每個選手Et程表中只需填人對方選手號,其賽程可在1天內完成.合并是分治算法的關鍵步驟.假設2組規模為2的選手在前2一1天內完成了組內循環賽,那么在剩下的2.天內

8、,讓第一組的1所示是2.個選手的比賽Et程表.其中左上角(灰色背景,4×4格)與左下角(白色背景,4×4格)的2塊分別為選手1至選手4和選手5至選手8在前3天的比賽Et程表.據此,將左上角小塊中的所有數字按其相對位置抄到右下角,又將左下角小塊中的所有數字按其相對位置抄到右上角,這樣,就得到所有選手在后4的合并方法.表12個選手的循環賽日程表2任意數量選手的循環賽賽程分治算法任意數量選手的循環賽日程表安排問題描述如下.問題2設有n個選手進行某類循環比賽,比賽場地資源充足,現要求設計滿足如下條件的比賽Et程表:1)每個選手必須與其余選手各賽1次;2)每個選手每天只能參賽1次;3

9、)假設n為偶數,循環賽在n一1天內結束;假設n為奇數,循環賽在n天內結束.當n=2t時,為偶數,比賽日程表中每天參賽有?124?鄭州輕工業學院(自然科學版)t對選手,比賽日程表中沒有選手輪空的現象發生.當n=2t+1時,為奇數,比賽日程表中每天參賽還是只有t對選手,多出1名選手,這名選手必須輪空.對n為奇數的情況,可增加1名匿名選手,與匿名選手的比賽即視為輪空.這時,奇數個選手的比論問題方便,以下的證明設選手的數量n為偶數.下面用歸納法來證明問題2的解的存在性.證明當n=1時,不需要安排比賽;當n=2時,2個選手只須1天完成比賽;當n=3時,3個選手顯然只需3天完成比賽,在每天的賽程安排中總有

10、1名選手輪空.即,當n<4時,問題2有解.假設選手數量為1,2,n一1時,問題2有解,下面證明選手數量等于n時,問題2有解.證明已設選手的數量n為偶數,那么令n=2m.假設可知,對于m個選手的情況,問題2有解.1)假設m為偶數,那么可在前m一1天內完成2個小組的內循環賽,后m天讓第一組的每個選手分別與第二組的m個選手各賽一場,從而形成n個選手的比賽日程表.比賽在2m一1天,即n1內完成.2)假設m為奇數,那么可在前m天內完成2個小組的內循環賽,其中,每個小組每天都會有一個選手前m天內,每天可安排2個小組內輪空的選手進行比賽.從而,前m天內,2個小組內的每個選手都完成了組內比賽,并

11、且每個選手還與另一組的其中一名選手進行了比賽.在剩下的m一1天內,再讓第一組每個選手與第二組中沒有相遇過的m一1個選手進行比賽.與m為偶數時相同,所形成的比賽日程表會在2m一1天,即n一1內完成.證畢.以上的證明過程已表達了算法的根本思想,從中可歸納出如下分治策略.2.3.1分解假設選手數量為奇數,那么添加1個匿名選手平分為2個小組,每小組選手數量為m=n/2,即m為子問題的規模.2.3.2治理假設子問題的規模為2,即小組內選手數量為2時,那么在1天內即可完成比賽,直接安排賽程;否那么,遞歸調用本算法進行處理.2.3.3合并合并分2種情況處理.1)假設m為偶數,那么可在前m一1天內完成每小組的

12、內循環賽,后m一1天內讓第一組的第i個選手在第天與第二組的第(+一1)modm+1個選手進行比賽,其中,J=m,m+1,n一1.2)假設m為奇數,那么可在前m天內完成每小組的內循環賽,同時,在前m天內每個小組每天都會有1個選手輪空,由于采用算法相同,每小組中輪空的組內的1對輪空的選手進行比賽.這樣,就形成了前m天內2個小組的組內循環賽日程表和每個選手與天內讓第一組第i個選手在第天與第二組的第(+一1)modm+1個選手進行比賽,其中,J=m+1,m+2,n一1.2.4算法的C+語言實現#defineMAX500classroundRobinfriendschedule(int);private

13、:intmax;/參賽選手人數/賽程安排表.數組a的第0列ai兒0中存儲第i個選手的實際編號,第i個選手的編號實為i+1,ai兒中存儲編號為i的選手在第天的對手的編號./intaMAX兒MAX;voidRRSchedule(int,int);/本函數將生成編號從start開始的n個隊員的循環賽日程表./voidroundRobin:RRSchedule(intstart,int凡)intm,i,icomp,temp;/如果只有2個選手,那么直接安排賽程if(n=2)astart兒1=astart+1兒0;astart+1兒1=astart兒0;else/否那么,選手多于2人/假設n為奇數,那么

14、添加編號為0的匿名選手,遞歸調用自身求解/第4期李健勇等:任意數量選手的循環賽賽程分治算法?125?if(n%2=1)temp=口start+n0;/將第n+1個選手編號置0口start+n0=0;cycle(start,n+1);/恢復原來編號口start+n0=temp;/假設n為偶數.那么平分為2個小組,各自安排前m天的賽程/if(n%2=0)m=n/2:cycle(start,m);cycle(start+m.m);/假設m為奇數,前m天的比賽中,2小組內進行的比賽每天都恰有1個人輪空,因此先安排2組中輪空的2個選手比賽,然后安排第m+1天到第n一1天的賽程,第1組的第i個選手在第天的

15、對手是第二組的第(i+一1)%m+1個,即大組中第(i+一1)%m+m+1個選手/if(m%2=1)for(i=c;i<c+m;i+)for(j=1;<=m;+)if(i=0)口i=口i+m0;口i+m=口i0;for(i=1;i<=m;i+)for(j:m+1<n;+)icomp=(i+一1)%m+m+1;口start+i一1=口icomp+start一10;口start+i_comp一1J=口i+start一10;/endif(m%2=1)/假設m為偶數,安排第m天到第n一1天的賽程/if(m%2=0)for(i=1;i<=m;i+)for(j=m;j<=n一1;+)icomp=(i+一1)%m+m+1;start+i1=start+icomp一10;口start+icomp一1J=口start+i一10;/endif(m%2=0endff(n%2=:0)/endelse3結論用分治法求解非2個選手循環賽賽程安排問選手的方法將奇數問題偶數化,可以在遞歸求解子問題時只考慮2種情形,從而簡化子問題的分解與同求解方法有著不同的復雜度,各解法的算法復雜度比擬是值得研究的問題.另外,非2個選手的循環賽賽程安