查看: 4826|回复: 7

突然想起了EMCM2005 的B题足球排队 TSP问题

字体大小: 正常放大

kevin655

8 主题	3 听众	77 积分

升级 75.79%

TA的每日心情

	开心 2013-5-12 19:00

签到天数: 1 天

[LV.1]初来乍到

电梯直达

1^#

发表于 2008-10-3 12:59 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

3年前的问题，如今印象还是非常深刻，还是把它好好留在这里吧。做过这题的同学估计都已经读到研了,所以我就发这个版了

足球排队系统，61个点全部走完，找出最短的hamilton道路。
有用蚁群算出结果为5的；
遗传算出结果为6的；
模拟退火算出6的；
还有一个是lingo中的现成模型，那本黄皮书上有，几秒中内就能得到5，加个0点组成62个点的hamilton回路来解。

如果有人要测测算法的性能，那么这题就是个很好的数据。

最后好像基本是5的是一等，6的是二等。

做过这个题的,如果谁有好的思路和方法,欢迎提出..

[ 本帖最后由 kevin655 于 2008-10-3 13:27 编辑 ]

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

baochens

5 主题	3 听众	130 积分

升级 15%

TA的每日心情

	开心 2013-8-21 01:50

签到天数: 3 天

[LV.2]偶尔看看I

群组: 数学趣味、游戏、IQ等

2^#

发表于 2008-10-3 13:11 |只看该作者 |招呼Ta 关注Ta

没参加过，把题目搜到了，放到这里，方便后来人阅读

B题

比赛项目的排序

全民健身计划是1995年在国务院领导下，由国家体委会同有关部门、各群众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主义现代化目标相配套的社会系统工程和跨世纪的发展战略规划。现在，以全民健身为主要内容的群众性体育活动蓬勃开展，举国上下形成了全民健身的热潮，人民群众健康水平不断提高，同时也扩大了竞技体育的社会影响，提高了竞技体育水平。现在各级、各类、各种运动比赛比比皆是，这不但提高了全民的身体素质，而且使一批运动员脱颖而出，成为运动健将，为国家争得了荣誉。
在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。

1．表1是某个小型运动会的比赛报名表。有14个比赛项目，40名运动员参加比赛。表中第1行表示14个比赛项目，第1列表示40名运动员，表中“＃”号位置表示运动员参加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能的少；

2．文件“运动员报名表”中给出了某个运动比赛的报名情况。共有61个比赛项目，1050人参加比赛。请给出算法及其框图，同时给出合理的比赛项目排序表，使连续参加两项比赛的运动员人次尽可能的少；

3．说明上述算法的合理性；

4．对“问题2”的比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方案。