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

Division and conquer algorithm for the round robin calendar problem with arbitrary competitors

作　　者：李健勇[1] 李晔[1] 刘艳红[2] 张杰[1] 李建春[1] 黄道颖[1] 

机构地区：[1]郑州轻工业学院计算机与通信工程学院,河南郑州450002 [2]郑州大学电气工程学院,河南郑州450001

出　　处：《郑州轻工业学院学报（自然科学版）》2007年第4期122-125,共4页Journal of Zhengzhou University of Light Industry:Natural Science

基　　金：河南省杰出青年科学基金项目(0612000600);河南省自然科学基金项目(0611052300)

摘　　要：对任意数量选手的循环赛赛程安排问题,提出了一种新的分治算法.通过将非2k个选手的赛程安排问题偶数化,解决了分解及合并过程中子问题解的交叠问题,证明了原问题解的存在性,最后通过C++语言编程对该分治算法进行了实现与验证.A novel division and conquer algorithm was proposed for the round robin calendar problem with arbitrary competitors. First, the non 2k-competitor calendar problem was translated to a problem with even competitors, which was essential to tackle the intersection of different element problems during the decomposition and combination procedure. Then it was shown that there exists a solution to the calendar problem with arbitrary competitors. A C ＋ ＋ program was finally put forward to demonstrate the effectiveness of the proposed algorithm.

关 键 词：循环赛算法 分治算法 分解 合并 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]