比赛项目的排序1

i = 1, 2,Ln; j = 1, 2,Lm 矩阵 Aij 见附录 1
第二步：设题目中给出的报名表转化而成的 0-1 矩阵为初始矩阵，计算 M 用关联度来表示运动
员连续参加比赛的程度，初始关联度为 0。若 Ai, j 与 Ai, j+1 （i=1，2，……，40，j=1，2，……13）
都是 1，即运动员 i 连续 j 和 j+1 项比赛项目，则关联度加 1。通过计算机循环程序，将关联度累加， 最终算出 M=18。
同穷举法的结果是一致的，这说明穷举法用于解决小型比赛排序问题是可行的。 5.2 大型比赛项目排序表
5.2.1 多轨搜索模型的算法 该运动比赛共有 61 个比赛项目，1050 人参加比赛，当用上述穷举法时，我们发现计算机无法
项目和参赛人数都用参数来表示，很容易得到解决此类问题的一般性算法。
关键词 多轨搜索模型 单向最小路径的 Hamilton 通路 改良 Hamilton 圈法 元素判别值法
穷举法
文章号 TS200603007
一．问题重述（略） 二．模型的假设
1．不考虑赛程前后顺序安排对各参赛者实力的影响。 2．不考虑两场比赛间时间间隔的差别。 3．每队都能按时参加比赛，不考虑天气，场地，队员受伤等因素对赛程的影响。 4．认为每场比赛持续时间的长短对运动员的体力恢复均无影响。 5．近似认为每个运动员的体力恢复、水平发挥能力无明显差别。
B2 → B6 → B3 → B7 → B11 → B5 → B1 → B8 → B9 → B4 → B13 → B10 → B12 → B14
B9 → B4 → B13 → B10 → B12 → B14 → B2 → B6 → B3 → B7 → B11 → B5 → B1 → B8
90
《数模探索》
的 Hamilton 圈。利用 Matlab 编写 Hamilton 最优通路程序，修改 C 以得到具有较小权的另一个
88
《数模探索》
比赛项目的排序
2006 年第一期(总第 5 期)
Hamilton 圈即为改良圈算法，从而得解。值得一提的是 Hamilton 圈，我们采用的方法比 C 语言更 为精练，所花费的时间大为减少，是一种使用方便又效率极高的方法。
三．符号说明 Ai, j ：第 i 个运动员在第 j 个比赛项目的参赛项目， i=1,2……40，j=1，2……14
M：初始分配方案的关联度。
Bj,k ：第 j 个比赛项目和第 k 个比赛项目之间的关联度，j=1，2，……，13，k=j+1，……，14
B j ：第 j 个比赛项目,j=1，2，……，14
联度要加上+，最后得到的 0-1 阵的新关联度为:
M’=M- B13,14 + B1.14
② B1,4 插在 Bj 和 Bj+1 （j=1，2，……12）之间。关联度 M 首先也变为 M- B13,14 ，而 Bj 和 B1,4 ，
Bj+1 和 B1,4 从原先没有关联性变为有关联性，关联度要加上 Bj.14 和 Bj+1.14 ， Bj ， Bj+1 却因为 B14 的
变为 M’,与之相对应的矩阵 A 'i, j ,
第五步：依次改变 B1,3 , B1,2 ，……， B1 的位置，循环上述①，②两个步骤，找出所有分配方案
关联度的最小值 MS 和相应的关联度为 MS 的 0-1 矩阵。 运行结果为 N=2， 有两人连续参加比赛的方案有好许多种，下面罗列出主要的几种：
值最小的那个改良圈。这将会得到更令人满意的答案。 4.3 阐述算法的合理性
对穷举法、多轨搜索模型和单 Hamilton 通路优化方法的评价，特别是改良圈的引入，不但可 以方便地求解“最小 Hamilton 圈问题”和单向 H-通路问题，而且还能有效地求解调运、指派和货 郎担问题，解决一类旅行商（TSP）问题。 4.4 针对第二题的结果，解决问题的建议及方案。
4.1.3 目标工作——对穷举方法的改进 建立穷举法模型，通过对题意的理解，加大限制条件，减少计算机循环次数，提高计算效率。 4.1.4 模型反思——对问题的进一步思考 穷举法虽然能计算出结果，却需要占用大量的时间和内存，特别是所提供的数据较大时，显然 这种方法就不太适用。为了模型的推广，必须将问题转化为一个合适的数学模型，然后采用该模型 的相关算法对其进行运算。为此我们将运动员参赛情况变为 0-1 矩阵，建立多轨搜索模型[2]，根据 相邻两列的关联度情况变为兼项矩阵，对得到的矩阵进行数据处理，形成相邻编排项目矩阵，再对 整个矩阵求倒就获得了我们所需要的 Hamilton 图方矩阵，至此就将此 NP 问题转化为著名的旅行商 （TSP）问题[4]。接下来就是求最优 Hamilton 圈，最后将圈上权值最大的那条边去掉就是我们所要 的项目排序了。此通路即为最合理的项目安排顺序。而求最小 Hamilton 圈目前还没有求解的有效算 法，所以如何找到一个效率高、推广性好的算法寻求最优 Hamilton 圈成为我们解题的关键。 4.2 根据附件中所提供的运动比赛的报名情况，建立模型，给出算法及其框图以及合理的比赛项目 排序表。 4.2.1 问题转化： 此问题是 NP 问题，根据上题的分析我们采用与穷举法类似的多轨搜索模型，算出运动员兼项矩
举法来完成这项任务，将比赛报名表转化为一个 0-1 矩阵，通过计算机编程，选出连续参加比赛的人数最少的几种
排序方法，进而从中确定最优方案。其结果为最少 2 人次连续参赛。
问题 2．给出算法和其框图，有 61 个比赛项目，1050 人参赛的项目排序表。由于该问题涉及的数据较多，不能
用穷举法来给出排序表。其次考虑到穷举法的运算量，我们决定对问题进行分析与转化——首先将 0-1 矩阵用多轨
插 入 变 成 没 有 关 联 性 ， 关 联 度 既 而 又 要 减 去 Bj, j+1 , 最 后 得 到 的 该 0-1 阵 的 新 关 联 度 为 :
M’=M- B13,14 + B j.14 + B j+1.14 - B j, j+1
算出 B1,4 在不同位置时所产生的各个矩阵的关联度，从中选出最小的 N，若 N<M,则初始关联度
矩阵 D14×14 (ri, j )14×14 为：
di,i = d × max(di, j ) = 2×1 = 2 ;i=1，2，……，14，j=1,2，……,14
根据相邻编排项目矩阵应用单向 Hamilton 最优通路求解出最优排序方案为：
B13 → B10 → B12 → B14 → B2 → B6 → B3 → B7 → B11 → B5 → B1 → B8 → B9 → B4
列出来，从中找出最优的排序方案。而且在穷举的途中我们也可以不断发现各方案之间的规律，直 接去掉一些明显不可行的方案，从而降低穷举的数量，提高进程。而穷举的过程可以通过计算机编 程来实现。 具体的运行过程如下：
第一步：将比赛报名表转化为 0-1 矩阵，以便计算机识别。
Aij
=
⎧1 ⎨⎩ 0
第i个人参加第j个比赛项目 第i个人不参加第j个比赛项目
阵（ Rm×m ）、相邻编排系数矩阵（ Bm×m ），进而将问题转化为单向 Hamilton 最优通路[1]求解，整个
过程就是在一个赋权完全图中，找出一个有最小权的单向 Hamilton 圈。我们得出的最优圈，将圈上 权值最大的那条边去掉就是我们所要的项目排序了。
4.2.2 具体方法 采用多轨搜索模型、结合图论知识, 构成最优圈，即在一个赋权完全图中，找出一度 Bj,k （j=1，2，……，13，k=j+1，……，14）。方法如
上。 B= [0 2 1 2 0 0 1 0 1 2 1 1 1 1 20141011131021
89
《数模探索》
比赛项目的排序
2006 年第一期(总第 5 期)
11010003110221 24101121021011 01010201110112 00012012111212 11020101110221 01311210121422 11101111011131 23121112101003 11010101110311 10201224103010 12211122301104 1 1 1 1 2 2 1 2 1 3 1 0 4 0]
第四步：改变 B1,4 的位置，形成新的 0-1 矩阵，计算出该方案的关联度。
① B1,4 放在 B1 前，那么原本参加 B1,3 和 B1,4 的运动员从连续参加转变为不连续参加， B1,3 和 B1,4
之间存在的关联性消失，关联度 M 变为 M- B13,14 ，而 B1 ， B1,4 从原先没有关联性变为有关联性，关
搜索模型转化为 Hamilton 图矩阵，然后用改良圈法进行求单向最小路径的 Hamilton 通路，此通路即为最合理的项
目安排顺序。而此算法远远比穷举法的运算量小的多。其结果为最少 6 人次连续参赛。
问题 3. 给出解决“运动员连续参加比赛”问题的建议及方案。有了问题 2 的解法，我们将其普遍推广，把比赛
把项目矩阵化为 0-1 矩阵，进而构造出相邻编排项目矩阵，这样就把问题转化为 NP 完备问题。 4.1.2 具体方法
对于 NP 完全问题，至今没有一种快速简便的方法，因为此问题涉及的数据不多，则我们首先采 用穷举法，按照矩阵的各列，用关联度来表示运动员连续参加比赛的程度，记初始关联度为 0，若 运动员 i 连续参加 j 和 j+1 项比赛项目，则关联度加 1，通过关联度的数值将列安插入恰当的位置。
比赛项目的排序
2006 年第一期(总第 5 期)
B13 → B10 → B12 → B14 → B2 → B6 → B3 → B7 → B11 → B5 → B1 → B8 → B9 → B4
B13 → B10 → B12 → B14 → B2 → B6 → B3 → B7 → B11 → B5 → B1 → B8 → B4 → B9