08GMCM比赛感言

baochens

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

; E: \% {/ F0 r5 t1 u     总体上我们这几天过的还算是轻松，每天睡眠在8小时左右，仅仅最后一晚通宵。虽然我们做的不是很好，但是我还是想表达点我的想法：搞数模不是三天三夜（本科）或者四天四夜连轴转，我们参加数模是个享受的过程不是玩命。
   

baochens

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

zty2500

不错 ，支持 ，学到了
0 K: [, s& r* w3 c- F1 MPS ：今年我 做了 两天C 最后 还是 放弃了 C转做 A ！

georgewon

这哥们够狠，所有的比赛都参加了，还指导过几次，那是相当的强~~~~~~~

qbbcyf

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

zhc6851

厉害厉害:

cilluick

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

chenming

竞赛只有对与错，没有享受对或者享受错；破釜沉舟，无论对错，程序运行完后才感知对错，然后再享受对错，享受程序。

baochens

第一次参加研究生建模，发觉研究生建模相比于本科的更偏重实用性，问题更专业。
; R- ^: i- `. n( d
5 w5 H  F6 J! O. ?% O* D5 N" d回复楼上：我没说什么对与错的事啊，不管是比赛还是其他。