IOI'94 汽车问题

admin

有一个人在一个公共汽车站上，从12:00到12:59观察公共汽车到达本站的情况，该站被多条公共汽车线路所公用，他记下了公共汽车到达本站的时刻。
　●在12:00─12:59这个期间内，同一条线路上的公共汽车以相同的时间间隔到站。
　●时间单位用“分”表示，从0到59。
　●每条公共汽车线路上的车至少到达本站两次。
　●在本例的公共汽线路数一定≤17。
　●来自不同线路的公共汽车可能在同一时刻到达本站。
　●不同公共汽车线路的车首次到站时间和（或）（and／or ）时间间隔（到站的）可能相同。如果两条公共汽车线路的车有相同的开始时间和相同的时间间隔，它们必须分开表示出来。
　　请为公共汽车线路编一个调度表，目标是：公共汽车线路数目最少的情况下，使公共汽车到达本站的时刻满足输入数据的要求。对于每一公共汽车线路，输出其起始时刻（第一次到达本站）和到达本站的时间间隔。

输入数据：
首先给出观察者所看到的驶进本站的公共汽车数n（n≤300），下面以递增顺序给出各公共汽车到达本站的时刻。我们的例子是：
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

输出数据：
一个数字，至少需要几条线路本例为3，分别是
0 13
3 12
5 8

admin

试题仅给出12:00-12:59期间汽车到达本站的情况，要求得出公用该站的汽车线路最少的方案。显然，单凭试题给定的已知条件，根本无法找出一个能准确反映两者间运算关系的数学模型。在这种情况下，除了采用回溯法外，别无他路。
一种回溯搜索的策略是从12:00开始逐分钟往后搜索，求出所有满足输入数据要求的线路方案，然后通过线路数的排序比较，求出最佳方案。但这种以分钟为搜索单位进行盲目搜索的算法效率实在太低。为此我们作了一些改进：

　　以各公共汽车到达本站的时刻作为搜索点，从第一辆汽车到达本站的时刻出发，按时间顺序搜索每一个有汽车经过的时刻ｔ。
　　设ｉ为某线路的汽车首次从本站出发的时刻（0≤ｉ≤59）
　　open(i)──i时刻出发的未确定时间间隔的线路数。 每新增一条由i时刻出发的新线路，open(i)＋1。初始时open(0-59)=0；
　　closed(i)──i时刻出发的已确定时间间隔的线路数+1。 每确定一条由i时刻出发的线路的时间间隔，close(i)＋1。初始时closed[0]，……closed[59]=1；
　　显然，若i时刻open(i)≥close(i)， 说明所有从ｉ时刻出发的线路中可能存在未确定时间间隔的线路，该时刻为未匹配时刻。
　　best──目前求出的所有方案中最少的汽车线路数。我们以best为槛值，当发现i时刻新增线路后的线路数大于等于best时，就不必再考虑该时刻往后的搜索了，因为不可能产生比已求得的best更好的方案，而是应该回溯至前一个有汽车经过的时刻，重新审定其线路的起始时刻和间隔。

　　１、确定经由本站的线路的起始时刻和时间间隔
　　每搜索到一个有汽车经过本站的时刻t， 为了确定该时刻经过的所有线路的开始时间和时间间隔，我们顺序搜索0……t-1时刻。若期间i(0≤i≤ t-1)时刻 open(i) ≥closed(i)且t时刻后每隔t－i都有汽车到站，则确认线路以i为开始时间、t－i为时间间隔，closed(i)+1并在时刻表中撤去t时刻和以后每个以t－i为间隔的时刻；

　　２、新增线路
　　在确定了 t 时刻经由本站的所有线路的开始时间和时间间隔后， 若目前线路数+1＜best，则新增一条以t时刻为出发点、但尚未确定时间间隔的线路(open(i)+1)， 并在时刻表中撤去t时刻；

　　３、确定最佳方案
       时刻表中t时刻后无汽车到达，说明一种方案产生。此时，若线路数＜best， 且所有线路的时间间隔都已确定, 则线路数赋于best , 打印所有线路的开始时间和间隔时间。 由于搜索过程中best递减，因此在回溯搜索完所有可能方案后，最后输出的方案即为最佳方案；


例如输入数据为
9 (汽车数)
1 4 6 7 8 10 12 13 14 (各公共汽车到达本站的时刻)

　　第一辆车时刻1首次到达本站，由此开始了第一条线路（arrive(1)=1），扩展出v1。而第2辆车到达时刻为4，时刻4后每隔4-1=3都有车经过本站，因此结点v2确定了第1条线路的间隔时间为3（timelength(1)=3）。
      由于时刻表中撤去第一条线路经由本站的时刻后，使得时刻6前无汽车通过，因此扩展出的Ｖ３确定时刻６作为第２条线路的开始时间（arrive(2)=6）。 而在时刻表中撤去时刻6后， 时刻8前也无汽车通过， 因此继后的Ｖ４又将时刻８作为第３条线路的开始时间（arrive[3]=8）。
　　从Ｖ４的时刻表可以看出，由时刻６出发的第二条线路于时刻１２经由本站，因此Ｖ５确定该线路的间隔时间为６。（timelength[2]=6）时刻表中撤去时刻１２后， 使得时刻８出发的第三条线路时刻１４经由本站， 由此得出第三条线路的时间间隔为１４－８＝６（timelength[3]=6）。至此时刻表中再无车辆通过，Ｖ６为目标结点，槛值best 为当前线路数３。
　　然后回溯至Ｖ５。由Ｖ５的时刻表看出，时刻１４前无车辆通过，只得回溯至Ｖ４。Ｖ４的时刻表中时刻１２有汽车通过，因此将时刻８出发的第三条线路的间隔时间修正为４，
扩展出Ｖ７。（timelength[3]=4 ）撤去第三条线路后使得由时刻６出发的第２条线路在时刻１４到站，因此将该线路的间隔时间修正为８（timelength[2]=8）， 扩展出目标结点Ｖ
８。
　　由于新方案的线路数已为best，因此摈弃该方案，由Ｖ８往上回溯。途经的Ｖ７、Ｖ４、Ｖ３、Ｖ２无法扩展，而Ｖ１的时刻表中时刻４前无车辆经由本站、时刻４后每隔２分钟
有车辆通过， 因此增加一条由时刻４出发、 间隔时间为２的新线路（ arrive[ 2] = 4,timelength[2]=2），扩展出Ｖ１０。在时刻表中撤去了线路２后，仅剩时刻７有车辆通过，
可以确定由时刻１出发的第１条线路的间隔时间为６（timelength[1]=6）， 最终得出了最佳结点Ｖ１１，best=2，即至少需要２条公共汽车线路，方能使到站时刻满足输入数据要求：
　　第一条线路的开始时间为1，间隔时间为4；
　　第二条线路的开始时间为4，间隔时间为2；

　　显然，改进后的回溯算法由于
　　１、摈弃了逐分钟搜索的作法，将搜索定位在几个有车辆通过的时刻上；
　　２、使用槛值best来削减那些必须检查的但不产生好的方案的结点，使得实际扩展的结
点数少于可扩展的结点数；
　　因此提高了搜索效率，具有一定的优化思想。特别在处理时间、任务序列一类的问题上，
这种算法更有其独到之处。