【前言】:
最近几年,社会上地理信息系统和电子地图技术越来越受到大家的关注,很多单位和个人都投入了大量的人力和物力进行了相关的设计开发。在这些实际的开发问题中,我想就公交车换乘自动查询系统的核心算法的设计和分析做一个不成体统的研究,还希望同志们能帮我指正错误,帮助提高。
【问题的提出】:
一个城市中,有大量的公交线路和站点,公交线四通八达,现实中,一个站点A到另一个站点B,应该有大量的不同选择的路线可以走,每一条线路中间可能转车,可能直达,路线所花费的时间和路程是完全不同的。
那么,如何帮助路人选择一个最俭省时间和路程的线路来走呢?
我想,我们是不是应该首先对公交车换乘问题,进行数学建模,在其上设计一套完整的寻址算法,然后再在算法的基础上设计一套自动的查询软件,用以实际生活中呢?
所以,我就试着做了点自己的开发,对该问题提出了一点自己的算法设计想法,做的不好,还望各位同仁和前辈指点。
【对问题的数学建模】:
一个城市中,有大量的公交车站点,为了数学建模的方便,我们在这里假设,在一个地点只有一个相同的站点,我们不考虑一个相同的地点前后几米的位置有两三个不同的站点的现象,我们将距离附近的一切公交车站点抽象集合在一起,看成一个统一的地点。我们将这些独立的包含各种公交车站点的地点,看成无向图中间独立的各个结点。
于是,问题就变成,在一个拥有大量结点的无向图中,如何求任意两个点之间的最短距离的离散数学问题。
关于这个问题的算法设计,古今中外很多数学家都提出了自己的有效的算法。由于本问题中,我们所要求求得路径应该是精确的值,也就是说,我们不希望得到的是,可能的优化的解,而是对所有可能穷尽后的最合适花费最小的解,所以,我在这里不自量力,狗胆提出一些自己对本问题的看法和算法方面的一些设计想法。
【算法的提出】:
首先,对于无向图中任意两个结点之间最短路径求最精确解的问题,我们首先想到的应该是穷尽算法,也就是说,将所有可能的路径线路的值求出,然后用合适的算法进行排序,选出最短的,输出为解。
注:我们为结点设计一个二维表,用来存放各个结点之间的邻近距离,比如现在假设有五个结点A,B,C,D,E,其中结点之间的路径关系如下图
其中,5是A到B的长度,10是B到C的长度,2是B到D的长度,7是D到C的长度
据此我们设计如下二维表:
由于这个二维表中上三角矩阵和下三角矩阵雷同,所以在实际处理中,我们只考虑下三角的部分,在这个表中,NULL表示两点之间没有直接相邻,但并不代表两点不可达!+∞就表示两点不可达,即根本没有线路连接两点。在本程序中,我们考虑用二维数组point[x][x]表示上述二维数组,其中x变量表示的是无向图中的各个站点,数组的取值就是站点之间的距离值,比如上述的二维表转换成为数组就成为:point[1][0]=5;point[2][0]=”NULL”;point[4][0]=” +∞”;
算法如下:
算法开始
输入:point[X][Y],开始结点begin,结束结点end
第一步:建立单链表LINK,用来存放每一次选择路线的路径结果和相应的路线。建立中间变量temp,用来存放每次路径选择中的暂时的长度。建立堆栈STACK,用来将每次选择的结点压栈,在最后穷尽失败的时候可以返回退栈重新选择新的路线。
第二步:for(y=0;y<end;y++)
{
x=begin;
建立一个LINK结点Aa;
do{
while(point[x][y]!=”NULL”&&point[y][end]!= ” +∞”&&y!=end)
{
结点压栈;
temp+=point[x][y];
将y添加到Aa结点用来存放路线的属性里面;
begin=y;
}
if(y= =end)
{
将temp添加到Aa的存放路径长度的属性里面;
将Aa添加到LINK链表;
}
else{清空Aa;}
将结点出栈;
begin=出栈结点下标;
}while(STACK非空);
}
第三步:对LINK里面的结点进行排序,输出长度最小的结点的路线序列;
算法结束
【对算法的修改和改良】:
大家都注意到了,这个算法,穷尽一切可能的达到的结点序列,并且计算一切的结点序列路径和,最后进行数值比对,然后求出最优的结果。虽然可以很精确的求出最优的结果,但是在现实的问题的处理中间,如果当结点数目相当大的时候,想要快速实时的完成这个问题的求值可以说是impossible mission,如果想要开发一个实时的迅速的公交车查询系统,这种算法显然是不足取的。
因此,我考虑对原有的死板的算法进行优化。
首先,我们分析原有算法,很明显的看出,原有的算法,最大的时间开销在于它会穷尽一切可能的结点序列,不会遗漏每条路线的求值。但是在现实中,是不是会出现这样一个现象,我们可以利用已知的可达的线路的路径长度,排除掉在其他计算过程中明显大于它的结点序列,提前中断序列搜索的进行。
比如,在上图中,我们从A出发到达C,我们依据原有算法,在一开始从A走到B再走到C,得到的路径总长度是15。现在我们重新,从A到B到D到C,在这个过程中,当我们到达D的时候,路径的总长度就已经达到了17,就是说已经超过了15,那么再往下面搜索就没有目的了,我们可以提前从搜索中中断,转入下一序列的搜索。
依据这个原理,我们可以设计一个length用来存放已知最小的路径总长度,然后在搜索途中实时的与它进行大小对比,对比它大的搜索立即中断,转入下一搜索。
依据这个想法,如果选取的length适合,我们将可以大大降低算法的搜索深度,加快搜索的时间效率。
好了!想法有了,那么下面的问题就在于如何求出这个length,这是一个两难的问题,我们当然可以在程序内部每次执行一次扫描,选出最小的路径总长度将它放置在length里面,但是排序算法也是需要消耗时间的,而且将大量的排序内置在外围的循环中,这不能说一个良好的主意。
对此我的看法是,在程序之中,是否可以每隔一定的搜索次数后,进行一次排列算法,找到现在已知的路径总长度中的最小值,将其赋值给length,如果经过相关计算,选定优秀的搜索次数,可以保证算法的稳定和优秀的效率。
由于时间有限和专业知识的缺乏,我并不能提供出关于搜索次数的证明和计算公式。
在这里我只能提出对原有穷举算法的改良
算法开始
输入:point[X][Y],开始结点begin,结束结点end,输入循环次数count
第一步:建立单链表LINK,用来存放每一次选择路线的路径结果和相应的路线。建立中间变量temp,用来存放每次路径选择中的暂时的长度。建立堆栈STACK,用来将每次选择的结点压栈,在最后穷尽失败的时候可以返回退栈重新选择新的路线。
建立中间变量length,存放已知的最短总路径长度
第二步:for(y=0;y<end;y++)
{
x=begin;
建立一个LINK结点Aa;
int I;
do{
while(point[x][y]!=”NULL”&&point[y][end]!= ” +∞”&&y!=end)
{
结点压栈;
temp+=point[x][y];
将y添加到Aa结点用来存放路线的属性里面;
if(temp>=length){temp=0;break;}
begin=y;
}
if(y= =end)
{
将temp添加到Aa的存放路径长度的属性里面;
将Aa添加到LINK链表;
}
else{清空Aa;}
将结点出栈;
begin=出栈结点下标;
I ++;
if(count= = I )
{I =0;
对已知路径总长度进行排序,选出最短路径赋值给length;
}
}while(STACK非空);
}
第三步:对LINK里面的结点进行排序,输出长度最小的结点的路线序列;
算法结束
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/nanjingjiangb/archive/2006/03/26/639222.aspx
分享到:
相关推荐
基于dijkstra算法的最小换乘代码..........
公交车换乘算法.txt
公交车换乘
公交换乘算法可以用于互联网公交分析,里面有算法描述,功能很请打
实现多次换乘得基本原理,教学用得 公交换乘算法 c# 实现多次换乘到达
如果换乘次数超过3(也就是最少需要换乘4次坐5次公交车,默认不可达),建议在执行是不要使用换乘次数为3次坐4辆公交车的算法,因为如果真的遇到不可达的2站,需要进行3次换乘算法的查找时会非常费时间(根据实际...
公交一次换乘算法,在线效果演示:http://bus.faqee.com,(本文件包含一次换乘算法的源码)
关于公交查询及换乘的算法源代码的非常详细的资料,有各论坛对这个算法的研究资料,有完整的查询系统,有详细的分析,还有建模用的论文。
Algorithm for finding optimal paths in a public transit network TRB[RESUBMIT]
// 取得出发站点所经的公交车的字符串 // 取得目的地所经的公交车的字符串 // 取得两个站点都存在的站点,即可以直达的公交车 // 解析出发点与目的地的公交车的字符串,得到两个数组 // 分别以...
基于python实现的公交换成系统源码(求解最短路径+最少换乘问题)带GUI界面.zip 基于python实现的公交换成系统源码(求解最短路径+最少换乘问题)带GUI界面.zip 基于python实现的公交换成系统源码(求解最短路径+最少换乘...
公交线路GIS系统源码+数据库(包括公交换乘算法(最短路径算法)).zip 公交线路GIS系统源码+数据库(包括公交换乘算法(最短路径算法)).zip 公交线路GIS系统源码+数据库(包括公交换乘算法(最短路径算法)).zip...
大数据-算法-粘贴式LED公交电子站牌设计及公交车与公用自行车换乘算法
问题描述:已知站点,线路-站点数据,求指定点之间的: 1、 直达线路 2、 一次换乘线路 3、 两次换乘线路 本资源是用matlab编程的代码,从原理上对换乘算法进行了程序化。
问题描述:已知站点,线路,线路-站点数据,求指定点之间的: 1、直达线路 2、一次换乘线路 3、两次换乘线路
本课题研究的主要内容是利用最优路径算法来实现公交换乘查询系统。在这个系统中实现的功能主要有:1、数据库维护 管理员用来增加公交站点、公交路线等,或在现有数据库中增加、删除、修改公交线路信息。2、换乘查询 ...
Python公交换乘系统源码.zip
本文虽没有基于DIJKSTRA算法去查找最短路径,但仍能找出最短路径,而且在MFC界面下,窗口更友好.
包含完整源程序,.exe文件,算法介绍,主要功能函数介绍,比较详细!(课程设计报告雷同不太好吧,还是要靠自己做哦!) 线路交叉的换乘站的重合的线路使用同一站名,当输入合法的上、下车站名时,将输出换乘的线路...