一种改进的公交换乘算法的实现

1、本栏目责任编辑:李桂瑾人工智能及识别技术1引言目前,实现公交换乘现有的算法和方法:迪杰斯特拉算法、蚂蚁算法、依靠GIS 组件等。其中迪杰斯拉算法在公交站点很多的情况下,数据量大,运算速度慢;蚂蚁算法难于理解;GIS 组件成本高。相对上述已有方法,用邻接矩阵方法实现公交换乘能够弥补上述不足。南昌市公交线路存在内外线、来返路线一致、来返路线不一致等情况。某系统模块要实现以不依靠第三方组件、乘车路线较优为约束条件的公交换乘。通过对邻接矩阵实现公交换乘方法进行了改进,增加实现来返路线不一致、内外线、最少站点等功能。本文首先介绍了改进的邻接矩阵实现公交换乘的基本理论,然后阐述了怎样用改进的邻接矩阵实现公

2、交换乘。2邻接矩阵实现公交换乘理论2.1邻接矩阵实现公交换乘基本思想把每条公交线作为图中一个顶点,任意两条公交线路之间的联系取决两者之间有无交点(共同的停靠站点,相应地该两条线路之间的矩阵元素值为1或者0。这样就把城市公交线路系统可以抽象为n*n 邻接矩阵,可以借用邻接矩阵的特性和算法,来解决公交线路换乘问题。2.2线路矩阵的建立假定有1路、2路、3路、4路这四条公交线路,如图1。图中1、2路有交点;3、4路有交点;2、4有交点,相应的邻接矩阵A 如图2。 图1 图2图32.3邻接矩阵得到换乘路线在矩阵A 中,(V1,V4为0,则V1到V4经过一次换乘不能到达;(V1,V2为1,则V1到V2经

3、过一次换乘能到达。(V1,V4在矩阵A*A 为1,说明经过二次换乘能够到达。“中间线路”是哪条呢?矩阵A 的第一行为t1=(1,1,0,0第四列的转置为t2=(0,1,1,1。t1&t2=(1&0,1&1,0&1,0&1=(0,1,0,0=t3。t3为中的第2个元素为1,则说明“中间线路”是线络2。一次换乘矩阵为A ,n 次换乘矩阵为A 的n 次方,表达式为:A n =A*A A 。这表明1路中的任何站点经过一次转乘是不能到达4路中的任何点;要到达,必须经过两次换乘。运算过程:1*0+1*1+0*1+0*1=20=>1过程原理:1*1,前面“1”来

4、源于第一行的第二个数,后面“1”来源于第二行的第四个数。这表明2路是1路和4路之间的“桥梁”。3邻接矩阵实现公交换乘的具体方式3.1针对具体线路如何构建邻接矩阵城市公交具体线路各式各样,但我们可以归纳了三种情况:内外线、往返线路不一致、往返线路一致三种情况。对于往返一致的线路可以作为一个顶点;内外线、往返不一致可以分开作为两个不同的顶点。如图4:图41路为V1,2路往线为V2,2路返线为V3,3路内线为V4,3路外线为V5。V2与V3;V4与V5都认为有交点。3.2如何实现公交换乘收稿日期:2007-06-29作者简介:许军林(1980-,男,江西临川人,东华理工大学硕士研究生,研究方向:计算

5、机网络与分布式数据库;蒋年德(1971-,男,广西全州人,教授,博士,研究方向:网络与分布式数据库、数字图像处理技术。一种改进的公交换乘算法的实现许军林,蒋年德(东华理工大学,江西抚州344000摘要:针对公交线路中存在往返路线不一致、内外线路等情况,对用改进的邻接矩阵方法实现这一类型的公交换乘进行了研究。最后通过对线路结果集进行筛选、比较实现了最少换乘、最少站点为约束条件的公交换乘查询模块。关键词:往返路线;内外线;邻接矩阵;最少换乘;最少站点中图分类号:TP301文献标识码:A 文章编号:1009-3044(200714-30517-02A Realization of Improved

6、Bus Change ArithmeticXU Jun-lin,JIANG Nian-de(East China Institute of Technology,Fuzhou 344000,ChinaAbstract:There are go-return route and out-in routes in bus route,use the method of better adjacency matrix to implement this kind of bus change.Finally,by selecting better in the sets of result,it ca

7、n achieve the aim of least bus change and stations in bus change module.Key words:go-return route;out-in route;adjacency matrix;least bus change;leaststations517人工智能及识别技术电脑知识与技术本栏目责任编辑:李桂瑾(上接第499页本文将神经网络技术应用于商业银行信用风险评估中。结果表明,神经网网络技术具有较好的判别功能。其优点在于:(1基于主成分的SOM神经网络模型在算法上和分类效果明显优于BP神经网络;(2神经网络方法是一种稳健的、

8、非参数的方法,具有很强的非线性映射能力,其学习经验的能力强,分类精度高;参考文献:2王春峰,万海晖.组合预测在商业银行信用风险评估中的应用J.管理工程学报,1999,13(1:58.3方洪全,曾勇对.银行信用风险评价体系的比较J.系统工程理论方法应用,2004,13(3:214-217.神经网络M,西安:西安电子科技大学出版社,2002.5何晓群.多元统计分析M.北京:中国人民大学出版社, 2004.在实现公交换乘之前,我们需要做的事是:估计公交系统中各站点互相到达最大的换乘数。因为公交线路是经过严格规划好的,因此不会很大,假设为4,则我们在数据库中分别建立矩阵A、A2、A3、A4。数据库中保

9、存线路信息时需要设定方向字段,以表明此线路是单向还是双向。(a求出所有经过起始站点X的路线集合set1和经过所有目的站点Y的路线集合set2。假设set1=1,23;set2=6,215。把set1和set2的元素分别组成数对(V1,V6、(V1,V215、(V23,V6、(V23, V215。(b根据邻接矩阵A n(n=1,2,3,4查出所有数对的值。以(V1,V6对应的数据值为例。先在矩阵A中进行查找,如果A中a16为1即数据库矩阵数据表中(V1,V6为1,则说明在站点乘1,再乘6线即可达Y点。(c如果A中a16为0,则在A2中查a16,如果为1,则说明X站点经过二次换乘可达到Y站点。(d

10、如果A,A2中a16,都为0,则在A3中进行查找。如果为1,则说明X站点经过三次换乘可以达到Y站点。(e中间需要换乘的路线就是:用相应矩阵中第1行和第6列的转置进行与运算,在得到的行列式中元素不为零对应的线路。因为线路中存在单向行驶的路线,所以我们要对初步结果集进行筛选。例如:从A点要B点,只有图5中的第三种情况才能到达。如何判断呢?抽取线路a的站点组成字符串L1:AC,抽取线路b的站点组成字符串L2:BC。通过判断其站点字符在字符中的相对位置得到两个布尔值,然后把两个布尔值进行“与”运算。b1=L1.charAt(转站>L1.charAt(起站;b2=L2.charAt(终站>L

11、2. charAt(转站;Result=b1&&b2;If(trueok Else false。大部分公交乘客在选择出行路线时,首先考虑的是换乘次数,其次是出行耗时和距离长短。而出行耗时与换乘的次数、等车时间、公交车沿途停靠站点耗时以及距离的长短密切相关。因此,对于出行耗时和距离长短,可以转化为换乘次数最少的基础上公交画沿途停靠站点多少的问题。(a实现最少换乘本文实现的方式是:先判断起始点X到目的站点有没有直达车,有则返回;否则在矩阵A中判断有没有换乘一次的方案,有返回;否则在矩阵A2中进行判断。(b实现最少站点在相同的换乘次数中,我们可以把乘车线路所有经过的站点组成数组,数组长度越少的说明经过的站点越少。这样相应乘车的时间越少。图54结束语本文分析了公交网络中公交路线类型,在文献1的基础上改进了公交线路模型,使模型与实际交通路线更相符合。提出对邻接矩阵的改进和完善方法,使改进后的方法更易解决实际中的公交线路模型;把改进后的公交换乘方法应用到南昌市