比赛项目的排序
齐汇，陈艳，赵伸极
（浙江师范大学，浙江金华，321004）
摘要 本文根据某个运动比赛的报名情况，合理安排比赛项目顺序，使连续参加两项比赛的运动员人数尽可能的少，
以便运动员恢复体力，发挥正常水平。
问题1．合理安排某个小型运动会（14个比赛项目，40个运动员参加比赛）比赛项目的报名顺序。我们采用穷举法来完成这项任务，将比赛报名表转化为一个0-1矩阵，通过计算机编程，选出连续参加比赛的人数最少的几种排序方法，进而从中确定最优方案。其结果为最少2人次连续参赛。
问题2．给出算法和其框图，有61个比赛项目，1050人参赛的项目排序表。由于该问题涉及的数据较多，不能用穷举法来给出排序表。其次考虑到穷举法的运算量，我们决定对问题进行分析与转化——首先将0-1矩阵用多轨搜索模型转化为Hamilton 图矩阵，然后用改良圈法进行求单向最小路径的Hamilton 通路，此通路即为最合理的项目安排顺序。而此算法远远比穷举法的运算量小的多。其结果为最少6人次连续参赛。
问题3. 给出解决“运动员连续参加比赛”问题的建议及方案。有了问题2的解法，我们将其普遍推广，把比赛项目和参赛人数都用参数来表示，很容易得到解决此类问题的一般性算法。
关键词 多轨搜索模型 单向最小路径的Hamilton 通路 改良Hamilton 圈法 元素判别值法 穷举法 文章号 TS200603007
一．问题重述（略） 二．模型的假设
1．不考虑赛程前后顺序安排对各参赛者实力的影响。 2．不考虑两场比赛间时间间隔的差别。
3．每队都能按时参加比赛，不考虑天气，场地，队员受伤等因素对赛程的影响。 4．认为每场比赛持续时间的长短对运动员的体力恢复均无影响。 5．近似认为每个运动员的体力恢复、水平发挥能力无明显差别。
三．符号说明
2……14 A i , j ：第i 个运动员在第j 个比赛项目的参赛项目，i=1,2……40，j=1，
M：初始分配方案的关联度。
B j , k ：第j 个比赛项目和第k 个比赛项目之间的关联度，j=1，2，……，13，k=j+1，……，14
B j ：第j 个比赛项目,j=1，2，……，14
MS：所有分配方案关联度的最小值。
d i ×j ：第i 项与第j 项可能相邻编排系数，i，j=1，2，……，m
R m ×m ：运动员兼项矩阵。 TX i , j ：元素判别值。 ZX i , j ：元素总检验数。
四．问题分析
4.1 建立模型，合理排序使得连续参加两项比赛的运动员人次尽可能地少。
4.1.1问题转化
问题要求我们建立一个合理模型，使得连续参加两项比赛的运动员人次尽可能地少。首先我们把项目矩阵化为0-1矩阵，进而构造出相邻编排项目矩阵，这样就把问题转化为NP 完备问题。
4.1.2 具体方法
对于NP 完全问题，至今没有一种快速简便的方法，因为此问题涉及的数据不多，则我们首先采用穷举法，按照矩阵的各列，用关联度来表示运动员连续参加比赛的程度，记初始关联度为0，若运动员i 连续参加j 和j+1项比赛项目，则关联度加1，通过关联度的数值将列安插入恰当的位置。
4.1.3 目标工作——对穷举方法的改进
建立穷举法模型，通过对题意的理解，加大限制条件，减少计算机循环次数，提高计算效率。 4.1.4模型反思——对问题的进一步思考
穷举法虽然能计算出结果，却需要占用大量的时间和内存，特别是所提供的数据较大时，显然这种方法就不太适用。为了模型的推广，必须将问题转化为一个合适的数学模型，然后采用该模型的相关算法对其进行运算。为此我们将运动员参赛情况变为0-1矩阵，建立多轨搜索模型，根据相邻两列的关联度情况变为兼项矩阵，对得到的矩阵进行数据处理，形成相邻编排项目矩阵，再对整个矩阵求倒就获得了我们所需要的Hamilton 图方矩阵，至此就将此NP 问题转化为著名的旅行商（TSP）问题。接下来就是求最优Hamilton 圈，最后将圈上权值最大的那条边去掉就是我们所要的项目排序了。此通路即为最合理的项目安排顺序。而求最小Hamilton 圈目前还没有求解的有效算法，所以如何找到一个效率高、推广性好的算法寻求最优Hamilton 圈成为我们解题的关键。 4.2 根据附件中所提供的运动比赛的报名情况，建立模型，给出算法及其框图以及合理的比赛项目排序表。
4.2.1问题转化：
此问题是NP 问题，根据上题的分析我们采用与穷举法类似的多轨搜索模型，算出运动员兼项矩阵（R m ×m ）、相邻编排系数矩阵（B m ×m ），进而将问题转化为单向Hamilton 最优通路求解，整个
[1]
[4]
[2]
过程就是在一个赋权完全图中，找出一个有最小权的单向Hamilton 圈。我们得出的最优圈，将圈上权值最大的那条边去掉就是我们所要的项目排序了。
4.2.2 具体方法
采用多轨搜索模型、结合图论知识, 构成最优圈，即在一个赋权完全图中，找出一个有最小权的Hamilton 圈。利用Matlab 编写Hamilton 最优通路程序，修改C 以得到具有较小权的另一个
Hamilton 圈即为改良圈算法，从而得解。值得一提的是Hamilton 圈，我们采用的方法比C 语言更为精练，所花费的时间大为减少，是一种使用方便又效率极高的方法。 4.2.3 目标工作——对Hamilton 最优通路图的改进
查阅了相关资料我们了解到，目前还没有求解旅行商问题的有效算法。修改单Hamilton 图以得到具有较小权的另一个Hamilton 圈即为改良圈算法，其具体改良算法我们将在模型的建立中阐述。
4.2.4模型反思——对问题的深入思考
对Hamilton 改良圈的进一步深刻理解。我们将Hamilton 改良圈的初始圈进行了遍历，取出权值最小的那个改良圈。这将会得到更令人满意的答案。 4.3 阐述算法的合理性
对穷举法、多轨搜索模型和单Hamilton 通路优化方法的评价，特别是改良圈的引入，不但可以方便地求解“最小Hamilton 圈问题”和单向H-通路问题，而且还能有效地求解调运、指派和货郎担问题，解决一类旅行商（TSP）问题。 4.4 针对第二题的结果，解决问题的建议及方案。
对于“运动员连续参加比赛”这个问题是运动会编排比赛秩序一个重要的考虑因素，为了体现比赛的公平性，要尽量错开连续比赛的人次，在结果的分析中我们会给出可行的建议和具体的方案。
五．模型建立
5.1 小型运动会比赛项目的排序 5.1.1 穷举法的原理说明
小型运动会的比赛项目少，参加的运动员也不多，因此可以采用一般的穷举法，将各种情况罗列出来，从中找出最优的排序方案。而且在穷举的途中我们也可以不断发现各方案之间的规律，直接去掉一些明显不可行的方案，从而降低穷举的数量，提高进程。而穷举的过程可以通过计算机编程来实现。
具体的运行过程如下：
第一步：将比赛报名表转化为0-1矩阵，以便计算机识别。
⎧1第i个人参加第j个比赛项目 A ij =⎨ i =1, 2, L n ; j =1, 2, L m 矩阵A ij 见附录1
0第i个人不参加第j个比赛项目⎩
第二步：设题目中给出的报名表转化而成的0-1矩阵为初始矩阵，计算M 用关联度来表示运动员连续参加比赛的程度，初始关联度为0。若A i , j 与A i , j +1（i=1，2，……，40，j=1，2，……13）都是1，即运动员i 连续j 和j+1项比赛项目，则关联度加1。通过计算机循环程序，将关联度累加，最终算出M=18。
第三步：算出各比赛项目之间的关联度B j , k （j=1，2，……，13，k=j+1，……，14）。方法如上。 B= [0 2 1 2 0 0 1 0 1 2 1 1 1 1 2 0 1 4 1 0 1 1 1 3 1 0 2 1
1 1 0 1 0 0 0 3 1 1 0 2 2 1 2 4 1 0 1 1 2 1 0 2 1 0 1 1 0 1 0 1 0 2 0 1 1 1 0 1 1 2 0 0 0 1 2 0 1 2 1 1 1 2 1 2 1 1 0 2 0 1 0 1 1 1 0 2 2 1 0 1 3 1 1 2 1 0 1 2 1 4 2 2 1 1 1 0 1 1 1 1 0 1 1 1 3 1 2 3 1 2 1 1 1 2 1 0 1 0 0 3 1 1 0 1 0 1 0 1 1 1 0 3 1 1 1 0 2 0 1 2 2 4 1 0 3 0 1 0 1 2 2 1 1 1 2 2 3 0 1 1 0 4 1 1 1 1 2 2 1 2 1 3 1 0 4 0]
第四步：改变B 1,4的位置，形成新的0-1矩阵，计算出该方案的关联度。
①B 1,4放在B 1前，那么原本参加B 1,3和B 1,4的运动员从连续参加转变为不连续参加，B 1,3和B 1,4
之间存在的关联性消失，关联度M 变为M-B 13,14，而B 1，B 1,4从原先没有关联性变为有关联性，关联度要加上+，最后得到的0-1阵的新关联度为: M’=M-B 13,14+B 1.14
②B 1,4插在B j 和B j +1（j=1，2，……12）之间。关联度M 首先也变为M-B 13,14，而B j 和B 1,4，
B j +1和B 1,4从原先没有关联性变为有关联性，关联度要加上B j .14和B j +1.14，B j ，B j +1却因为B 14的
插入变成没有关联性，关联度既而又要减去B j , j +1, 最后得到的该0-1阵的新关联度为: M’=M-B 13,14+B j .14+B j +1.14-B j , j +1
算出B 1,4在不同位置时所产生的各个矩阵的关联度，从中选出最小的N，若N
第五步：依次改变B 1,3, B 1,2，……，B 1的位置，循环上述①，②两个步骤，找出所有分配方案关联度的最小值MS 和相应的关联度为MS 的0-1矩阵。
运行结果为N=2， 有两人连续参加比赛的方案有好许多种，下面罗列出主要的几种：
B 2→B 6→B 3→B 7→B 11→B 5→B 1→B 8→B 9→B 4→B 13→B 10→B 12→B 14 B 9→B 4→B 13→B 10→B 12→B 14→B 2→B 6→B 3→B 7→B 11→B 5→B 1→B 8
B 13→B 10→B 12→B 14→B 2→B 6→B 3→B 7→B 11→B 5→B 1→B 8→B 9→B 4 B 13→B 10→B 12→B 14→B 2→B 6→B 3→B 7→B 11→B 5→B 1→B 8→B 4→B 9
第六步：将最后确定的0-1矩阵重新转化为比赛报名表，从中选出最优的安排顺序。（以运动员参加的比赛项目之间的间隔最大为最优）。
B 13→B 10→B 12→B 14→B 2→B 6→B 3→B 7→B 11→B 5→B 1→B 8→B 9→B 4
5.1.3 穷举法模型的检验
我们用多轨搜索模型（具体的算法在5.2中给出）来检验穷举法的运算结果。可能相邻编排项目矩阵D 14×14(r i , j ) 14×14为：
d i , i =d ×max(d i , j ) =2×1=2;i=1，2，……，14，j=1,2，……,14
根据相邻编排项目矩阵应用单向Hamilton 最优通路求解出最优排序方案为：
B 13→B 10→B 12→B 14→B 2→B 6→B 3→B 7→B 11→B 5→B 1→B 8→B 9→B 4
同穷举法的结果是一致的，这说明穷举法用于解决小型比赛排序问题是可行的。 5.2 大型比赛项目排序表 5.2.1 多轨搜索模型的算法
该运动比赛共有61个比赛项目，1050人参加比赛，当用上述穷举法时，我们发现计算机无法处理如此大的数据量。因此我们找到了一种含有穷举法原理，但操作比较简单，更具有科学性，适用于处理大量数据的模型——多轨搜索模型来完成排序工作。
多轨搜索模型的算法如下：
第一步：建立运动员参加比赛项目的数据矩阵,记
⎧1X ij =⎨
⎩0
表示第i个运动员参加第j项的比赛，
i =1, 2, L , n ; j =1, 2, L , m
表示第i个运动员不参加第j项的比赛，
l
k
若某运动员参加了第l 项和第k 项的比赛则有y i =(0,L ,1,0, L 1,0L ) , i=1,2,…,n，则所有运动员参加比赛的报名情况可以建立矩阵
⎛X 1,1X 1,2⎜
X 2,1X 2,2
Y m ×m =⎜
⎜M M ⎜⎜X X ⎝m ,1m ,2
第二步：建立运动员兼项矩阵R m ×n
L X 1, m ⎞
⎟
L X 2, m ⎟
L M ⎟
⎟
L X m , m ⎟⎠m ×m
R m ×m =R (r i , j ) =Y Y ，其中r i , j =∑X i , k X k , j （i，j=1，2，……，m）
k =1
'
n
第三步：建立可能相邻编排项目矩阵D m ×m d =1−i ×j
=(d i , j ) m ×m
X X X +X
i , k
k , j
i , k
=1−
k , j
r i , j
为第i 项与第j 项可能相邻编排系数。（i，j=1，2，……，m）
X
i , k
+X k , j
D m ×m 刻划了比赛项目的依赖关系,若d i ×j 大,则说明第i 项和第j 项之间运动员兼项比例越少,则在编排中d i ×j 大的两个项目可按排在相邻和相同的时间内进行,为编排工作提供了数量依据。
第四步：转化为Hamilton 图矩阵
⎛1
对B m ×m 的每一项进行倒数操作，B =⎜⎜b
⎝i ×j
' ⎞⎟⎟ ⎠m ×m
这样就得出每个项目之间的权重，也就构成了Hamilton 图矩阵
此时我们的问题就是求单向最优Hamilton 通路，而求单项最优Hamilton 通路又可以转化为最小权的Hamilton 圈的问题，即我们只要将断开两个项目关联度最小的那个边就是单向最优Hamilton 通路了。
5.2.3 单向Hamilton 最优通路的求解新方法及其算法设计 当我们建立了可能相邻编排项目矩阵D m ×m
=(d i , j ) m ×m 后，就要根据可能相邻编排系数对比赛
项目进行合理排序，使连续参加两项比赛的运动员人次尽可能的少；在寻找最优方案过程中，我们发现可以把项目的排列顺序近似看成是求单向Hamilton 最优通路的问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton 圈，称这种圈为最优圈。我们通过元素判别值分配法，求解最小H-圈和最小权的Hamilton 通路。
首先提出用元素判别值分配法的几点原则： 原则1：判别值越大,其分配的优先级越高。
原则2：当对某元素X i , j 进行分配或选上后，则将该元素置为X i , j =1。我们可将它的对应元素置为“×”(不允许出现X i , j −X i , j 回路)，将该元素所有的i 行及j 列标上记号“√”。
原则3：若有多个元素的判别值相同,则元素总检验数小的先分配，如果元素总检验数也相同，则耗费小的优先，再按下标的顺序进行分配。
原则4：当某行或某列已经具有标记“√”或某元素已置“×”时，那么处于该行或该列的元素，及已置为“×”的元素，不论判别值多大,皆已失去分配权。
单向-通路求解的过程如下： 第一步：给d i , i 赋值
因为排序问题因不允许从B i 到B i ，故要使d i , i 具有足够大的正数，即
d i , i =d ×max(d i , j ) ;i=1，2，……，m，j=1,2，……,m
在求解程序的计算元素判别值部分按r=2计算。这样取值既可以使对角线上的元素具有足够大的正数, 又不会使求解中使用的矩形回路检验数总和的数值太大. 取d=2，
d i , i =d ×max(d i , j ) =2×1=2。
第二步：根据元素判别值的数学模型计算各个元素的判别值TX i , j
(m −1) ×(m −1)
TX i , j =
∑
s =1
f s (ΔX i , j ) =∑∑f s (d i , j −d i , j +k +d i +l , j +k −d i +l , j )
i =1j =1
m −1m −1
其中1−i ≤l ≤m −i 且l ≠0, 1−j ≤k ≤m −j 1-j k ≠0；
ΔX i , j =d i , j −d i , j +k +d i +l , j +k −d i +l , j 称为元素X 在此距形回路的检验数.并有：
ΔX i , j
f (ΔX i , j ) =⎨
0Δ≥X 0⎩i , j
依据上述定义，该模型含有m ×m 个元素.每个元素以它为顶点的矩形回路共有(m-1)×(m-1)个。因而其判别值为
TX i , j ∈[0,(m −1)(m −1)]
第三步：计算各个元素的总检验数ZX i , j
ZX i , j =∑ΔX i , j =∑∑(d i , j −d i , j +k +d i +l , j +k −d i +l , j )
i =1j =1
m −1m −1
其中1−i ≤l ≤m −i 且l ≠0, 1−j ≤k ≤m −j ,1-j k ≠0； 第四步：调配和求解
(1)选尚未调配的元素中,元素判别值最大（其它参考值依次为总检验数最小、下标顺序在前）的元素,如为X i , j 给X j , i 标上得到调配的顺序号K(从1开始,直到m),对其相应的对称元素X j , i 记上“×”，并对第i 行及第j 列记上“√”。
(2)检查表上所有行和列是否皆已标上“√”标志.如果尚有未作标志“√”的行或列（有行必有列,反之也一样），则执行(1),否则执行(3)。
(3) 给出最优排序的Hamilton 通路。 5.2.4 单向Hamilton 通路的改进
我们希望有一个方法以获得相当好（但不一定最优）的解。求Hamilton 圈的方法很多，但从算法效率方面考虑我们求Hamilton 圈用的是改良圈算法。
对Hamilton 圈适当修改，以得到具有较小权的另一个Hamilton 圈，使结果更加精确，修改的方法叫做改良圈算法。
第一步：设初始圈C
=B 1B 2L B m B 1
第二步：对于m，构造新的Hamilton 圈：
C ij =B 1B 2L B i B j B j −1B j −2L B i +1B j +1B j +2L B m B 1,
它是由C 中删去边
B i B i +1
和
B j B j +1
，添加边
B i B j
和
B i +1B j +1
而得到的。若
w (B i B j ) +w (B i +1B j +1)
第二步：重复第一步，直至无法改进，停止。
用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，我们将结果进行进一步优化。即将所有可能的初始圈进行遍历，然后再对所得结果取路径值最小的那个圈。即为我们的最优项目排序了。
5.3 解决“运动员连续参加比赛”问题的建议及方案
随着5.2问题的解决，多轨搜索模型和单向Hamilton 最优通路模型就可以作为“运动员连续参加比赛”问题的方案。 5.3.1 多轨搜索模型
多轨搜索模型可以普遍解决“运动员连续参加比赛”问题,其算法和框图在5.2中已经详细给出,只要改变运动员参加比赛项目数据矩阵的行数和列数,此后步骤中的兼项矩阵和相邻编排项目矩阵的行列数也做相应改变即可。 5.3.2 单向Hamilton 最优通路
运动员连续参加比赛的项目排序问题是NP-完备问题，所以将它转化为求项目图的最小Hamilton 圈。即类似货郎担问题、邮递员问题、骑士巡游问题等等。而求最小Hamilton 圈目前还没有有效算法，我们查相关资料求最小Hamilton 圈有穷举法、改良圈法、元素判别值分配法、IS法（冲突图的着色问题）等方法。其中有些方法是改进的算法，比如改良圈法、元素判别值分配法、IS 法。而穷举法是求最小Hamilton 圈的一般方法，规模小的话还可以进行，但对于规模大的其运算量太大而无法进行。本文采用的是一种比较有效的算法——改良圈法。它的运算量比穷举法小的多。改良算法运算量O(m*(m+1)/2)
六．模型结果
6.1 14个比赛项目，40个运动员参加的小型运动会的比赛项目排序表
B 13→B 10→B 12→B 14→B 2→B 6→B 3→B 7→B 11→B 5→B 1→B 8→B 9→B 4
给出的比赛项目的顺序安排，有2人次连续参加比赛
6.2 61个比赛项目，1050个运动员参加的运动会的比赛项目排序表 由于数据太大，我们只给出排列顺序：
B 20→B 6→B 15→B 33→B 47→B 55→B 5→B 36→B 45→B 7→B 42→B 52→B 50→B 3→B 10→B 21→B 12→B 31→B 39→B 13→B 32→B 56→B 11→B 54→B 43→B 38→B 49→B 26→B 27→B 29→B 24→B 51→B 16→B 57→B 53→B 25→B 4→B 44→B 2→B 61→B 58→B 30→B 37→B 22→B 17→B 28→B 59→B 8→B 60→B 19→B 1→B 41→B 14→B 23→B 34→B 48→B 40→B 18→B 9→B 35→B 46
其中有6人次连续参加比赛。 6.3多轨搜索模型的合理性分析
穷举法充分利用电子计算机高速计算的特点，首先把排序问题转化为0—1矩阵，以关联度最小为目标，计算出所有可能方案，并从中选取最合理的方案。该方法优点是输出信息全面，可从中选择几个合理的方案，能看到在改变项目顺序时，安排合理性的变化趋势，便于我们根据规律，设定约束条件，自动删除一些明显不合理的方案，简化程序。穷举法思路清晰、简单、便于理解、实用性强，不必要求掌握更多的优化技术，适于现场技术人员使用，在我国体育事业蓬勃发展的新形势下，对运动员的编制有一定的实际意义。
多轨搜索模型主要应用于竞赛项目顺序的编排工作与穷举法有类似的数学理念，有较强的科学性,特别用计算机实现快捷准确。多轨搜索模型构造出了相邻系数矩阵，借助该系数矩阵来刻画比赛项目之间的依赖关系，系数大则说明项目间的兼项比例越少，就此可以进行项目的排序。我们可以把得到的相邻系数矩阵转化为一个赋权完全图，进而用单向Hamilton 最优通路解决排序问题，同H-圈问题一样,目前尚无一种有效求解方法，但使用元素判别值分配法求解单向H-通路问题,仅一次调配便可获得最优的单向H-通路,无须调整。该方法具有明显的优越性：
(1)元素判别值的数学模型简单,计算方便。 (2)分配原则简便。
(3)一次分配可获最优方案。这是现行方法所无法实现的。 (4)具有一定的通用性。
此算法不但可以方便地求解单向H-通路问题,并且可用于求解“最小Hamilton 圈问题”，而且还能有效地求解调运、指派和货郎担问题，同时可以一次调解得到最优解,无须作任何进一步的调整，这也是当前所有可行的方法所不能达到的功能。利用图论的知识我们需要在一个赋权完全图中，找出一个有最小权的Hamilton 圈，但这种方法是极其烦琐的，因此一个可行的办法是首先求一个Hamilton 圈C ，然后适当修改C 以得到具有较小权的另一个Hamilton 圈，即改良圈。通过初始圈的选定来求最优解，此外，算法的优劣程度有时也能用Kruskal 算法加以说明和检验。值得一提的是该算法在计算机上操作时，即使像问题2中如此大的数据也可以很快的运行出来。
八．模型的评价
（1） 穷举法思路清晰、简单、便于理解、实用性强，不必要求掌握更多的优化技术，适于现场技
术人员使用。
（2） 在穷举法的基础上给出了原理类似的多轨搜索模型，使模型有较强的科学性和理论依据，特
别用微机实现具有快捷准确的特点。
（3） 对于实际问题我们还可以根据实际情况分析对象的内在特性与各因数间的机理。而本文章只
对数据的自身的特性上进行分析，这样使得求解过程具有片面性。
（4） 我们将对Hamilton 圈适当修改为改良圈，并把圈修改过程变为一次替换三条边，使结果更加
精确。
(5) 用元素判别值分配法求解最小H-圈最小权的Hamilton 通路问题，它只需一次分配便可获最优，无须调整，是一个有效的求解方法,且具有一定的通用性。不但可以方便地求解单向H-通路问题,并且可用于求解“最小Hamilton 圈问题”，而且方法还能有效地求解调运、指派和货郎担问题。用元素判别值分配法在处理较少的数据,即使不使用计算机，用人工表上操作也十分方便。 (6) 我们查资料知元素判别值法的数学模型具有一定的通用性.不但可以方便地求解单向H-通路问题,并且可用于求解“最小Hamilton 圈问题”，进而此方法还能有效地求解调运、指派和货郎担问题等NP 难题。将所求得的最小Hamilton 圈进行改良，可以使结果更加精确。
九．模型的推广
目前，我国的田径比赛越来越多，而且受到了全国人民的广泛关注。田径比赛中竞赛分组和竞赛日程的编排是否合理,直接影响比赛能否顺利进行和运动员竞技水平的发挥,是比赛组织工作的一个重要环节。目前田径比赛的编排工作多是由一批有经验的人员参加,依据竞赛规程和规则在一定时间内完成。由于编排工作需要处理几十个参赛单位和上千名运动员以及几十个比赛项目,不但工量巨大,而且难免出砒漏。本文研制的数学模型可以较好的解决此类问题，使比赛公平、合理的举行，每个运动员都受到公平的待遇，提高他们的积极性。同时，该模型也可以广泛应用于许多领域，许多项目（NP问题）的编排上。目前正逐步在大中小学和工矿企事业单位推广使用,带来了很好的经济和社会效益。
改良的Hamilton 圈可以很好的解决旅行商（TSP）问题，即一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）。
单向Hamilton 最优通路的求解法对各种排序问题的解决提供帮助，如科学安排零件加工顺序,使调整机器的总时间最少，以提高工作效率,而且还能有效地求解调运、指派和货郎担问题。
参考文献
[1] 张银明，单向Hamilton 最优通路的求解新方法及其算法设计，华侨大学学报，第24卷，第3期：314-320，2003.7。 [2] 佟毅，田径竞赛编排中的两个数学模型，数理统计与管理，第17卷，第4期：1-3、15，1998.7。 [3] 李良刚，杨莉，非直接对抗性项目竞赛日程编排方法的研究，四川体育科学，第3期：40-42，2001.9。
《数模探索》 比赛项目的排序 2006年第一期(总第5期)
[4] http://www.sdau.edu.cn/xinxi/sxjm/jiaocheng/jiaocheng/51.doc，2005年11月28日。
[评语]该论文首先针对小型运动会的比赛项目的排序问题给出了穷举法，从中确定最优化，思路清晰，算法简单。对大型运动会比赛项目的排序问题运用多轨搜索模型，将问题转化成TSP 问题，用改良圈法来求单向最小路径的Hamiltion 通路，并用Matlab 编写了较为精练的程序，降低了运算量并尝试用元素判别值法对所求的最小Hamilton 圈进行改良，优化结果。全文图文并貌，使论文更具说服力.
97 （定稿老师：张莹）