一种城市公交查询快速算法_牟廉明.pdfVIP

第 27 卷第 8期 计算机应用与软件 V o l27 No. 8 2010 年 8月 Com puter A pplications and Sofwt are A ug. 2010 1 2 牟廉明 刘高峰 1 ( 641112 2 ( 641112 针对目前城市公交查询存在的问题, 首先对城市公交查询需求进行了详细分 , 利用最优直达矩阵对初始公交数据进行 预处理; 其次设计了换乘算子并给出最优查询标准判断方法; 然后利用直达矩阵是一个典型的稀疏矩阵, 将直达矩阵转化为十字链 表, 设计了高效的查询算法; 最后应用实例对算法的有效性进行了比较和验证 城市公交 直达矩阵 换乘算子 A FAST ALGORITHM FOR URBAN PUBL IC TRANSPORTATION INQUIRY 1 2 M ou L ianm ing L iu G aofeng 1 (KeyLaboratory of N umericalSmi ulation of SichuanProvince, Neijiang 641112, Sichuan, China) 2 (College of athematicsand Inf ormation Science,Neijiang Normal University, Neijiang 641112, Sichuan, China) Abstract In allu sion to the shortcom ing of urban public transpo rtation inquiry, f irstly, the inqu iry requ irem ent in th is reg ard is e labo rately analyzed, and the prmi ary data o f public transpo rtation is pre-processed by op tmi um nonstop m atr ix. Secondly, the transfer opera tor is des igned and the judgm ent m ethod of optmi um inqu iry standard is g iven. T h irdly, becau se nonstop m atr ix is a typ ica l sparse-m a trix, the effic ient query algorithm is designed a fter transform ing the large- scale nonstop m atr ix to cross cha in- list. L astly, the va lid ity of the algorithm is compared and testified w ith an instance. K eywords U rban public transpo rtation N onstop m atr ix T ransfer opera to r , 0 ( ; ( 2 , ( , . ; ( 3 , : [ 1- 7] ; , , [ 1- 7] ; ,