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

kevin655

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

; X) a  z. J9 A- }足球排队系统，61个点全部走完，找出最短的hamilton道路。
& c( l' e$ r; O3 {: f有用蚁群算出结果为5的；
4 s& Q  |0 |+ m* f- v9 o* Y遗传算出结果为6的；
4 E; u2 r! w# c$ k+ b模拟退火算出6的；
1 @# l, q5 d/ ^8 Y& J还有一个是lingo中的现成模型，那本黄皮书上有，几秒中内就能得到5，加个0点组成62个点的hamilton回路来解。
5 x7 [+ V) `5 `$ A3 S
如果有人要测测算法的性能，那么这题就是个很好的数据。
, g5 v- {" j& P
  i& o. m6 ^" \最后好像基本是5的是一等，6的是二等。

# ]1 p0 i  ^5 a$ p做过这个题的,如果谁有好的思路和方法,欢迎提出..

: T; n1 x! U: `" y( t$ l[ 本帖最后由 kevin655 于 2008-10-3 13:27 编辑 ]

baochens

B题

比赛项目的排序

全民健身计划是1995年在国务院领导下，由国家体委会同有关部门、各群众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主义现代化目标相配套的社会系统工程和跨世纪的发展战略规划。现在，以全民健身为主要内容的群众性体育活动蓬勃开展，举国上下形成了全民健身的热潮，人民群众健康水平不断提高，同时也扩大了竞技体育的社会影响，提高了竞技体育水平。现在各级、各类、各种运动比赛比比皆是，这不但提高了全民的身体素质，而且使一批运动员脱颖而出，成为运动健将，为国家争得了荣誉。
在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。
8 S7 W  u$ n: Z$ r5 z* B1 }
/ d, S  [1 n) @* Y% z2 j7 x0 L1．表1是某个小型运动会的比赛报名表。有14个比赛项目，40名运动员参加比赛。表中第1行表示14个比赛项目，第1列表示40名运动员，表中“＃”号位置表示运动员参加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能的少；
  @" B2 w! A3 S! T
( z0 V) k( G( H  V, `2 g1 {2．文件“运动员报名表”中给出了某个运动比赛的报名情况。共有61个比赛项目，1050人参加比赛。请给出算法及其框图，同时给出合理的比赛项目排序表，使连续参加两项比赛的运动员人次尽可能的少；

3．说明上述算法的合理性；
' d+ ~: p' K  e
4．对“问题2”的比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方案。

( t/ g# P8 w( o3 l! r  n% ?
! d4 D! \4 t: j/ h' _
8 D! b" K1 f) {# d; L9 u

georgewon

我们都做了这题的，当成训练题做的，我很有影像，感觉做的很不错的~~~~

kevin655

这个当训练题是个很好的题

feitian2

支持呀！！！！！！！！！！！！！

xjz549

突然想起了EMCM2005 的B题

heyb223313

感谢版主！

参天大树

恩恩，我现在回去做做