最短路径算法分析2.doc

随着计算机和地理信息科学的发展,地理信息系统因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,通用的网络分析功能包括路径分析、资源分配、连通分析、流分析等。网络分析中最基本和最关键的问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位。从道路网络模型的角度看,最短路径分析就是在指定道路网络的两节点间找出一条阻碍强度最小的路径。根据阻碍强度的不同定义,最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。因此,城市道路网作为一种大型网络设施有其本身的特征。它一方面包含网络本身的拓扑特征;另一方面还包含了大量反应地理位置特征的几何数据。本文根据道路网的特点,运用GIS网络分析功能对道路网络模型、道路的权重选择以及快速寻求路网中两节点间的最短路径算法分别进行了研究。1 道路网模型及权重设置1.1 道路网模型建立城市道路网主要由众多道路相交、相连构成。在纵横交织、错综复杂的道路网络中,道路间的地理位置关系相当复杂,一条道路可能与若干条道路相交相连,且其相交相连的模式复杂。为了避免过多地考虑道路间的拓扑关系,抽取道路网中道路交叉路口作为分析对象,并对道路以交叉路口为结点进行分割,成为路段。这样,整个网络图将由交叉路口点和路段组成,并定义交叉路口点为网络的结点,路段为网络的弧。从而建立基于路段连接的网络模型,其模型形式表述为:式中,RW代表道路网络;N代表结点集;R代表路段集合,其元素为有序对,表示由结点x到结点y存在一条有向通路;LR代表路段长度集合,其元素表示有向路段的加权长度。其中,路段的加权长度是指根据目标函数要求,综合各种动态实时信息和静态属性信息后所得的路段参数,而并非真实意义下的长度。1.2 道路网权重选择在交通路网中,两点间最优路径算法的优劣主要受到2个因素的影响,即所使用的最短路径算法和所选择的道路权重。最短路径算法是路径选择的搜索工具,决定了如何在庞大的路网数据库中找到最佳的可行路径。道路权重则是路径选择的搜索指标,是最短路径算法的依据。因此,道路权重的选择直接影响到最优路径算法的合理性。一个城市的道路网络由不同等级的道路组成,不同等级的道路的通行能力和功能要求均不相同。只有整个城市的交通负载根据出行者目的的不同,均衡分布在不同等级的道路上,城市的路网才能得到最有效的利用。因此单纯的选择距离、时间或道路的通行能力作为道路权重都不太客观,需要选择一种比较综合的指标作为道路权重。可达性是Hansen于1959年首次提出的概念,用于定义交通网络中各结点间相互作用机会的大小。其表述的是路网中任意点之间通达的可能性及难易程度,数学上指单位时间内可实现通达的直线距离1,即为可达能力(km/m),是可达性的量度。可达性同时考虑了时间和距离的因素,把道路交通的固定设施和移动工具有机结合起来,而且避免了以道路通行能力作为权重可能造成的城市路网全局负载问题。因此以可达性为道路权重是一个比较综合的指标,具有更大的合理性。2 最短路径算法最短路径问题的算法有很多种,包括基于限制条件的深度优先搜索算法、Dijkstra算法、Floyd算法、A*算法等,各种算法在空间复杂度、时间复杂度、易实现性等方面各具特色。其中,采用启发式策略的Dijkstra算法是目前公认的求解最短路问题的经典算法。但Dijkstra算法在基于网络的权矩阵求解最短路问题的计算机算法和程序中,运用了关联矩阵、邻接矩阵和距离矩阵的概念。在存储图形数据和运算时,需要定义NN的数组(其中N为网络的结点数),当网络的结点数较大时,将占有大量的计算机内存。如果不对Dijkstra算法进行优化,该算法很难在实际中得到应用。在原始的Dijkstra算法中,每次在临时标记点中搜索路径最短的结点时都要遍历所有的临时标记结点。解决办法就是将临时标记结点按照最短路径排序,每个搜索过程不必全部遍历或者较少地遍历临时标记点。或者尽量减少最短路径分析过程中搜索的临时结点数量。基于此思想,提出了以下优化算法。2.1 算法原理利用两点之间直线最短的原理,在道路网中,如果两结点间存在一条边,则该边为两结点间的最短路径。若不存在一条边,则连接起、止点的直线段代表了一个路线的趋势,顺着连线方向的某条边是最短路径的可能性最大。依据此思想,可以构造2个矢量,矢量一以当前结点为起点,目标点为终点;矢量二以当前结点为起点,当前结点的邻接点为终点。将矢量二的方向值与矢量一的方向值相减得到两矢量间的夹角。由夹角最小的边组成的路径最接近于最短路径。 由于只依据矢量夹角作为求解最短路径中路段集合的要素,可能造成求得的路径因左右方向的震荡而增加路径的总长度,使求得的解大于实际最短路经长,所以在每次搜索最短路径顶点时,将当前结点的邻接点按照矢量夹角大于零和小于零分为两组,分别在两组中选取矢量夹角绝对值的最小值对应的结点。算法采用双向搜索,从起点S开始进行正向搜索,同时从终点T进行逆向搜索。两个方向每一步都要搜索与指定直线段左右两侧各一条夹角最小的边,直到二者会合或直到目标点,最后取两个方向搜索到的距离最短的路径为所求解。2.2 算法具体步骤假设需要求解最短路径的两个结点分别为S点和T点,其中起点为S、终点为T。定义ds(i)表示源结点S到结点i的加权距离;dt(j)表示目标点T到结点j的加权距离; ps(m)、pt(m)表示结点m的状态,分为未标记结点(0)和标记结点(1)两种,其中ps表示正向搜索(从S出发)过程中的状态,pt表示逆向搜索(从T出发)过程中的状态。第一步:初始化:对所有结点i,若i=S,则ds(i)=0, ps(i)=1;若i=T,则dt(i)=0, pt(i)=1;否则ds(i), dt(i),ps(i)=0, pt(i)=0。并定义一个数变量k作为循环变量,初始化为k=0。第二步:判断S与T之间是否邻接,若邻接,则连接两端点的边即为所求最短路径。否则,转第三步。第三步:令S、T分别为两棵二叉树的根节点,分别从S、T出发,在直线段ST、TS左右两侧各寻找一条与、夹角最小的边,把搜索到的边加入对应的二叉树。设从S点出发搜寻到的两条边的另一端点分别为A1、A1,计算SA1、SA1的加权距离,分别记为ds(A1)、ds(A1);从T点出发搜寻到的两条边的另一端点分别为B1、B1,记TB1、TB1的加权距离分别为dt(B1)、dt(B1)。第四步:将ds(A1)、ds(A1)作为当前点A1、A1的标记值,d t(B1)、dt(B1) 作为当前点B1、B1的标记值。也就是将起点或终点至该临时标记点子路径上所有边的权值之和作为当前点的标记值。同时ps(A1)、ps(A1)、 pt(B1)、pt(B1)均变为1。第五步:用A1、A1分别代替S,B1、B1分别代替T,然后变量k自增k=k 1,重复第二、三、四步,但第三步中是从A1(A1)、B1(B1)出发,在直线段A1T(A1T)、TB1(TB1)左右两侧各寻找一条与夹角绝对值最小的边。把搜索到的边加入对应的二叉树,对二叉树的当前点分别计算标记值并作标记。以此类推,直至An,Bn会合于一点,即正向和逆向搜索都对同一点进行了标记,则点列S,A1,An(Bn),B1,T组成可能最短路径,路径长度为ds(An) dt(Bn)。若二者没有会合,也即双向搜索都未对同一点进行标记,则正向搜索到终点T,逆向搜索到起点S,生成两棵特殊的二叉树。相应方向已标记过的点不在搜索范围之内。第六步:搜索结束后,若会合于一点,则取会合点处的标记值之和ds(An) dt(Bn)作为可能最短路径长度;若没有会合,则取终点T(正向搜索)或起点S(逆向搜索)处的标记值ds(T)、dt(S)作为可能最短路径长度。取其中最小值min ds(An) dt(Bn), ds(T), dt(S)即为所求最短路径长度。如果所求最短路径中包含会合点,则最短路径由会合点开始沿与之相关联的两条边依次寻找求解的最短路径的标记结点,加入路径队列,直至S、T。若没有会合点,则从起点S或终点T开始,在二叉树中顺次寻找所求最短路径的相关结点,直至达到T或S,便得到最短路径序列。搜索流程如图1。3 结论本文根据城市交通道路网的特点,建立了道路网数据模型,并在综合考虑人们出行时的时间消耗和能量消耗的情况下,选择可达性作为道路权重,以此为搜索指标进行最短路径分析。本文所用最短路径算法对经典的Dijkstra算法进行了改进,在每次搜索过程中,不必遍历图中所有未标记的结点,只搜索当前结点的邻接结点。对于实际的道路网,每个结点的邻接点个数一般为25个,较之Dijkstra算法大大减少了搜索范围。而且求解的只是源点到终点间的最短路径,搜索的速度快,也增加了适用性。参考文献1白尘.交通路网中最优路径算法的道路权重选择.中国管理信息化,2009,12(15):54-56.2鲍培明.距离寻优中Dijkstra算法的优化.计算