搜索对象与策略的重要性 由“汽车问题”浅谈深度搜索 &nbsh1; 欢迎阅读本文档,希望本文档能对您有所帮助! 由“汽车问题”浅谈深度搜索的一个方面———搜索对象与策略的重要性 问 题 描 述 有一个人在某个公共汽车站上,从12:00到12:59观察公共汽车到达本站的...
问 题 描 述
有一个人在某个公共汽车站上,从12:00到12:59观察公共汽车到达本站的情况,该站被多条公共汽车线路所公用,他依次记下公共汽车到达本站的时刻。
l 在12:00-12:59期间,同一条线路上的公共汽车以相同的时间间隔到站。
l 时间单位用“分”表示,从0 到59 。
l 每条公共汽车线路至少有两辆车到达本站。
l 公共汽车线路数K一定≤17,汽车数目N一定小于300。
l 来自不同线路的公共汽车可能在同一时刻到达本站。
l 不同公共汽车线路的车首次到站时间和到站的时间间隔都有可能相同。
请为公共汽车线路编一个调度表,目标是:公共汽车线路数目最少的情况下,使公共汽车到达本站的时刻满足输入数据的要求。
例如:
汽车编号 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
到达时间 |
0 |
3 |
5 |
13 |
14 |
14 |
21 |
25 |
那就可能存在这样一个解,由以下3条汽车线路组成:
解 析
经过一系列的分析,我们决定用深度搜索(由于通篇讨论的是深度搜索,以下就统一简称搜索)解这道题目。
对这样一个问题,首先提取出三个关键要素:时间、车、路线。
☆车辆的特征是时间,
☆路线的特征是“首发车时间”和“间隔时间”,这等效于“第一辆车”和“第二辆车”。
面对这三个关键要素,下面就要从中确定搜索对象和搜索策略。可以看出,题目要求的是车和线路的关系,而时间在其中起的是描述作用和条件制约作用,因此,本题的搜索对象应该是车或线路这两个关键要素。
● 分析搜索对象及策略
1.对象—→ 车
由此对象而产生的搜索策略是:按到站时间顺序,依次枚举每辆车属于哪条路线。
注意路线的特征,若一路线的第一辆车和第二辆车确定了,那该路线也就确定了。
大致搜索 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 为: