数学建模社区-数学中国

标题: 08GMCM比赛感言 [打印本页]

---

作者: baochens    时间: 2008-10-2 19:25
标题: 08GMCM比赛感言
我们做的是C题，理解这个题目花了一天多的时间（汗 ，自认为我们组的理解水平还可以，这个题目对于很多非专业的人很难理解详细，很多地方没有描述清楚，这是这个题目出的最败笔的地方，总体来说题目还不错）。然后我们从数学中国提供的论文中找到了三篇与题目较相近的论文，按照他们的思路整出模型一来（整数规划），我们觉得该模型不具有新意而且获奖概率太小（毕竟看这些参考资料的人太多），遂决定另辟一思路。在第三天早上，另一模型提出，与队友商量后定砣。模型的思想如下：首先讲中时最小的目标进行转化，转化为从编组场进入出发场车辆最多，再进一步转化为在尽量让车辆在所有限制下（重量、中时、长度）使得最多列（注意是列不是辆）车驶出。这样，建立一个分层规划模型（第一层目标是尽量满轴），第二层是最多辆车驶出。模型虽然初步完成，可是这个模型的求解也没有任何套路可以套用。然后我们设计了分方向剪枝搜索算法进行求解。首先解释下什么是分方向，假设每列车的车辆都是按照方向上的一个特定顺序的（如，都是按照按照东西南北方向来的），鉴于四个方向的相对独立性，我们按每个方向单独处理，这对于NPC问题来说，大大减少了数据量（试想一下，一个数据量70的TSP和70/4的TSP问题的对比）。至于剪枝，我想大家都知道是啥意思，我们算法在运行的过程中做如下剪枝处理：
1.如果编组场中有尾数与当前要放入编组场的车辆组编号相同的，直接放在该列后面。（解释一下什么是位数：我们用站名（共29个）命名车辆组，位数即该列最靠后的车辆组的编号）
. T0 m- P, y+ x2 [6 i% P: ?& w2.如果没有相同的，放在尾数比它编号小的后面或者另辟新列
3.当状态树达到一定数据量时（比如10000）我们采用评估函数进行进一步剪枝，该评估函数为按照经验得到的，故选择在该评估函数评估的最优的一部分（例如：500或者1000），以保证尽量最优（因为评估函数是根据经验获得的，这个我们在后面提到了，可以通过机器学习策略进行改进）。
% i0 g8 ^! K, t1 `8 Y    通过上面的剪枝策略可以保证状态保持在一定范围内，利于处理大规模数据，当某状态中某列车达到三个限制条件之一就表示该列车要驶出了，如果确实驶出该列车，则以后的处理以该状态为树根继续运行算法（因为有的状态当前可以驶出一列，可能其他状态一小段时间后会有多列驶出，使得其更优，故我们不是立即确定哪个状态优，而是一直等到处理完当前已知数据后而决定）。
    对于第一问，相当于将算法首先执行到一定深度（即把所有达到场的车辆先利用分方向剪枝搜索算法进行处理），然后选择最优进行编组。
    对于第二问，对这些数据进行特殊处理，不按照上面的三个约束来，在优先处理他们的同时，具体处理方案如下：发往S1和军用的车辆组在编组时放在所有可能性中列车长度最长的后面，然后立马出发；对于发往一个方向的救灾车，直接由转发场进入出发场出发；对于发往两个方向的救灾车按照和S1的车一个处理办法。这样处理的理由是：因为这些车辆都是急用的，对它们来说，时间是最关键的，我们这样处理使得时间最短。
    对于第三问：相当于让我们的算法运行的深度增加了，可以用上面的算法稍加改动直接处理。
7 |3 i( b$ V/ _; i    对于第四问：将目的地为S3以南的站点的编号（即：s1、s2以远、s3以西及以远）转化为E4以南，然后利用上面的算法进行处理。
1 J) n, G* z6 \% e  ^, r5 y! u    对于第五问：经过分析后我们发现解体速度是影响编组效率的最根本因素（因为按照我们的编组方案，最多只用29列编组场的轨道，这是因为没有任何两列的尾数是相同的），在任何编组时到达场都停满车时编组效率最高（因为算法运行深度最大，结果相对最优），故得到最多编组辆数。由于题目中没有满足我们要求的数据，我们把题目中的数据进行如下处理：将所有列车的时间间隔改为10分钟（通过一些假设和近似我们把解体一列车时间看成10分钟），且当前时刻在到达场中已有12列车，这12列车也是间隔10分钟来的，最近来的是5：50。
' L, P) j; [" p! s: e   对于第六问：1.鉴于我们在处理的时候都是按照列车到达先后进行处理的（即先到先服务原则），而这种方案并不一定是最优的，我们提出一种根据列车的结构（方向数、站点数、每个站点的车辆组等信息）进行评估解体先后的函数，该函数需要通过机器学习进行获得；2. 我们算法执行过程中用到的评估函数也可以通过进一步机器学习进行改进；3.我们上面的处理都是按照双推单溜进行的，我们在这里证明了双推双溜达到最优的一种情况，并且证明了这种双推双溜与双推单溜效果是一样的，只是各个站点的数目是两个双推单溜之和。
    最后，鉴于第一次参加ＧＭＣＭ，经验不足，最后论文写的很不好，虽然弄了８３页（其中包括６０多页的答案，汗），哎．．．．
! I8 I4 Y5 \! Y9 ?( f5 T
     总体上我们这几天过的还算是轻松，每天睡眠在8小时左右，仅仅最后一晚通宵。虽然我们做的不是很好，但是我还是想表达点我的想法：搞数模不是三天三夜（本科）或者四天四夜连轴转，我们参加数模是个享受的过程不是玩命。
   

---

作者: baochens    时间: 2008-10-2 20:59
    这是我第一次参加研究生比赛，我们队由三个学计算机的研一同学组成，从构成和经验上我们是不足的。对于我本人而言，从06年第一次参加全国赛来，到现在已经两年多了，加上这次，共参加了三次全国赛（两次本科，一次研究生）和两次美国赛，也指导过几次比赛。总体来数，学到了很多，收获了很多。下面谈谈对数学建模的一些浅薄的看法。
  
* t9 C0 \# ~& c       我觉得比赛关键的是:
7 B5 X; x- q9 @# C       1.学会在统一标准下的团队合作。标准不统一就会导致三个和尚挑水的笑话，这在比赛中是很多见的。
        2.学会在有压力无处求助的时候把握方向和果断决策。我们都知道思路不是一下子就有的，模型不是一下子就建立的，而且在建模的过程中会出现很多未曾遇到和想到的事件发生，如何处理这些事我想是数学建模最核心的地方，正是通过对这些事件的处理我们提高了自己。很多人问过我，当不知道该怎么做的时候我该怎么办呢？我的意思是，大的方向一定要正确，而这个大的方向从某种程度上是由每个人对哲学的认识所决定的（说的有点玄乎啊，别介意 ）。有些方向有些事我们不需去做的，具体判断哪些方向可以下手这个很难说，很多专家搞研究搞了很久才发现原来这个方向没钱途。也许这是某种潜在的能力，我个人觉得对一个人（特别是搞研究的人）是很关键很核心的。
        3.做最好的自己，获自己的一等奖（特等奖）。很多人参加比赛都没获奖，就我个人的认识而言，这些没获奖的人绝大多数是因为不了解数学建模的“游戏规则”。从某种程度上说，是还没有入门，而这个入门环节如果通过比赛来认识和提高这代价是很大的，所以这就产生了培训的必要。当然，培训不能解决一切，大部分给你提供的是间接的经验和教训，我个人非常坚定的认为直接经验和教训对人是至关重要的，没有直接经验和教训一个人不可能对某些事有很深刻的认识。但是，鉴于人生苦短，我们很难所有事都直接体验，所以我们需要读圣贤书听他人介绍经验之类的。我们首先要直接体验一些事，然后根据这些直接的体验（少数）和间接的体验（绝大多数）来得到对这些绝大多数事情与直接体验相似程度的认识（类比+人类智能因素）。当我们付出后不一定就能获奖，我想说的是获奖不能说明一切，只能说明你做的和评委的理解相差不大或者说是比较适合评委的口味。我们尽了最大的努力，提高了自己，发觉自己某些方面的不足然后提高自己这是最关键的。比赛最关键的是享受，最大的对手是自己。

---

作者: zty2500    时间: 2008-10-2 21:11
不错 ，支持 ，学到了
PS ：今年我 做了 两天C 最后 还是 放弃了 C转做 A ！

---

作者: georgewon    时间: 2008-10-2 21:12
标题: 回复 1# baochens 的帖子
这哥们够狠，所有的比赛都参加了，还指导过几次，那是相当的强~~~~~~~

---

作者: qbbcyf    时间: 2008-10-2 21:22
我也做的是C题，如lz所说，理解这个题目要花很长的时间，我觉得题目问的不是很清楚，所以我们开始的一两天根本就找不到思路，后来我把中时和解编次序联系起来，简化成为一个TSP问题，利用遗传算法求解，由于适应度函数很难操作，导致我摆弄些程序用了很长时间，几乎没有怎么睡觉，后来到第2，3，4，5问的时候，我已经没有精力去编写程序，只是在第一问的程序上进行了修改，好在程序的通用性还好，都计算出来了结果，当然有些结果可能不是很好，总算是匆匆的做完，感觉这次的题目还是难度大点。

---

作者: zhc6851    时间: 2008-10-2 21:27
厉害厉害:

---

作者: cilluick    时间: 2008-10-3 00:05
确实，我们理解C题意思也画了1天多时间，用遗传算法做了，花了很长时间，但最后没有得到结果，后来用的贪心做的，也只做了第一问，后面的几问都没有时间来做，只是在第一问的基础上加了些条件，求出一个结果。我们做出了一个仿真的演示程序，快2000多行，MFC做的，几天下来都快累死了，不过时间太少，做的效果还是不理想。

---

作者: chenming    时间: 2008-10-3 08:56
标题: 意见与兄弟不同
竞赛只有对与错，没有享受对或者享受错；破釜沉舟，无论对错，程序运行完后才感知对错，然后再享受对错，享受程序。

---

作者: baochens    时间: 2008-10-3 10:45
第一次参加研究生建模，发觉研究生建模相比于本科的更偏重实用性，问题更专业。
* `! a* D7 e" `8 l& R- L' X
回复楼上：我没说什么对与错的事啊，不管是比赛还是其他。

---

作者: woniu_87    时间: 2008-10-3 19:42
分析问题很深刻嘛

---

作者: Raptor    时间: 2008-10-3 23:27
研究生竞赛和大学生竞赛确实有质的差别，希望我两年后也能参加研究生建模

---

作者: Raptor    时间: 2008-10-3 23:31
８３页，其中包括６０多页的答案，就凭这论文的厚度评委也要仔细考虑一番，我们的论文只有19页，只不过我们是本科生

---

作者: tangbaby    时间: 2008-10-5 09:24
遗传算法。。。。。。我估计你没戏

---

作者: baochens    时间: 2008-10-5 23:51
GA...传说中很promising的算法

---

作者: baochens    时间: 2008-11-19 09:57

3 ~- F  v  P; f5 N3 ^3 ?8 A以下是Ｃ题一等奖获奖名单：

: Q# N% Q8 i9 y/ H4 U1        1042238        山东大学        孙宝臣        张翠翠        高希峰
" w3 P5 b7 c' u! z. ^6 q8 L2        1042609        青岛科技大学        汤志高        谢  冰        于  琳
3        1000704        北京理工大学        张晓晨        朱  昊        王  博
& W4 q1 X5 y8 h7 E/ I& u5 d4        9004401        海军工程大学        周  晨        王  建        史掁宇
5        9006820        第二炮兵工程学院        雷雄俊        吕  东        罗元俊
6        1141404        中国石油大学（北京）        祁彬彬        史博会        高建军
7        1042607        青岛科技大学        宋传胜        刘  锋        刘彦龙
8        1061301        西南交通大学        刘  盾        韩  冬        赵  军
& Q# i- v2 h. O) v9        1001310        北京邮电大学        何可嘉        唐  杰        李辛鹤
10        9005203        空军工程大学        梁晓龙        宋  敏        胡明朗
11        9005204        空军工程大学        黄聪会        周二虎        吝  科
& E, u0 m2 U; x12        1024809        上海交通大学        周  悦        栾士岩        曹  祥
13        1028637        东南大学        陆佳明        姚伟峰        黄德光
% O5 a: J+ G& C; a! d5 ?8 ^8 `
红色字体是我们队，纯属侥幸，获得初评一等奖．．．

---

作者: xiaohongwei    时间: 2008-11-19 10:01

---

作者: bestwolf    时间: 2008-11-19 15:05
标题: 太强大了
太强大了，牛人，景仰中。。。。

---

作者: wuzoujing    时间: 2008-11-20 17:14
楼主太厉害了！！我也是c，理解题目花了大半时间，最后结尾太潦草了~~答案只贴了一部分到论文中，怕论文正文比答案还少不好~~~最后只得了三等，受伤啊！！

---

作者: wuzoujing    时间: 2008-11-20 17:15
baochens 能把你的论文发给我看看吗？好好学习学些~~~~

---

作者: wuzoujing    时间: 2008-11-20 17:15
wuzoujing@163.com

---

作者: tangbaby    时间: 2008-11-21 16:33
我知道你在等我回复，哼~~我还是不喜欢遗传算法，西安见~
可是我现在看你帖子里面没有遗传啊~~

: A4 x4 q/ ]8 J' m4 P' d[ 本帖最后由 tangbaby 于 2008-11-21 16:36 编辑 ]

---

作者: 复活    时间: 2008-12-1 11:59
我第一次参加数模，呵呵
想象的挺恐怖，真正经历过感觉也是一段很有启发的锻炼

---

作者: qust_scs    时间: 2008-12-10 21:44
呵呵，同感啊！遭受也基本相同，也是前两天基本没干什么。只是去理解题意和找参考文献了。第二天快完了才如梦方醒，着手建模，还好文献看多了题目理解深了，建模也就快了，最终用 遗传算法 类似TSp问题编写了程序，再辅以淘汰择优函数和检验函数，终于在交卷前把结果出来了，成绩还不错！

---

作者: wuzoujing    时间: 2008-12-30 21:48
29# baochens
十分感谢！！
我已经下了看了看，兄弟文章做到很完善，代码、帮助文档写的也很规范。另，我们的模型也采用了分支定界，但没有提出这个名词来，很受伤～～～

---

作者: wuzoujing    时间: 2008-12-30 21:52
评估解体先后，我们采用的是模糊数学理论，根据各影响因子权重进行计算综合指标，来获取解体顺序。

---

作者: sunchao    时间: 2009-1-18 14:36

---

作者: yuhuayuanyu    时间: 2009-2-26 10:29
不错 ，支持 ，学到了

---

作者: dongmiao    时间: 2009-4-12 15:52
有没有做A题的啊，很需要优秀的论文

---

作者: iori1986iori    时间: 2009-5-2 08:29
我一次全国赛，一次美赛。收获很多。超级多啊

---

作者: zww86    时间: 2009-5-23 11:07
你们玩命果然玩的很强

---

作者: wang6895    时间: 2009-6-6 10:38

( B# b  o* ^- m& W5 K/ W作自己的第一

---

作者: meiyi128    时间: 2009-7-15 08:15
今年打算参加比赛，第一次参赛没啥经验，还要多多学习啊

---

作者: xiaobingforever    时间: 2009-7-18 15:02
像前辈学习！

---

作者: shumo779    时间: 2009-7-21 09:45
C题确实比较难！！爱有B题

---

作者: qqqqqq    时间: 2009-7-27 02:33
挺欣赏楼主那句“做最好的自己，获自己的一等奖（特等奖）”的，虽然我的水平低微，也不指望我这个菜鸟的水平能怎么超常发挥，但是我还是会报名参加比赛，只是为了多学些东西，多见识些实际中的问题，多提高一下下自己的各种能力，甚至多认识几个志同道合的朋友……呵呵，我这么想是不是只是一种菜鸟自我安慰的阿Q精神呢？

---

作者: qqqqqq    时间: 2009-7-27 02:39
26# tangbaby
又一个高手出现了……请您也奉献出您的论文供我们膜拜和学习吧！！！

---

作者: ccsmars    时间: 2009-8-11 13:27
我们组也是缺乏专业知识，直接转入其他题目了

---

作者: 李若琪683197    时间: 2009-8-11 19:43
值得学习和鉴赏呀。。。

---

作者: insightlight    时间: 2009-8-12 00:25
dddddddddddddddd

---

作者: insightlight    时间: 2009-8-12 00:26
ddddddddddd

---

作者: yimizi    时间: 2009-8-12 12:37
太崇拜了！

---

作者: yanano    时间: 2009-8-12 18:37
厉害厉害，学习了！

---

作者: cixiang    时间: 2009-8-19 13:39
楼主写的不错，向你学习啊

---

作者: xxj198712    时间: 2009-8-19 19:52
doushiniurena

---

作者: 海生    时间: 2009-8-25 22:23
强悍啊@！！！！！

---

作者: 海生    时间: 2009-8-25 22:25
哎
: Q0 {+ B0 S6 {$ T好难啊啊啊啊啊

---

作者: longshui2848    时间: 2009-8-26 13:06
谢过了~~~~~

---

作者: 半糖主义    时间: 2009-8-26 18:26
个人觉得以上能参加比赛的人都是很厉害的，只要是能坚持下来，就已经很厉害了！
呵呵

---

作者: jinyang.yu    时间: 2009-8-27 09:40
我们现在在练这个题啊，那个程序根本编不出来啊。对于一个本科的来说是不是太难了？

---

作者: mezhaoyun    时间: 2009-8-27 10:11
20# baochens
! ]1 o- U- m0 L  I) M
丫丫，真牛

---

作者: mezhaoyun    时间: 2009-8-27 10:12
20# baochens

丫丫，真牛

---

作者: 洛殷    时间: 2009-8-27 14:54
这个过程，我也要经历了

---

作者: cuiming06121033    时间: 2009-8-28 23:29
恩 说得很好 值得借鉴

---

作者: wangxinzhi    时间: 2009-8-30 14:05
同意楼主，“参加数模是个享受的过程”

---

作者: lirui0081    时间: 2009-8-30 16:04
楼主强人
7 U1 n: Y' ~3 w7 C- `3 z" j顶你~~~~！

---

作者: kqian1987    时间: 2009-9-2 17:57
顶了～比赛临近，心里没谱～

---

作者: formulaone9275    时间: 2009-9-2 22:41
谢谢分享，支持一下

---

作者: 郑志航    时间: 2009-9-3 13:40
你们真猛啊！我这次参赛

---

作者: 小万    时间: 2009-9-3 15:36
学到了很多啊！！

---

作者: 荆棘鸟13    时间: 2009-9-16 14:43
顶一下先   8错  都是牛人~~~~~~~

---

作者: olh2008    时间: 2009-9-16 15:24
有同感，呵呵……

---

作者: 522902573    时间: 2009-9-16 16:02
dddddddddddddddddddd

---

作者: 爱之日    时间: 2009-11-27 21:01
多谢楼主分享竞赛经验，对我以后参赛很有用。
谢了！

---

作者: 爱之日    时间: 2009-11-27 21:14
的确很强，希望以后有机会参加研究生数学建模建模竞赛

---

作者: csucsm    时间: 2009-11-27 22:42
我和两个师兄一起，三个搞计算机的，做了今年的D题，
最后得奖，与大家同感~~~！！！
. e0 W! O% N/ i; A, d支持~~！！！

---

作者: gzyefeng    时间: 2009-12-12 22:02
很好。。顶啊。。。。。。。。。。。。。

---

作者: mnpfc    时间: 2010-3-16 23:02
很受用，顶楼主

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5