资源描述：
《基于矩阵的公交查询高效算法_陈培军》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第32卷第1期太原科技大学学报Vo.l32No.12011年2月JOURNALOFTAIYUANUNIVERSITYOFSCIENCEANDTECHNOLOGYFeb.2011文章编号:1673-2057(2011)01-0050-05基于矩阵的公交查询高效算法陈培军,王欣洁(太原科技大学,太原030024)摘要:引入最小乘车次数矩阵Q,直达信息矩阵,直达信息转置矩阵,充分利用矩阵Q进行宏观的判断,用后两个矩阵进行精细的查找,并设计寻找和组装最优方案的算法,进而在最小换乘算法的基础上设计了高效公交查询算法。该算法不仅缩短了查询时间,且使查
2、询结果更加人性化,可给出最少换乘次数为3的出行线路查询结果。关键词:公交查询;最小换乘算法;最小乘车次数矩阵;直达信息矩阵中图分类号:TP311文献标志码:A随着城市规模的扩大,公共交通越来越受到重应的记录,并使得这些记录避免了同一换乘站点前视,得到飞速发展,对城市的作用越来越大,但如何后两次乘车线路相同的情形。文献中的系统仅使用合理选择出行线路,成为很多人面临的问题。因了二次换乘,在利用该方法获得高次换乘结果时,此,公交网络信息的查询变得越来越受到重视。很该方法计算了大量的冗余的信息,从而增加了不必[1-4]多文献都认可了最小换乘算法,
3、并融入一定的要的运行时间。冗余来自两方面:(1)若低次换乘已优化思想,得到一定范围内的最优。经可达,且结果中已包含最优,则会组合出很多的文献[2]中详细介绍了5次以内的最小换乘算无价值的高次换乘结果;(2)矩阵计算得到了起点法,若该算法用于判定最小换乘次数是有效的,则可到达的所有中间站点,而其中很多无法直达终要给出具体方案还需很多辅助工作。存在的问题是点,没有充分利用直达矩阵稀疏的特点。随着换乘次数的增加,查询需要的时间有可能很本文主要研究如何设计高效的换乘算法。在最长,实时效果差,所以很多系统实现时一般都只考小换乘算法中,要想缩短算法的
4、运行时间,可行的虑到最多二次换乘(乘车次数为三次,乘车次数比方法有:(1)加快两站点是否可直达的查询及可直换乘次数多一次)的查询结果。达时线路信息的获取;(2)若知道两站点间的最小文献[5]中引入直达矩阵和最小换乘矩阵Q,换乘次数,则调用查询方法更具针对性,可直接去利用Q矩阵来评价公交网络的方便可达性;用掉很多不必要的低次换乘查询。在以上想法的指引Dijkstra算法寻找最短路径时,利用Q矩阵对待检标下,本文设计了确定换乘方案的高效算法,并以号进行筛选,减少计算量,从而得到综合考虑换乘2007年全国大学生数学建模比赛B题的数据为例和路径长
5、度的最佳路径。该算法要在全空间中搜给出相应的实验结果。索,一般情形下搜索代价仍较大。1相关的数据结构与定义文献[6]定义了一种新型的直达矩阵,并提出两种新的矩阵运算。在此基础上,建立起了一种基输入线路信息。对B题的数据进行一定的处于矩阵运算的公交查询算法。算法可行,本质上仍理,用MATLAB的cell保存线路信息,设计数据结是换乘算法,文献中定义的运算本质上就是找到相构如下:收稿日期:2010-09-01作者简介:陈培军(1978-),男,讲师,主要研究方向为计算智能、最优化方法研究。第32卷第1期陈培军,等:基于矩阵的公交查询高效算法5
6、1站点i可以直达站点j的线路数。若站点i有m条可线路名计价方式行车方向线路站点以直达站点j的线路,则Dij=m;若站点i没有可以具体形式为:直达站点j的线路,Dij=0;若i=j,规定Di=0.定datacell=义直达线路矩阵T=(Tij)N@N,元素Tij为结构体,保{存站点i直达站点j的线路编号、乘车时间、乘车站{'L001,''0,'s','sym(['S0619S1914,S0710])'}数、票价等相关信息,且按某种性能指标排序;若站{'L001,''0,'x','sym(['S0710S0128,S0619])'}点i到站点
7、j不存在直达的线路,则Tij为空。D矩阵{'L002,''0,'u','sym(['S3748S2160,S0004])'}为稀疏矩阵,相应于Dij==0的Tij为空,考虑到存{'L002,''0,'d','sym(['S0004S1968,S3748])'}储空间,可以且必须采用稀疏存储。为表达方便,引,入以下记号,cindex(i)表示站点i(i=1,2,,,N){'L017,''0,'r','sym(['S3748S2160,S3748])'}可直达的站点数,index{i}表示站点i可直达的所有,站点,index{i}(j)表示站
8、点i可直达的第j(j=1,2,},,cindex(i))个站点,可用D{i}(j)、T{i}(j)表示其中,各个属性的命名方式如下:站点i和其可直达的第j个站点index{i}(j)之间的(1
