国家集训队2001论文集 骆骥

《国家集训队2001论文集 骆骥》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、冬令营论文交流骆骥由“汽车问题”浅谈深度搜索的一个方面———搜索对象与策略的重要性问题描述有一个人在某个公共汽车站上，从12:00到12:59观察公共汽车到达本站的情况，该站被多条公共汽车线路所公用，他依次记下公共汽车到达本站的时刻。l在12:00－12:59期间，同一条线路上的公共汽车以相同的时间间隔到站。l时间单位用“分”表示，从0到59。l每条公共汽车线路至少有两辆车到达本站。l公共汽车线路数K一定≤17，汽车数目N一定小于300。l来自不同线路的公共汽车可能在同一时刻到达本站。l不同公共汽车线路的

2、车首次到站时间和到站的时间间隔都有可能相同。请为公共汽车线路编一个调度表，目标是：公共汽车线路数目最少的情况下，使公共汽车到达本站的时刻满足输入数据的要求。例如：汽车编号12345678到达时间03513141421250143142551321线路一线路二线路三0351314142125间隔为14间隔为11间隔为8那就可能存在这样一个解，由以下3条汽车线路组成：解析经过一系列的分析，我们决定用深度搜索（由于通篇讨论的是深度搜索，以下就统一简称搜索）解这道题目。对这样一个问题，首先提取出三个关键要素：时间

3、、车、路线。☆车辆的特征是时间，☆路线的特征是“首发车时间”和“间隔时间”，这等效于“第一辆车”和“第二辆车”。面对这三个关键要素，下面就要从中确定搜索对象和搜索策略。可以看出，题目要求的是车和线路的关系，而时间在其中起的是描述作用和条件制约作用，因此，本题的搜索对象应该是车或线路这两个关键要素。●分析搜索对象及策略1．对象—→车由此对象而产生的搜索策略是：按到站时间顺序，依次枚举每辆车属于哪条路线。注意路线的特征，若一路线的第一辆车和第二辆车确定了，那该路线也就确定了。第4页共4页冬令营论文交流骆骥大致

4、搜索方案为：按到达时间顺序，依次对于那些没有确定属于哪条线路的车进行枚举，该车属于某新线路的第一辆车或属于某已有线路的第二辆车，若为后一种选择，则可确定路线上其他所有的车辆。………………0?3?5?13?0?3?5130?3135?不成立0133?5?不成立053?不成立0?3?5?0?3?03不成立0?0?35不成立014注意：表示的是一条线路。0为第一辆车到达时间，14为第二辆车到达时间。汽车编号12345678到达时间0351314142125还是看先前给的那个简单例子来构造搜索树大致如下：观察该搜

5、索树，发现：随着搜索树层数的递增，每层节点所扩展出的树叉数目逐渐增大。从直观上说：该搜索树从根开始，“分叉”越来越多，“枝叶”越来越茂盛。这就是搜索对象为车的搜索树的典型特点。2．对象—→线路由此对象而产生的搜索策略是：枚举每条路线包含哪些车，确定该路线。实际上，对每条路线，我们只要枚举其特征：第一辆车和第二辆车。再根据“有序化”思想，固定所有路线是按照第一辆车的到达时间为关键字排序的。大致搜索方案为：汽车编号12345678到达时间03513141421250?……014313不成立……03不成立014

6、3?……0143145?0143255?0253?01435不成立…………………………搜索每层都要确定一条路线：将未确定归属路线的到达时间最小的车固定第4页共4页冬令营论文交流骆骥为新路线的第一辆车，其后枚举这条路线的第二辆车，从而确定该路线。同样，根据先前给的那个简单例子我们也构造出了方法二的搜索树（见前页）。观察这个搜索树，和方法一的搜索树对比，我们发现，两者特性截然相反，该搜索树从根开始，“分叉”越来越少。两种搜索对象及策略是完全不同的，搜索树特性又截然相反。从宏观上，搜索树上节点多少，两者相差无几

7、。如何抉择呢？这时就要从微观上比较：●比较哪个搜索对象和策略更优既然是比较，就要有比较的标准。这里，确定了两个标准：谁易于优化剪枝；谁的操作量小★关于谁易于优化剪枝的比较：本题的主要剪枝有三种，如下逐一分析。◇可行性剪枝当路线的特征确定了，就可以判断该路线是否成立。方法一，搜索中，每层枚举当前车是哪条路线的第二辆车，都要用到该判断；方法二，每层是确定一条路线，也用到该判断。关键是，根据两者搜索树，方法一一旦剪枝，将剪去的是一大片“茂盛”的树枝，显然，相比之下，方法二剪枝的效果就差了许多。故在此剪枝应用上，

8、方法二比方法一逊色许多。◇与已知最优解比较剪枝这就要看谁能很快找到解了。显然，由于方法一可行性剪枝的优点，每次剪枝都能删去很多的不可行的节点，找到解的速度就不比方法二慢了。此剪枝，方法二不比方法一要好。◇排除重复剪枝注意到题目中时间这个关键要素的范围为0~59，而车辆数目可达300，说明，在同一时间到达的车辆数目很多！前面那个简单例子中，就出现了两个14，而到达时间为14的两辆车各属于那条路线是等效的，这就有重复。方法一对于同