论文部分内容阅读
摘 要：本文针对以往传统的日程赛安排系统容易受到参赛规模问题变复杂的不利因素，提出了一种利用分治思想和循环赛安排方法相融合的算法，有效地提高了比赛日程安排的准确率。
关键词：分治法;循环日程赛;算法分析
近几年来，由于赛事日程安排制度的不断改革，各级日程安排岗位对日程安排信息管理信息化的需求与日俱增。因为对大多数的循环赛日程管理者而言，如何有效地管理循环赛的日程安排，使其发挥最大的效率，是每位循环赛日程管理者所面临的难题及挑战。所以日程安排管理系统成了循环赛日程管理的重中之重。
在以人为本的理念下，循环赛安排管理在赛事组织中的作用日益突出。但是，人员的复杂性和组织的公正、公开使得日程安排的管理成为难题。基于现今对循环赛事要求越来越高的趋势，日程安排管理系统将成为循环赛日程管理的一个非常重要的内容。日程安排管理系统的作用之一是规划日程安排，帮助管理者建立日程安排档案。它很好地利用分治的思想，使赛事安排变得合理、简单。它的出现使得日程安排档案查询、调用的速度加快，也使得精确分析大量参赛队员的知识、经验、技术、能力成为可能。所以，实现循环赛日程安排管理系统的公正化、数字化、科学化和网络化是非常有必要的。
一、分治思想
1.分治思想的概念
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
2.分治法的适用条件
用分治法求解的问题一般都满足以下几个条件：（1）该问题的规模缩小到一定的程度就可以容易地解决。（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（3）利用该问题分解出的子问题的解可以合并为该问题的解。能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。
3.分治法的求解步骤
首先，分解子问题。如果问题规模很小，直接就能求出问题的解，可以不用分解问题，否则就以递归方式不断分解子问题，直到每个子问题都能直接求解为止。然后，递归地求解子问题。最后，合并子问题的解，分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。
二、算法设计
1.日程赛问题概述
设有n=2k个运动员要进行网球循环赛。现要设计一个满足要求的比赛日程表。（1）每个选手必须与其他n-1个选手个比赛一次;（2）每个选手一天只能赛一次;（3）循环赛一共进行n-1天。按此要求可将比赛日程设计成有n行和n-1列的表。在表中的第i行和第j列处填入第i个选手在第j天遇到的选手。
2.算法应用
按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。
分析过程具体如下：
若n=1，赛程表如表1。
表1
[1]
若n=2，赛程表如表2。
表2
[1][1][2][2]
若n=3，则：（1）添加一个虚拟选手4号，构成n+1=4。（2）因为4/2=2，所以把参赛选手分两组，每组各自安排（1 2），（3 4）。每组跟另一组分别比赛（拷贝），四个选手比赛的赛程如表3。
表3
以此类推，若n=8，那赛程如表4。
表4
归纳起来，算法步骤如下：
（1）如果n为偶数，可分为两个n/2人的组分别比赛，然后两组间比赛;如果n/2为偶数，左下角为左上角加n/2来得到，然后左下角拷贝到右上角，左上角拷贝到右下角;如果n/2为奇数，先安排左下角（除0外都加n/2），然后把同一天都有空的选手安排比赛。然后，右上角要按规则一来完成，右下角由规则二来定。
（2）如果n为奇数，则加1个选手使n+1成为偶数。转化成偶数名选手的赛程安排问题来解决。最后把虚拟选手n+1号所在位置上的值置为0，即完成安排。
三、结论
在本文中，筆者提出了一种基于分治思想的循环日程赛安排问题的算法，将分治思想应用在日程赛安排问题中。由于分治法的分解、求解、合并能让复杂的问题简单化，赛程安排问题的求解难度取决于参赛规模，为了有效实现赛程安排，我们设计了一种将分治思想与赛程安排方法相融合的算法。本文算法可以用网络软件开发成系统，推广应用于各种竞赛活动中。
参考文献：
[1]汪力君.分治算法在排课系统中的分析与应用[J].安徽建筑工业学院学报（自然科学版），2007，15（6）.
[2]霍红卫.算法设计与分析[M].西安：西安电子科技大学出版社，2005.
[3]王海源.分治算法的两种思路和形式[J].上海师范大学学报（自然科学版），2003（1）.
关键词：分治法;循环日程赛;算法分析
近几年来，由于赛事日程安排制度的不断改革，各级日程安排岗位对日程安排信息管理信息化的需求与日俱增。因为对大多数的循环赛日程管理者而言，如何有效地管理循环赛的日程安排，使其发挥最大的效率，是每位循环赛日程管理者所面临的难题及挑战。所以日程安排管理系统成了循环赛日程管理的重中之重。
在以人为本的理念下，循环赛安排管理在赛事组织中的作用日益突出。但是，人员的复杂性和组织的公正、公开使得日程安排的管理成为难题。基于现今对循环赛事要求越来越高的趋势，日程安排管理系统将成为循环赛日程管理的一个非常重要的内容。日程安排管理系统的作用之一是规划日程安排，帮助管理者建立日程安排档案。它很好地利用分治的思想，使赛事安排变得合理、简单。它的出现使得日程安排档案查询、调用的速度加快，也使得精确分析大量参赛队员的知识、经验、技术、能力成为可能。所以，实现循环赛日程安排管理系统的公正化、数字化、科学化和网络化是非常有必要的。
一、分治思想
1.分治思想的概念
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
2.分治法的适用条件
用分治法求解的问题一般都满足以下几个条件：（1）该问题的规模缩小到一定的程度就可以容易地解决。（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（3）利用该问题分解出的子问题的解可以合并为该问题的解。能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。
3.分治法的求解步骤
首先，分解子问题。如果问题规模很小，直接就能求出问题的解，可以不用分解问题，否则就以递归方式不断分解子问题，直到每个子问题都能直接求解为止。然后，递归地求解子问题。最后，合并子问题的解，分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。
二、算法设计
1.日程赛问题概述
设有n=2k个运动员要进行网球循环赛。现要设计一个满足要求的比赛日程表。（1）每个选手必须与其他n-1个选手个比赛一次;（2）每个选手一天只能赛一次;（3）循环赛一共进行n-1天。按此要求可将比赛日程设计成有n行和n-1列的表。在表中的第i行和第j列处填入第i个选手在第j天遇到的选手。
2.算法应用
按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。
分析过程具体如下：
若n=1，赛程表如表1。
表1
[1]
若n=2，赛程表如表2。
表2
[1][1][2][2]
若n=3，则：（1）添加一个虚拟选手4号，构成n+1=4。（2）因为4/2=2，所以把参赛选手分两组，每组各自安排（1 2），（3 4）。每组跟另一组分别比赛（拷贝），四个选手比赛的赛程如表3。
表3
以此类推，若n=8，那赛程如表4。
表4
归纳起来，算法步骤如下：
（1）如果n为偶数，可分为两个n/2人的组分别比赛，然后两组间比赛;如果n/2为偶数，左下角为左上角加n/2来得到，然后左下角拷贝到右上角，左上角拷贝到右下角;如果n/2为奇数，先安排左下角（除0外都加n/2），然后把同一天都有空的选手安排比赛。然后，右上角要按规则一来完成，右下角由规则二来定。
（2）如果n为奇数，则加1个选手使n+1成为偶数。转化成偶数名选手的赛程安排问题来解决。最后把虚拟选手n+1号所在位置上的值置为0，即完成安排。
三、结论
在本文中，筆者提出了一种基于分治思想的循环日程赛安排问题的算法，将分治思想应用在日程赛安排问题中。由于分治法的分解、求解、合并能让复杂的问题简单化，赛程安排问题的求解难度取决于参赛规模，为了有效实现赛程安排，我们设计了一种将分治思想与赛程安排方法相融合的算法。本文算法可以用网络软件开发成系统，推广应用于各种竞赛活动中。
参考文献：
[1]汪力君.分治算法在排课系统中的分析与应用[J].安徽建筑工业学院学报（自然科学版），2007，15（6）.
[2]霍红卫.算法设计与分析[M].西安：西安电子科技大学出版社，2005.
[3]王海源.分治算法的两种思路和形式[J].上海师范大学学报（自然科学版），2003（1）.