任意数量选手的循环赛赛程分治算法

《任意数量选手的循环赛赛程分治算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第22卷第4期20(}7年8月郑州轻工业学院学报(自然科学版)JOURNALOFZHENGZHOUUNIVERSITYOFLIGHTINDUSTRY{NaturalScienceV01．22No．4Aug．2007文章编号：1004—1478(2007)04—0122—04任意数量选手的循环赛赛程分治算法李健勇1，李，晔1，刘艳红2，张杰1，李建春1，黄道颖1(1．郑州轻工业学院计算机与通信工程学院．河南郑州450002；2．郑州大学电气工程学院，河南郑州450001)摘要：对任意数量选手的循环赛赛程安排问题，提出了一种新的分治算法．通过将非2。个选

2、手的赛程安排问题偶数化，解决了分解及合并过程中子问题解的交叠问题，证明了原问题解的存在性，最后通过C++语言编程对该分治算法进行了实现与验证．关键词：循环赛算法；分治算法；分解；合并中图分类号：TP391文献标识码：ADivisionandconqueralgorithmfortheroundrobincalendarproblemwitharbitrarycompetitorsLIJian·yon91，LIYel，LIUYan-hang‘，ZHANGJiel，LIJian·ehunl，HUANGDao-yins(1．College0，Comp．andCom

3、．Eng．，Zhengz．houUniv．矿LighlInd．，Zhengztwu，450002，China；2．College0，Electr．Eng．．ZhengzhouUniv,，Zhea鲁=hou450001，Ch／na)Abstract：AnoveldivisionandconqueralgorithmWasproposedfortheroundrobincalendarproblemwitharbitraryeompetitom．First．thenon2‘-competitorcalendarproblemwastranslatedtoapro

4、blemwithevencompetitors，wZichwasessentialtotackletheintersectionofdifferentelementprobldmsduringthedecom-positionandcombinationprocedure．ThenitWasshownthatthereexistsasolutiontothecalendarproblemwitharbitrarycompetitors．AC4-+programWasfinallyputforwardtodemonstratetheeffectivenesso

5、ftheproposedalgorithm．Keywords：roundrobincalendaralgorithm；divisionandconqueralgorithm；decomposition；combination¨弓l吾分治法是一种典型的计算机算法，其基本思想是把一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同，通过求解并合并各子问题的解得到原问题的解．分治算法能够大幅度降低计算规模，被广泛应用于二分搜索、大整数乘法、Strasson矩阵乘法等经典计算问题以及复杂电路设计等．采用分治法能有效地解决2‘个选手的循环赛赛

6、程安排问题⋯，程国忠”1证明了该方法的正确性，并指出对非2‘个选手的赛程安排问题，可能不能直接采用分治算法加以解决．针对非2‘个选手的循环赛赛程安排问题，刘超等”1提出了扩展循环赛收稿日期：2007—01—06基金项目：河南省杰出青年科学基金项目(06t2000600)；河南省自然科学基金项目(0611052300)作者简介：李健勇(1969一)，男，河南省孟州市人，郑州轻工业学院讲师，硕士，主要研究方向：网络控制、对等网络万方数据第4期李健勇等：任意数量选手的循环赛赛程分治算法·123·日程表算法，罗宇等”1则提出了一种行向变换排列的算法．对2f名运动员的

7、单循环赛程安排问题，俞万禧b。61采用图论方法研究了其对集构造．采用分治法能方便地解决2‘个选手的循环赛赛程安排问题的原因在于。当把每个原问题化为2个子问题时。各子问题的解之问不存在交集，通过简单合并即可得到原问题的解．而对非21个选手的循环赛赛程安排，如果采用二分方法进行分解，各子问题的解之问存在交集，必须经过复杂处理之后才能得到原问题的解．本文拟采用分治法来解决非2‘个选手的循环赛赛程安排问题，通过解决各子问题的解之间的交叠问题，证明其分治算法的存在性，并用C++语言实现该算法．12‘个选手循环赛赛程分治算法1．1问题描述2‘个选手的循环赛程安排要求如下

8、．问题1设有2‘个选手进行某类循环比赛．比赛场地资源