公交换乘算法 编程语言 编程语言 清风亭.doc

公交换乘算法 编程语言 编程语言 清风亭注册设为首页帮助首页|博客群|公社|专栏|论坛|图片|商城|交友|博客联播|投稿|随机访问|订阅 用户名 注 册 密码 忘记密码 保存密码 用户名 注 册 密码 忘记密码 保存密码 清风亭 复制我的GIS生活首页个人资料日志图片视频(测)好友博客群百科 我的日志公交换乘算法 分类:编程语言2007.5.23 16:56 作者：清风 | 评论：4 | 阅读：统计失败 公交换乘简单算法:三个表（最简单化，不考虑模糊查询，单行线等其他东西）：1，站点表stop(stop_id,stop_name)2，路线表line(line_id,line_name)3，路线站点表(点线路关系表)linestops( line_id, stop_id, seq )此处的seq指某站点在某线路中的顺序。现在分析算法：1，直达线路首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2然后查询select line_id from(select line_id from linestops where stop_id = id1) A,(select line_id from linestops where stop_id = id2) Bwhere A.line_id = B.line_id即得到可直达的线路列表2,一次换乘首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2然后搜寻两个站点通过直达方式各自能够到达的站点集合，最后他们的交集就是我们所需要的换乘站点。select stop_id from(select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id1)A,(select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id1)Bwhere A.stop_id= B.stop_id得到换乘站（可能有多个或0个）后，剩下的就是显示能够到达换乘站的两边线路，这通过前面的直达查询即可。3，二次换乘首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2算法的中心思想是：站点1能够通过直达到达的所有站点集合A，站点2能够通过直达到达的所有站点集合B，A和B之间有直达的线路。一步一步来：站点1能够通过直达到达的所有站点集合A：select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id1)站点2能够通过直达到达的所有站点集合B：select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id2)而直达的查询是select line_id from(select line_id from linestops where stop_id = id1) C,(select line_id from linestops where stop_id = id2) Dwhere C.line_id = D.line_id我们把=id1和=id2换成 in (select .)A 和 in (select .)B这样最后我们的查询是select line_id from(select distinct line_id from linestops where stop_id in 【A】) C,(select distinct line_id from linestops where stop_id in 【B】) Dwhere C.line_id = D.line_id其中【A】是（select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id1)其中【B】是（select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id2)这样子我们找到了作为中间换乘的线路（可能有多条或者0条），对列举的的每一条假设命名为X线，下一步就是找出可以从站点1到达X任意一个站点的直达线路、和可以从站点2到达X任意一个站点的直达线路即可。那么与前面的算法相似，我们在站点1所有能够到达的站点中去寻找和线路X相交的站点，然后再去找这两个点的线路select stop_id from(select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id1)A,(select stop_id from linestops where line_id = X ) Bwhere A.stop_id = B.stop_id找到站点了，下面就是根据已经解决的直达查询找线路了。站点2类似。以上的算法有一个优点，全部是sql完成搜寻，所以asp代码只需寥寥几行循环而已。但是缺点是：慢,毕竟可能涉及了数百次sql查询。而且只是用最简单的sql方法去算出所有可以换乘的方案，不涉及最优/最短的算法。如果是最短路径，那得用特殊结构和算法。 另外:根据出行者输入的起点和终点，确定出行要选择的起始公交站点A和目的公交站点B。搜索数据库，查询站点A和站点B之间是否有相同的车经过，如果有一条或几条直达线路，通过比较选择距离最短的公交线路推荐给出行者。如果没有，则计算站点A和站点B之间有没有一个公共站点C，从站点C可以换乘到达站点B。这就有两种情况：(1)如果有，属于一次换乘。计算站点A和公共站点C之间有没有相同的公交车经过并存入集合X；同样，计算站点B和公共站点C之间有没有相同的公交车经过并存入集合Y。将这两个集合比较后就可以得到从站点A经过公共站点C到达站点B的公交线路，在这些线路中进行比较，选择距离最短的推荐给出行者。（2）如果没有公共站点C，就出现了要换乘两次的情况。将经过站点A的每条公交线路的所有站点存入集合O；同样，经过站点B的每条线路的所有站点存入集合P。比较这两个集合，先乘经过站点A的某一路车到达某一站点D，计算站点D与站点B之间有没有公共站点E,如果有则站点D、E为换乘站点。这种方案可能有多种，比较选择距离最短的推荐给出行者。如果不存在公共站点E，说明经过两次换乘无法从站点A到达站点B，停止搜索计算。公交出行最优路线具体算法：1） 输入起始站点A和目的站点B；2） 搜索系统数据库，经过起始站点A的公交线路存为X(i)(i=1,2,3,m,m为正整数)，经过目的站点B的公交线路存为Y(j)(j=1,2,3,n,.n为正整数)；3） 判断是否有X(i)=Y(j)，将满足条件的存入Z。若Z1，则该条公交线路X(i)即Y(j)为从站点A到站点B的直达最优线路，输出结果并结束运算。Z1，计算Z中各条线路的距离，选择一条距离最短的线路，输出结果并结束运算；4） 搜索系统数据库，公交线路X(i)所包含的站点存为O(i,u)(u=1,2,3,g,g为正整数)公交线路Y(j)所包含的站点存为P(j,v)(v=1,2,3,h,h为正整数)；5） 判断是否有O(i,u)= P(j,v)，将满足条件的存入W。若W1，则站点O(i,u)即P(j,v)为从站点A到站点B的一次换乘站点，公交线路X(i)，Y(j)为换乘一次的最优路线，输出结果并结束运算。若W1，分别计算每条换乘路线的距离，选择一条距离最短的线路，输出结果并结束运算；6） 搜索系统数据库，经过站点O(i,u)的公交线路存为R(k)(k=1,2,3,p,p为正整数)，公交线路R(k)所包含的站点存为G(k,t)(t=1,2,3,q,q为正整数)；7）判断是否有G(k,t)=P(j,v)，将满足条件的存入S。若S1，则站点G(k,t)即P(j,v)为从站点A到站点B的二次换乘站点，公交线路X (i)，R(k)，Y(j)为换乘二次的最优路线，输出结果并结束运算。若S1，分别计算每条换乘二次的路线距离，选择一条距离最短的线路，输出结果并结束运算；8） 以上步骤没有找到合适的公交线路,输出“没有找到换乘次数不超过两次的最优公交线路”，结束运算。本文讨论的公交出行最优路线算法，主要是以距离为标准。在得出了换乘方案之后，可以进一步考虑时间因素，从而找到更具优胜性的换乘方案，这有待进行进一步的探讨、研究。你可以通过这个链接引用该篇文章:/viewdiary.15969393.html 引用到我的博客：0 | 收藏到我的博客 基于 ArcGis. 上一篇 | 下一篇 Windows下J. 我的广告我的搜索 Web bokee 输入您的搜索字词 提交搜索表单 文章评论添加评论已有4位对此文章感兴趣的网友发表了看法【点击查看】 昵 称： 主 页： (选填)看了你写的文章，很不错！ 验证码： 个人形象 加为好友 发送私信 给我留言 加入收藏 我的群组 荐给好友 英语测试 定制广告男人自慰的六点迷思 自慰向来是许多人的心灵秘密花园，如此刻意忽略自己为自己制造的快乐，并隔着一层面纱看待自慰，迷思于是产生. 定制广告相关博客文章数据读取中. 相关服务关于博客关于博客网用户帮助产品展示频道推荐热点与排行 什么是博客?本站介绍用户注册博客搜索