城市公交线路快速查询实现

　　随着中国经济的快速发展，城市交通问题日益突出，尤其在大中城市，改善交通已是刻不容缓，许多国家和城市都在积极地研究和发展本地的公共交通设施与服务，公交优先已成为城市交通发展的基本战略。

　　公交查询是方便市民及广大游客出行的重要举措。目前，国内的公交查询系统发展很快，基本功能都已实现，现在正朝着人性化的方向发展。例如，原来系统在选择起、终站点时是给出已有的站点名称，操作时只能在其中选择，而现在的一些系统可在地图上选择站点进行查询，甚至在地图上选择任意两点就可查找出最合适的路线。但这些系统也存在一些问题，主要是查询效率低，尤其是换乘查询，而大多数查询都涉及到换乘，甚至是多次换乘。对于直达车查询来说，用一次或两次循环即可实现，而对于换乘，算法不同，效率相差很大，本文主要讨论换乘算法。

　　1 普通算法设计

　　公交换乘查询的基本原理如下：首先查找出经过起点与终点的所有车次，然后查找各车次是否有相交的站点，如有，则该站点可作为中转站，找出所有可能方案，然后选择最优方案，如需要多次换乘，则可嵌套一次换乘。

　　普通算法具体设计如下：①设 start、end 分别为起点与终点两站点，Start(i1)(j1) (i1=1,2…n1，i1 表示经过起点的线路集合;j1=1,2…m1，j1 表示各车次途经的站点集合)，相应终点也有 End(i2)(j2);②从 Start(i1)(j1)与 End(i2)(j2)取出某一线路的途经站点集合，然后逐一对比各站点;③检查是否有相同的站点，如果有，则记下当前的站点与起、终点车次，否则继续循环;④重复②、③步骤直到结束。假设经过起点的车次有 n 趟，每一趟车经过 ik(k=1,2…n)个站点;经过终点的车次有 m 趟，每一趟车经过 jh(h=1,2…m)个站点，那么计算换乘一次所需要的时间复杂度是：nхmх(i1﹢i2﹢…﹢in) х(j1﹢j2+…+jm)，如果多次换乘其时间复杂度将呈指数级增长。

　　2 改进算法设计及实现

　　改进算法与普通算法的基本原理相同，但具体设计不同。

　　2.1 算法设计

　　本算法主要对普通算法中站点与站点比较找出相同站点的方法进行改进，其原理如下：①对公交站点进行编号，且号码唯一，对线路途经的各站点名称用编号替代再对其排序;②以查找相同数值编号的元素为条件，如图 1 所示，S 和 E 分别表示经过起、终点某一车次途经站点集合，对 S 中的第一个元素，从头开始扫描 E 中的每一个元素，顺序查找满足条件的元素，找到后就将 S 中此元素记下来;当遇到 E 中第一个大于 S 中的元素时，对 E 的查询不再继续;③找到 S 中的第二个元素，然后从刚才的中断点处继续顺序扫描 E，查找到满足条件的元素后便记下，直到遇到 E 中大于 S 中的元素时，对 E 的查询不再继续;④重复②、③操作，直到 S 或 E 中的全部元素都处理完毕。使用本算法完成 1 中查询所需时间复杂度极大值是：nхmх((i1﹢i2﹢…﹢in) ﹢(j1﹢j2﹢…﹢jm))。