《表3 标签集L+ (S) 和L- (E)》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《公交网络路径规划问题中的一种高效索引方法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

定义9的条件c) 给出了查询的思路。对于从站点s到站点d、出发时刻不早于π、到达时刻不晚于π'的SDP查询q，算法在TAIL索引的L+（s）中找到出发时刻≥π的标签l+=〈u，πdept，πarr，·〉和在L-（d）中找到到达时刻≤π'的标签l-=〈u'，π'dept，π'arr，·〉，如果u=u'且πarr≤π'dept，则l+和l-拼接的路径是q的候选解。算法找出所有候选解，再从中选出符合查询q的解。这个求解过程类似数据库的连接操作。对于EAP查询，取π'=∞；对于LDP查询，取π=0。由于标签集合内的标签已排好序，所以可以通过线性扫描L+（s）和L-（d）的集合找出所有候选解。例如查询从S到E的、出发时刻不早于3、到达时刻不晚于30的SDP，对应表3，首先在L+（S）扫描第一个标签l1，在L-（E）中扫描第一个标签l6，l1和l6能构成路径，得到候选解，用l1+l6表示。由于L-（E）中起点为D的标签（l6，l7，l8）是按到达时刻升序排列的，所以没必要再配对l1和l7，l8，因为它们不可能生成更优的解。接下来，扫描L+（S）中的下一个标签l2，同时也扫描L-（E）中的下一个标签l7。因为l2和l7不能构成路径，所以只能再扫描L-（E）中的下一个标签l8，得到又一条候选路径，用l2+l8表示。至此L-（E）的标签扫描完毕，查询结束。在l1+l6和l2+l8两者中，l1+l6的耗时最短，为查询q的解。算法详情请参考文献[1]。