08GMCM比赛感言

[复制链接]

字体大小: 正常放大

baochens

5 主题	3 听众	130 积分

升级 15%

TA的每日心情

	开心 2013-8-21 01:50

签到天数: 3 天

[LV.2]偶尔看看I

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

电梯直达

发表于 2008-10-2 19:25 |只看该作者 |正序浏览

|招呼Ta 关注Ta

我们做的是C题，理解这个题目花了一天多的时间（汗

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