|
|||||
|
|
| 运动项目排序中的优化算法 | |
| 引用本文： | 赵振鹏,姚贵平,王鑫,孟亚.运动项目排序中的优化算法[J].内蒙古农业大学学报(自然科学版),2006,27(3):124-128. |
| 作者姓名： | 赵振鹏 姚贵平 王鑫 孟亚 |
| 作者单位： | 1. 北京理工大学计算机科学技术学院,北京,100081 2. 内蒙古农业大学,理学院,呼和浩特,010018 3. 北京理工大学理学院,北京,100081 |
| 摘 要： | 本文巧妙得将运动员参赛项目的排序问题转化为图论中经典的旅行商问题求解。以连续参加两项比赛的人次最少为目标,应用了最小生成树求解Ham ilton回路的方法,得到了题目的最优解。之后,经过严谨的分析,我们又增加了1个使连续比赛的事件尽量分散开的约束条件,即保证任何1位运动员至多出现1次连续比赛的情况的条件下,求得总连续比赛人次数最少的排序方案。这样得到结果就加强了比赛项目排序结果对每位运动员的公平性、合理性。改进后的约束模型,要求我们从一些近似最优解的结果中再挑选满足约束的最终解。针对这种算法,我们采取了解决这种问题更有效的遗传算法计算。两种算法各有利弊,得到的结果与理论分析保持一致。 |
| 关 键 词： | Hamilton回路 最小生成树法 遗传算法 |
| 文章编号： | 1009-3575(2006)03-0124-05 |
| 收稿时间： | 2006-05-11 |
| 修稿时间： | 2006年5月11日 |
OPTIMIZATION ALQORITHM IN SORTING SPORT ITEMS |
|
| ZHAO Zheng-peng,YAO Gui-ping,WANG Xin,MENG Ya.OPTIMIZATION ALQORITHM IN SORTING SPORT ITEMS[J].Journal of Inner Mongolia Agricultural University(Natural Science Edition),2006,27(3):124-128. | |
| Authors: | ZHAO Zheng-peng YAO Gui-ping WANG Xin MENG Ya |
| Institution: | College of Computer Science and Technology, Beijing University of Sciences and Technology, Beijing 100081, China; 2. College of Sciences,lnner Mongolia Agricultural University,Huhhot 010018,China; 3. College of Sciences ,Beijing University of Sciences and Technology,Beijing 100081, China |
| Abstract: | The problem about the taxis of the competition items in sports games was transformed into the Traveling Salesman Problem in classic graph theory.In order to get the minimum times of taking part in two competitions without any interval, the minimal spanning tree algorithm to figure out a Hamilton cycle was used.In this way the Optimized answer was got.And then,after precise analysis, a new limit to separate the affairs of taking part in two competitions uninterrupted was paid attention to get the minimum times of taking part in two competitions uninterrupted with the restrict that a athlete can only participate in one competition.After these treatments,the answer was more just and reasonable.After the promting the model,a relatively optimum answer among the approximate answers should be selected.Dealing with the later algorithm,the genetic algorithm was more efficiency.In conclusion,the two algorithms are as potent as each other,and the two answers are identical with the theoretic analyses. |
| Keywords: | Hamilton cycle minimal spanning tree genetic algorithm(GA) |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |